TRV-2026-1193Version 1 · Published

Saved · see the current record

Why this version exists

Certified into the record

The exact text we saved

This is the version exactly as it was saved, character for character. The SHA-256 hash below is a 64-character code worked out from that text. Run the same text through SHA-256 and you get the same code; change a single letter and the code comes out completely different. Each version also stores the previous version’s hash, which chains them together so no version can be swapped out quietly.

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
SHA-256 hash
b7c3f729e0efc0e5e53569b0a65761e3ff78818e7ddffb83ea5428764e14d1d9
Previous version’s hash
0000000000000000000000000000000000000000000000000000000000000000
Check this record hasn’t been altered
How to check it yourself, without trusting this page

Download any version from /api/record/TRV-2026-1193 and hash its canonical field yourself, for example with shasum -a 256. You should get its content_hash. Each version’s text also ends with prev:and the hash of the version before it (version 1 points to 64 zeros). If anyone had changed a single character of any version after it was saved, those hashes wouldn’t line up.