A single $T$-gate makes distribution learning hard

Abstract

The task of learning a probability distribution from samples is ubiquitous across the natural sciences. The output distributions of local quantum circuits form a particularly interesting class of distributions, of key importance both to quantum advantage proposals and a variety of quantum machine learning algorithms. In this work, we provide an extensive characterization of the learnability of the output distributions of local quantum circuits. Our first result yields insight into the relationship between the efficient learnability and the efficient simulatability of these distributions. Specifically, we prove that the density modelling problem associated with Clifford circuits can be efficiently solved, while for depth $d=n^{\Omega (1)}$ circuits the injection of a single $T$-gate into the circuit renders this problem hard. This result shows that efficient simulatability does not imply efficient learnability. Our second set of results provides insight into the potential and limitations of quantum generative modelling algorithms. We first show that the generative modelling problem associated with depth $d=n^{\Omega (1)}$ local quantum circuits is hard for any learning algorithm, classical or quantum. As a consequence, one cannot use a quantum algorithm to gain a practical advantage for this task. We then show that, for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=\omega (\log (n))$ Clifford circuits is hard. This result places limitations on the applicability of near-term hybrid quantum-classical generative modelling algorithms.

arXiv comment5+12 pages, 3 figures

References in corpus (38)

• Quantum Machine Learning
• Machine learning and the physical sciences
• Noisy intermediate-scale quantum (NISQ) algorithms
• Improved Simulation of Stabilizer Circuits
• Characterizing Quantum Supremacy in Near-Term Devices
• Parameterized quantum circuits as machine learning models
• Roads towards fault-tolerant universal quantum computation
• A rigorous and robust quantum speed-up in supervised machine learning
• Positive Wigner functions render classical simulation of quantum computation efficient
• Negative Quasi-Probability as a Resource for Quantum Computation
• A generative modeling approach for benchmarking and training shallow quantum circuits
• CaloGAN: Simulating 3D High Energy Particle Showers in Multi-Layer Electromagnetic Calorimeters with Generative Adversarial Networks
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Information Scrambling in Computationally Complex Quantum Circuits
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Trading classical and quantum computational resources
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Differentiable Learning of Quantum Circuit Born Machine
• Generative Adversarial Networks recover features in astrophysical images of galaxies beyond the deconvolution limit
• Beyond Barren Plateaus: Quantum Variational Algorithms Are Swamped With Traps
• Estimating outcome probabilities of quantum circuits using quasiprobabilities
• Nearly optimal lattice simulation by product formulas
• The Clifford group, stabilizer states, and linear and quadratic operations over GF(2)
• Fast simulation of stabilizer circuits using a graph state representation
• Linear growth of quantum circuit complexity
• The Born Supremacy: Quantum Advantage and Training of an Ising Born Machine
• Efficient Discrete Approximations of Quantum Gates
• Models of quantum complexity growth
• Hadamard-free circuits expose the structure of the Clifford group
• Fast cosmic web simulations with generative adversarial networks
• On the Quantum versus Classical Learnability of Discrete Distributions
• A Random Unitary Circuit Model for Black Hole Evaporation
• Phase space simulation method for quantum computation with magic states on qubits
• Localization with random time-periodic quantum circuits
• Improved upper bounds on the stabilizer rank of magic states
• Learning quantum circuits of some $T$ gates
• The Learnability of Quantum States
• On the Hardness of PAC-learning Stabilizer States with Noise

Cited by in corpus (22)

• Stabilizer entropy dynamics after a quantum quench
• Learning efficient decoders for quasi-chaotic quantum scramblers
• Learning quantum states and unitaries of bounded gate complexity
• Stabilizer entropy in non-integrable quantum evolutions
• Exponentially tighter bounds on limitations of quantum error mitigation
• Improved Stabilizer Estimation via Bell Difference Sampling
• Spectral Properties Versus Magic Generation in $T$-doped Random Clifford Circuits
• Efficient learning of $t$-doped stabilizer states with single-copy measurements
• Random unitaries, Robustness, and Complexity of Entanglement
• Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates
• Simple Hamiltonian dynamics is a powerful quantum processing resource
• Anticoncentration and State Design of Doped Real Clifford Circuits and Tensor Networks
• On the average-case complexity of learning output distributions of quantum circuits
• Quantum Local Differential Privacy and Quantum Statistical Query Model
• Learning unitaries with quantum statistical queries
• Learning Quantum Processes with Quantum Statistical Queries
• PAC-learning of free-fermionic states is NP-hard
• Agnostic Process Tomography
• On the Hardness of Measuring Magic
• Anticoncentration in Clifford Circuits and Beyond: From Random Tensor Networks to Pseudo-Magic States
• Optimal quantum reservoir learning in proximity to universality
• Gottesman-Knill Limit on One-way Communication Complexity: Tracing the Quantum Advantage down to Magic Resources