Learning shallow quantum circuits

Abstract

Despite fundamental interests in learning quantum circuits, the existence of a computationally efficient algorithm for learning shallow quantum circuits remains an open question. Because shallow quantum circuits can generate distributions that are classically hard to sample from, existing learning algorithms do not apply. In this work, we present a polynomial-time classical algorithm for learning the description of any unknown $n$-qubit shallow quantum circuit $U$ (with arbitrary unknown architecture) within a small diamond distance using single-qubit measurement data on the output states of $U$. We also provide a polynomial-time classical algorithm for learning the description of any unknown $n$-qubit state $|\psi ⟩=U|0^n⟩$ prepared by a shallow quantum circuit $U$ (on a 2D lattice) within a small trace distance using single-qubit measurements on copies of $|\psi ⟩$. Our approach uses a quantum circuit representation based on local inversions and a technique to combine these inversions. This circuit representation yields an optimization landscape that can be efficiently navigated and enables efficient learning of quantum circuits that are classically hard to simulate.

arXiv comment10 pages, 14 figures (7 inline; 7 floating) + 76-page appendix

References in corpus (51)

• Improved Simulation of Stabilizer Circuits
• Predicting Many Properties of a Quantum System from Very Few Measurements
• Parameterized quantum circuits as machine learning models
• Matrix Product States and Projected Entangled Pair States: Concepts, Symmetries, and Theorems
• A simple formula for the average gate fidelity of a quantum dynamical operation
• Challenges and Opportunities in Quantum Machine Learning
• Grover's quantum searching algorithm is optimal
• Connecting ansatz expressibility to gradient magnitudes and barren plateaus
• The randomized measurement toolbox
• Quantum-assisted quantum compiling
• Layerwise learning for quantum neural networks
• Classical simulation of noninteracting-fermion quantum circuits
• Probabilistic error cancellation with sparse Pauli-Lindblad models on noisy quantum processors
• Learning the quantum algorithm for state overlap
• Efficient tomography of a quantum many-body system
• Beyond Barren Plateaus: Quantum Variational Algorithms Are Swamped With Traps
• Robust Online Hamiltonian Learning
• Structure optimization for parameterized quantum circuits
• Noise Resilience of Variational Quantum Compiling
• Trainability of Dissipative Perceptron-Based Quantum Neural Networks
• Learning Quantum Systems
• Index theory of one dimensional quantum walks and cellular automata
• Computational advantage of quantum random sampling
• Quantum advantage with noisy shallow circuits in 3D
• Barren plateaus preclude learning scramblers
• Sample-efficient learning of quantum many-body systems
• The Perfect Distinguishability of Quantum Operations
• Adaptive Variational Quantum Dynamics Simulations
• Efficient estimation of Pauli channels
• Schur-Weyl Duality for the Clifford Group with Applications: Property Testing, a Robust Hudson Theorem, and de Finetti Representations
• Architectures for quantum simulation showing a quantum speedup
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
• Enhancing Generative Models via Quantum Correlations
• Out-of-distribution generalization for learning quantum dynamics
• Learning many-body Hamiltonians with Heisenberg-limited scaling
• Quantum advantages for Pauli channel estimation
• Robust quantum compilation and circuit optimisation via energy minimisation
• Shadow process tomography of quantum channels
• Classical Shadows for Quantum Process Tomography on Near-term Quantum Computers
• Generative Quantum Learning of Joint Probability Distribution Functions
• Classical simulation of short-time quantum dynamics
• Three-dimensional quantum cellular automata from chiral semion surface topological order and beyond
• Learning Quantum Hamiltonians from Single-qubit Measurements
• Closing gaps of a quantum advantage with short-time Hamiltonian dynamics
• Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
• Learning quantum circuits of some $T$ gates
• Dynamical simulation via quantum machine learning with provable generalization
• Pauli error estimation via Population Recovery
• Practical Black Box Hamiltonian Learning
• Improved Stabilizer Estimation via Bell Difference Sampling
• Scalably learning quantum many-body Hamiltonians from dynamical data

Cited by in corpus (14)

• Barren Plateaus in Variational Quantum Computing
• Quantum Convolutional Neural Networks are Effectively Classically Simulable
• On the average-case complexity of learning output distributions of quantum circuits
• Optimal estimates of trace distance between bosonic Gaussian states and applications to learning
• Learning quantum states prepared by shallow circuits in polynomial time
• Learning unitaries with quantum statistical queries
• Agnostic Process Tomography
• Nearly query-optimal classical shadow estimation of unitary channels
• Quantum State Preparation for Probability Distributions with Reflection Symmetry Using Matrix Product States
• Unconditionally separating noisy ${\mathsf{QNC}}^0$ from bounded polynomial threshold circuits of constant depth
• Sample optimal tomography of quantum Markov chains
• Artificial intelligence for representing and characterizing quantum systems
• Short remarks on shallow unitary circuits
• Agnostic Tomography of Stabilizer Product States