Truace
Subscribe

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

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=ω(log⁡(n)) , any learning algorithm requires super polynomially many queries to achieve a constant probability of…

By the Truvace desk2 min read1 sourcePeer-reviewedTRV-2026-1193· cite & verify
On the average-case complexity of learning output distributions of quantum circuits
Bqcfig3 by P. Drmota, D. P. Nadlinger, D. Main, B. C. Nichol, E. M. Ainley, D. Leichtle, A. Mantri, E. Kashefi, and R. Srinivas et al.. CC BY 4.0 · https://creativecommons.org/licenses/by/4.0

In brief

By the publication date of 2025-10-13, the authors had proven that learning the output distributions of brickwork random quantum circuits on n qubits is average-case hard in the statistical query model, establishing super polynomial and exponential query lower bounds that grow with circuit depth d.

This matters because it sets a fundamental limit on generic learning algorithms attempting to model random quantum circuit outputs, relevant to verification of quantum advantage and quantum machine learning, while remaining uncertain how the bounds extend beyond the statistical query model to other algorithmic approaches.

Main points

  1. Study analyzes learning output distributions of brickwork random quantum circuits on n qubits of depth d.
  2. At super logarithmic depth d=omega(log(n)), any SQ learner needs super polynomially many queries for constant success probability over random instance.
  3. At depth d=O(n), lower bound is Omega(2n) queries to achieve O(2-n) success probability.
  4. At infinite depth, bound becomes 22Omega(n) queries for 2-2Omega(n) success probability.
  5. Auxiliary result: output distribution is constantly far from any fixed distribution in total variation distance with probability 1-O(2-n).

The problem

Learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model, requiring super polynomially many queries at super logarithmic depth to achieve constant success probability.

The rundown

The authors work in the statistical query model, described as widely used as an abstract computational model for most generic learning algorithms, and prove average-case hardness for brickwork random circuits on n qubits.

Three depth regimes are analyzed: super logarithmic d=omega(log(n)) leading to super polynomial query lower bound, linear d=O(n) leading to Omega(2n) queries for O(2-n) success, and infinite depth leading to 22Omega(n) queries for 2-2Omega(n) success.

As an auxiliary result, they show the output distribution is constantly far from any fixed distribution in total variation distance with probability 1-O(2-n), noted as confirming a variant of a conjecture by Aaronson and Chen.

Sources

  1. Peer-reviewedQuantum2025-10-13

The debate