Imagine you're trying to reconstruct a massive crossword puzzle, but you're only allowed to look at one letter at a time — never a whole word, never a crossing. Previous wisdom said that if the crossword had words stretching across the entire grid (long-range entanglement), you'd need to see crossings (entangling measurements) to reconstruct it. This paper says: no, you can do it letter by letter, as long as the puzzle is sparse enough — most squares are blank. The committed claim: n-qubit quantum states whose density matrices have at most s nonzero entries in some unknown product basis can be efficiently learned using only single-qubit measurements. When s is constant, both sample complexity and classical computation are polynomial. When s grows polynomially with n, sample complexity remains polynomial, though classical computation may blow up — unless the unknown basis is a product of bases drawn from a known finite set (e.g., Pauli eigenbases), in which case computation is quasipolynomial. This matters because the standard assumption in quantum state tomography is that long-range entanglement demands entangling measurements. Full tomography of an n-qubit state requires exponential resources, and previous efficient approaches to structured states like sparse ones relied on entangling gates — multi-qubit operations that are expensive, noisy, and hardware-constrained on current devices. Eliminating entangling gates from the measurement protocol is a concrete hardware simplification, not a theoretical convenience. The algorithmic architecture belongs to the family of adaptive measurement and classical post-processing schemes for quantum tomography. The key structural insight is that sparsity in a product basis creates enough structure that information about nonzero entries can be extracted from marginal single-qubit statistics, even when correlations span the full system. The classical reconstruction problem then reduces to identifying the unknown product basis and inverting the sparse matrix, which is where the computational complexity splits depending on the sparsity regime. On the ladder, the relevant comparisons are compressed sensing approaches to quantum tomography (Gross et al., Flammia et al.) and shadow tomography (Huang, Kueng, Preskill). Shadow tomography already achieves polynomial sample complexity for predicting many properties, but typically requires random entangling circuits for full generality. Compressed sensing assumes low rank rather than sparsity in a product basis. This paper carves out a new structural assumption — sparsity in an unknown product basis — and shows it's learnable with strictly weaker measurements than previously required. It doesn't claim to beat these approaches on their own turf; it opens a different door. The integrity picture is theoretical: the results are information-theoretic and algorithmic, established through mathematical proof — sample complexity bounds and algorithmic correctness — not through numerical experiments or hardware demonstrations. This is appropriate for the claim being made (possibility results, not performance benchmarks), but it means no empirical validation exists. The gap between polynomial-in-principle and practical-on-hardware remains unaddressed. The successor question is the obvious one: run this on a real quantum device. The authors frame their results as "compatible with current quantum devices," but no experimental demonstration is included. The honest read is (a) — this is a theory paper, and experimental implementation is a different team's job — but also partly (c), because a hardware demo would be the natural next publication. The other glaring omission is noise: real single-qubit measurements have errors, and the robustness of the reconstruction algorithm to finite measurement noise and state preparation errors is not analyzed.
