The Learnability of Quantum States

Abstract

Traditional quantum state tomography requires a number of measurements that grows exponentially with the number of qubits n. But using ideas from computational learning theory, we show that "for most practical purposes" one can learn a state using a number of measurements that grows only linearly with n. Besides possible implications for experimental physics, our learning theorem has two applications to quantum computing: first, a new simulation of quantum one-way communication protocols, and second, the use of trusted classical advice to verify untrusted quantum advice.

30 pages; added discussion of adaptive measurements, moved proofs to appendix, and corrected various minor errors

References in corpus (9)

• Improved Simulation of Stabilizer Circuits
• Scalable multi-particle entanglement of trapped ions
• Classical simulation of noninteracting-fermion quantum circuits
• Full characterization of a three-photon GHZ state using quantum state tomography
• Quantum tomography as a tool for the characterization of optical devices
• Prediction, Learning, Uniform Convergence, and Scale-sensitive Dimensions
• Quantum state tomography of dissociating molecules
• Quantum State Reconstruction From Incomplete Data
• QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols

Cited by in corpus (49)

• Machine learning and the physical sciences
• Parameterized quantum circuits as machine learning models
• Quantum generative adversarial networks
• Optimal, reliable estimation of quantum states
• Quantum certification and benchmarking
• Reconstructing quantum states with generative models
• Intelligent Computing: The Latest Advances, Challenges and Future
• Artificial Intelligence and Machine Learning for Quantum Technologies
• Learning Quantum Systems
• Quantum machine learning for quantum anomaly detection
• Global Optimality in Low-rank Matrix Optimization
• The Quantum Wasserstein Distance of Order 1
• Adversarial quantum circuit learning for pure state approximation
• Learning quantum data with the quantum Earth Mover's distance
• Nonstabilizerness determining the hardness of direct fidelity estimation
• Calibration of quantum sensors by neural networks
• The learnability scaling of quantum states: restricted Boltzmann machines
• Bound entanglement from randomized measurements
• Learning efficient decoders for quasi-chaotic quantum scramblers
• Spatial versus Sequential Correlations for Random Access Coding
• Variational quantum process tomography
• Random unitary maps for quantum state reconstruction
• Testing product states, quantum Merlin-Arthur games and tensor optimisation
• Learning quantum circuits of some $T$ gates
• Structural risk minimization for quantum linear classifiers
• Pseudo-dimension of quantum circuits
• Flexible learning of quantum states with generative query neural networks
• A single $T$-gate makes distribution learning hard
• Efficient Quantum State Sample Tomography with Basis-dependent Neural-networks
• Scalable Quantum Tomography with Fidelity Estimation
• Confidence Polytopes in Quantum State Tomography
• Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix
• Compressively characterizing high-dimensional entangled states with complementary, random filtering
• Online Learning of Quantum States
• Probing the geometry of correlation matrices with randomized measurements
• Efficient online quantum state estimation using a matrix-exponentiated gradient method
• Validating and Certifying Stabilizer States
• Ability of unbounded pairs of observers to achieve quantum advantage in random access codes with a single pair of qubits
• Spiking neuromorphic chip learns entangled quantum states
• On the Hardness of PAC-learning Stabilizer States with Noise
• Quantum Process Identification: A Method for Characterizing Non-Markovian Quantum Dynamics
• Binary Classification with Classical Instances and Quantum Labels
• Quantum states cannot be transmitted efficiently classically
• Quantum tomography with random diagonal unitary maps and statistical bounds on information generation using random matrix theory
• A learning theory for quantum photonic processors and beyond
• Learning quantum graph states with product measurements
• Clifford Circuits can be Properly PAC Learned if and only if $\text{RP}=\text{NP}$
• Identifying the value of a random variable unambiguously: Quantum versus classical approaches
• Correlation between concurrence and mutual information