Learning quantum states and unitaries of bounded gate complexity

Abstract

While quantum state tomography is notoriously hard, most states hold little interest to practically-minded tomographers. Given that states and unitaries appearing in Nature are of bounded gate complexity, it is natural to ask if efficient learning becomes possible. In this work, we prove that to learn a state generated by a quantum circuit with $G$ two-qubit gates to a small trace distance, a sample complexity scaling linearly in $G$ is necessary and sufficient. We also prove that the optimal query complexity to learn a unitary generated by $G$ gates to a small average-case error scales linearly in $G$. While sample-efficient learning can be achieved, we show that under reasonable cryptographic conjectures, the computational complexity for learning states and unitaries of gate complexity $G$ must scale exponentially in $G$. We illustrate how these results establish fundamental limitations on the expressivity of quantum machine learning models and provide new perspectives on no-free-lunch theorems in unitary learning. Together, our results answer how the complexity of learning quantum states and unitaries relate to the complexity of creating these states and unitaries.

8 pages, 1 figure, 1 table + 56-page appendix; added numerics

References in corpus (75)

• Advances in Quantum Metrology
• Quantum Simulation
• Quantum metrology
• Solving the Quantum Many-Body Problem with Artificial Neural Networks
• A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States
• Improved Simulation of Stabilizer Circuits
• Quantum fingerprinting
• Predicting Many Properties of a Quantum System from Very Few Measurements
• Quantum state tomography via compressed sensing
• Quantum random access memory
• Complexity and Shock Wave Geometries
• The effect of data encoding on the expressive power of variational quantum machine learning models
• Efficient quantum state tomography
• Complexity, action, and black holes
• Data re-uploading for a universal quantum classifier
• Quantum Error Mitigation
• Quantum advantage in learning from experiments
• Quantum process tomography of a controlled-NOT gate
• Random Quantum Circuits
• Generalization in quantum machine learning from few training data
• Quantum Process Tomography: Resource Analysis of Different Strategies
• Demonstration of qubit operations below a rigorous fault tolerance threshold with gate set tomography
• Optimal, reliable estimation of quantum states
• The randomized measurement toolbox
• Sequential generation of entangled multi-qubit states
• Local random quantum circuits are approximate polynomial-designs
• Tomography of Quantum Operations
• The Second Law of Quantum Complexity
• Self-Consistent Quantum Process Tomography
• Probabilistic error cancellation with sparse Pauli-Lindblad models on noisy quantum processors
• Information-theoretic bounds on quantum advantage in machine learning
• Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space
• Permutationally invariant quantum tomography
• Efficient decomposition of quantum gates
• Sample-optimal tomography of quantum states
• Linear growth of quantum circuit complexity
• Introduction to Haar Measure Tools in Quantum Information: A Beginner's Tutorial
• TensorCircuit: a Quantum Software Framework for the NISQ Era
• Permutationally invariant state reconstruction
• Optimizing quantum process tomography with unitary 2-designs
• Models of quantum complexity growth
• Preparation of matrix product states with log-depth quantum circuits
• Classical Shadow Tomography with Locally Scrambled Quantum Dynamics
• Holographic quantum algorithms for simulating correlated spin systems
• Theoretical and Experimental Perspectives of Quantum Verification
• Random quantum circuits are approximate unitary $t$-designs in depth $O\left(n{t}^{5+o(1)}\right)$
• Experimental Comparison of Efficient Tomography Schemes for a Six-Qubit State
• Five Two-Qubit Gates Are Necessary for Implementing Toffoli Gate
• One qubit as a Universal Approximant
• Learning many-body Hamiltonians with Heisenberg-limited scaling
• Out-of-distribution generalization for learning quantum dynamics
• Reformulation of the No-Free-Lunch Theorem for Entangled Data Sets
• Quantum circuit complexity of one-dimensional topological phases
• Shallow shadows: Expectation estimation using low-depth random Clifford circuits
• Shadow process tomography of quantum channels
• Classical Shadows for Quantum Process Tomography on Near-term Quantum Computers
• Markovian Entanglement Dynamics under Locally Scrambled Quantum Evolution
• Learning efficient decoders for quasi-chaotic quantum scramblers
• Learning and Testing Algorithms for the Clifford Group
• Learning quantum circuits of some $T$ gates
• Unitary channel discrimination beyond group structures: Advantages of sequential and indefinite-causal-order strategies
• Pseudo-dimension of quantum circuits
• A single $T$-gate makes distribution learning hard
• Bell sampling from quantum circuits
• An Improved Sample Complexity Lower Bound for (Fidelity) Quantum State Tomography
• Query-optimal estimation of unitary channels in diamond distance
• Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix
• Learning quantum many-body systems from a few copies
• Transition Role of Entangled Data in Quantum Machine Learning
• Optimal quantum dataset for learning a unitary transformation
• Fundamental limitations for measurements in quantum many-body systems
• Unitarity estimation for quantum channels
• Empirical Sample Complexity of Neural Network Mixed State Reconstruction
• Non-local finite-depth circuits for constructing SPT states and quantum cellular automata
• Sample-Optimal Quantum Process Tomography with Non-Adaptive Incoherent Measurements

Cited by in corpus (19)

• Efficient learning of quantum states prepared with few fermionic non-Gaussian gates
• Entanglement-induced provable and robust quantum learning advantages
• The power and limitations of learning quantum dynamics incoherently
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits
• Optimal trace-distance bounds for free-fermionic states: Testing and improved tomography
• Learning Properties of Quantum States Without the I.I.D. Assumption
• Non-Clifford Cost of Random Unitaries
• On the average-case complexity of learning output distributions of quantum circuits
• Learning unitaries with quantum statistical queries
• Nearly query-optimal classical shadow estimation of unitary channels
• Pseudochaotic Many-Body Dynamics as a Pseudorandom State Generator
• Quantum circuit complexity and unsupervised machine learning of topological order
• Agnostic Process Tomography
• Learning the structure of any Hamiltonian from minimal assumptions
• Uncertainty-disturbance relations and applications
• Process Tomography for Clifford Unitaries
• Transfer learning of many-body electronic correlation entropy from local measurements
• Compression of quantum shallow-circuit states
• Run-length certificates in quantum learning: sample complexity and noise thresholds