Canonical text (the exact bytes fingerprinted)

TRUVACE RECORD VERSION
record: TRV-2026-1193
version: 1
kind: certified
reason: Certified into the record
timestamp: 2026-09-26T14:19:11.225482Z
status: published
lens: p_space
sector: science
headline: On the average-case complexity of learning output distributions of quantum circuits
dek: 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…
gain_title: (none)
problem_title: 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.
trace_subject: (none)
gain_reading: (none)
gain_evidence: (none)
problem_reading: 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.
problem_evidence: learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model | any learning algorithm requires super polynomially many queries to achieve a constant probability of success over the randomly drawn instance | any learning algorithm requires Ω(2n) queries to achieve a O(2−n) probability of success over the randomly drawn instance
quick_read: 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.
limitation: Results are proven in the statistical query model, which is an abstract model and does not cover all possible learning algorithms outside that model.
tag: Evidence-backed problem
key_points: Study analyzes learning output distributions of brickwork random quantum circuits on n qubits of depth d. | At super logarithmic depth d=omega(log(n)), any SQ learner needs super polynomially many queries for constant success probability over random instance. | At depth d=O(n), lower bound is Omega(2n) queries to achieve O(2-n) success probability. | At infinite depth, bound becomes 22Omega(n) queries for 2-2Omega(n) success probability. | Auxiliary result: output distribution is constantly far from any fixed distribution in total variation distance with probability 1-O(2-n).
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:
- peer_reviewed | Quantum | https://doi.org/10.22331/q-2025-10-13-1883 | 2025-10-13
prev: 0000000000000000000000000000000000000000000000000000000000000000

sha256

b7c3f729e0efc0e5e53569b0a65761e3ff78818e7ddffb83ea5428764e14d1d9

previous

0000000000000000000000000000000000000000000000000000000000000000