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.

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

References in corpus (11)

• Challenges and Opportunities in Quantum Machine Learning
• Robust Online Hamiltonian Learning
• Learning Quantum Systems
• Computational advantage of quantum random sampling
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
• Learning many-body Hamiltonians with Heisenberg-limited scaling
• Classical simulation of short-time quantum dynamics
• Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
• 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