REVIEW 3 cited by
Learning marginals suffices!
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
Beyond computer science, quantum complexity theory can potentially revolutionize multiple branches of physics, ranging from quantum many-body systems to quantum field theory. In this paper, we investigate the relationship between the sample complexity of learning a quantum state and the circuit complexity of the state. The circuit complexity of a quantum state refers to the minimum depth of the quantum circuit necessary to implement it. We show that learning its marginals for the quantum state with low circuit complexity suffices for state tomography, thus breaking the exponential barrier of the sample complexity for quantum state tomography. Our proof is elementary and overcomes difficulties characterizing short-range entanglement by bridging quantum circuit complexity and ground states of gapped local Hamiltonians. Our result, for example, settles the quantum circuit complexity of the multi-qubit GHZ state exactly.
Forward citations
Cited by 3 Pith papers
-
Quantum state determinability from local marginals is universally robust
Unique determinability of multipartite quantum states from local marginals is robust to small errors, with global deviations bounded by a power law, linear robustness certifiable by SDP, and applications to scalable e...
-
Certifying Quantum States with Uniform Measurements
Uniform (global) measurements suffice to efficiently certify a family of graph states, with a provable performance guarantee.
-
Pauli Measurements Are Near-Optimal for Single-Qubit Tomography
Single-qubit measurements need Ω(10^N/(√N ε²)) copies for N-qubit tomography, matching the Pauli-measurement upper bound up to a √N factor.
Discussion (0). Sign in to comment.