TRV-2026-1193Version 2 · Revised

Saved · see the current record

Why this version exists

Editorial pass: sharper headline; filed as context: no real AI gain or problem (gain absent, problem absent).

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: 2
kind: revised
reason: Editorial pass: sharper headline; filed as context: no real AI gain or problem (gain absent, problem absent).
timestamp: 2026-11-04T09:55:41.417766Z
status: published
lens: general
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: Context
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: b7c3f729e0efc0e5e53569b0a65761e3ff78818e7ddffb83ea5428764e14d1d9
SHA-256 hash
e475f15eb1fd635a90ef85392234c262c2cf3f821edbae8996bc3d98085440eb
Previous version’s hash
b7c3f729e0efc0e5e53569b0a65761e3ff78818e7ddffb83ea5428764e14d1d9
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.