Track the frontier, from condensed matter to cosmology.
Search papers, labs, and topics across Lattice.
The authors address the challenge of reconstructing $n$-qubit quantum states that are $s$-sparse in an unknown product basis, which typically exhibit long-range entanglement that defeats standard local tomography. While previous protocols relied on resource-intensive entangling circuits to capture this non-local structure, this work proves that sparse states can be fully characterized using strictly single-qubit measurements. The resulting algorithm achieves polynomial sample and classical computational complexity for constant sparsity, and retains polynomial sample complexity with quasipolynomial classical runtime when sparsity scales polynomially over fixed single-qubit basis sets.
Long-range entangled quantum states can be fully reconstructed without entangling measurement circuits, collapsing the hardware requirements for sparse state tomography down to single-qubit readouts.
We study the problem of learning a sparse quantum state, an $n$-qubit quantum state whose density matrix has at most $s$ nonzero matrix entries in an unknown product basis. While such states admit compact classical descriptions, they can carry long-range entanglement that prevents reconstruction from local reduced density matrices alone. Therefore, previous learning approaches addressed such long-range-entangled states using many entangling gates to extract the necessary information. In this work, we show that sparse states can nevertheless be efficiently learned using only single-qubit measurements. Specifically, when the sparsity $s$ is constant, our algorithm can learn sparse states from single-qubit measurements with polynomial sample complexity and classical computational complexity. When $s$ grows polynomially with $n$, sparse states can still be learned from single-qubit measurements with polynomial sample complexity, although efficient classical computation is not guaranteed in general. In this regime, however, the classical computational complexity becomes quasipolynomial when the state is sparse in an unknown basis that is a product of a known fixed finite set of single-qubit bases (e.g., eigenbases of Pauli operators). These results establish efficient learning of sparse states with long-range entanglement without entangling gates, and the single-qubit measurement requirements make our algorithms compatible with current quantum devices.