Learning Properties of Quantum States Without the I.I.D. Assumption
arXiv:2401.16922 · doi:10.1038/s41467-024-53765-6
Abstract
We develop a framework for learning properties of quantum states beyond the assumption of independent and identically distributed (i.i.d.) input states. We prove that, given any learning problem (under reasonable assumptions), an algorithm designed for i.i.d. input states can be adapted to handle input states of any nature, albeit at the expense of a polynomial increase in training data size (aka sample complexity). Importantly, this polynomial increase in sample complexity can be substantially improved to polylogarithmic if the learning algorithm in question only requires non-adaptive, single-copy measurements. Among other applications, this allows us to generalize the classical shadow framework to the non-i.i.d. setting while only incurring a comparatively small loss in sample efficiency. We use rigorous quantum information theory to prove our main results. In particular, we leverage permutation invariance and randomized single-copy measurements to derive a new quantum de Finetti theorem that mainly addresses measurement outcome statistics and, in turn, scales much more favorably in Hilbert space dimension.
arXiv comment36+10 pages, 7 Figures. Close to the published version
References in corpus (46)
- Predicting Many Properties of a Quantum System from Very Few Measurements
- A Theory of Fault-Tolerant Quantum Computation
- Dynamical decoupling and noise spectroscopy with a superconducting flux qubit
- A quantum network of clocks
- Efficient quantum state tomography
- Direct Fidelity Estimation from Few Pauli Measurements
- Graph States for Quantum Secret Sharing
- Unknown Quantum States: The Quantum de Finetti Representation
- The randomized measurement toolbox
- Quantum certification and benchmarking
- Practical characterization of quantum devices without tomography
- Authentication of Quantum Messages
- Reliable Quantum State Tomography
- One-and-a-half quantum de Finetti theorems
- Faithful Squashed Entanglement
- Verifiable measurement-only blind quantum computing with stabilizer testing
- Multiqubit Clifford groups are unitary 3-designs
- Evidence for interacting two-level systems from the 1/f noise of a superconducting resonator
- Experimental demonstration of graph-state quantum secret sharing
- Verification of quantum computation: An overview of existing approaches
- Rotating-frame relaxation as a noise spectrum analyzer of a superconducting qubit undergoing driven evolution
- Experimental Verification of Multipartite Entanglement in Quantum Networks
- Optimal verification of entangled states with local measurements
- A de Finetti representation for finite symmetric quantum states
- Efficient Verification of Pure Quantum States in the Adversarial Scenario
- Quantum Anonymous Transmissions
- Matchgate Shadows for Fermionic Quantum Simulation
- Anonymity for practical quantum networks
- General framework for verifying pure quantum states in the adversarial scenario
- Verified measurement-based quantum computing with hypergraph states
- Resource-efficient verification of quantum computing using Serfling's bound
- Shallow shadows: Expectation estimation using low-depth random Clifford circuits
- Scalable and Flexible Classical Shadow Tomography with Tensor Networks
- Efficient verification of Dicke states
- Anonymous quantum communication
- Optimal Verification of Greenberger-Horne-Zeilinger States
- Sample-efficient device-independent quantum state verification and certification
- Learning quantum states and unitaries of bounded gate complexity
- Thrifty shadow estimation: re-using quantum circuits and bounding tails
- Semidefinite programming hierarchies for constrained bilinear optimization
- Robust and efficient verification of graph states in blind measurement-based quantum computation
- Efficient verification of continuous-variable quantum states and devices without assuming identical and independent operations
- Sample-optimal classical shadows for pure states
- Verification of graph states in an untrusted network
- Quantum chi-squared tomography and mutual information testing
- Authenticated teleportation and verification in a noisy network