30/100

Emerging evidence

Published recordScienceGeneral

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
  1. Quantumdoi:10.22331/q-2025-10-13-1883
    Peer-reviewed2025-10-13

Cite this record

v2

Truvace 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 versions

Every change made to this record since it was first published, and why.

  1. Revisedv2e475f15eb1fd…

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

  2. Publishedv1b7c3f729e0ef…

    Certified into the record

Check this record hasn’t been altered

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.