Emerging evidence
Published recordScienceGeneral
More
On the average-case complexity of learning output distributions of quantum circuits
- Truvace record
- TRV-2026-1193raw data (JSON)
- Version
- v2Revised
- First published
- Evidence type
- Commentary, opinion, or narrative review
- Sources
- 1 sourcePeer-reviewed
- sha256
- e475f15eb1fd…check it
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…
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.
What this doesn’t fix
Results are proven in the statistical query model, which is an abstract model and does not cover all possible learning algorithms outside that model.
Sources
1 on file- Quantumdoi:10.22331/q-2025-10-13-1883
Cite this record
v2Truvace Impact Record TRV-2026-1193, v2: “On the average-case complexity of learning output distributions of quantum circuits.” Truvace, 2026-11-04. /record/TRV-2026-1193 (accessed on the day you copy it). sha256 e475f15eb1fd635a…
Change history
2 versionsEvery change made to this record since it was first published, and why.
Editorial pass: sharper headline; filed as context: no real AI gain or problem (gain absent, problem absent).
Certified into the record
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.
ace