aceOn 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…
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.
Results are proven in the statistical query model, which is an abstract model and does not cover all possible learning algorithms outside that model.
Evidence
- Peer-reviewedQuantum2025-10-13
How should this claim be treated?
Truvace Impact Record TRV-2026-1193, v1: “On the average-case complexity of learning output distributions of quantum circuits.” Truvace, 2026-09-26. /record/TRV-2026-1193 (accessed at citation time). sha256 b7c3f729e0efc0e5…
Calibration history
Every change to this record since certification, in the open. None yet — the reading has held since it entered the record.
Certified into the record
How to verify without trusting this page
Fetch the canonical text of any version from /api/record/TRV-2026-1193 and hash it yourself — for example shasum -a 256 on the saved canonical field. The result must equal content_hash, and each version’s text ends with prev:followed by the prior version’s hash (version 1 chains to 64 zeros). If a single character of any version had been altered since certification, the chain would not reproduce.