On the average-case complexity of learning output distributions of quantum circuits

Abstract

In this work, we show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model. This learning model is widely used as an abstract computational model for most generic learning algorithms. In particular, for brickwork random quantum circuits on $n$ qubits of depth $d$, we show three main results: - At super logarithmic circuit depth $d=\omega (\log (n))$, any learning algorithm requires super polynomially many queries to achieve a constant probability of success over the randomly drawn instance. - There exists a $d=O(n)$, such that any learning algorithm requires $\Omega (2^n)$ queries to achieve a $O(2^{-n})$ probability of success over the randomly drawn instance. - At infinite circuit depth $d\to \infty$, any learning algorithm requires $2^{2^{\Omega (n)}}$ many queries to achieve a $2^{-2^{\Omega (n)}}$ probability of success over the randomly drawn instance. As an auxiliary result of independent interest, we show that the output distribution of a brickwork random quantum circuit is constantly far from any fixed distribution in total variation distance with probability $1-O(2^{-n})$, which confirms a variant of a conjecture by Aaronson and Chen.

62 pages

References in corpus (35)

• Generative Adversarial Networks
• Quantum Circuit Learning
• Improved Simulation of Stabilizer Circuits
• Evaluating analytic gradients on quantum hardware
• Training Compute-Optimal Large Language Models
• Instantaneous non-local computation of low T-depth quantum circuits
• The Heisenberg Representation of Quantum Computers
• Evenly distributed unitaries: on the structure of unitary designs
• Classical simulation of noninteracting-fermion quantum circuits
• Random Quantum Circuits are Approximate 2-designs
• Local random quantum circuits are approximate polynomial-designs
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Provable Bounds for Learning Some Deep Representations
• Beyond Barren Plateaus: Quantum Variational Algorithms Are Swamped With Traps
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• The Born Supremacy: Quantum Advantage and Training of an Ising Born Machine
• Models of quantum complexity growth
• The spectral gap for some spin chains with discrete symmetry breaking
• Random quantum circuits are approximate unitary $t$-designs in depth $O\left(n{t}^{5+o(1)}\right)$
• On the Computational Efficiency of Training Neural Networks
• The Church of the Symmetric Subspace
• Unitary designs from statistical mechanics in random quantum circuits
• Efficient Simulation of Random Quantum States and Operators
• Improved spectral gaps for random quantum circuits: large local dimensions and all-to-all interactions
• Learning quantum states and unitaries of bounded gate complexity
• A single $T$-gate makes distribution learning hard
• Learning shallow quantum circuits
• Quantum statistical query learning
• Hardness of Learning Neural Networks with Natural Weights
• A Deep Conditioning Treatment of Neural Networks
• Learning quantum states prepared by shallow circuits in polynomial time
• Learning Quantum Processes with Quantum Statistical Queries
• On the Role of Entanglement and Statistics in Learning
• Learning (Very) Simple Generative Models Is Hard
• Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms

Cited by in corpus (2)

• Agnostic Process Tomography
• Resource-Dependent Complexity of Quantum Channels