Efficiently learn random quantum circuits using output states
Learning Random Quantum Circuits and the Emergence of Pseudorandomness
Data Structures and Algorithms
Summary
This paper presents a way to efficiently figure out how certain random quantum circuits work by looking only at their outputs when they start from a simple input. The authors show that for circuits that aren’t too complex, their method can learn the entire circuit quickly. They also explore how this relates to when quantum circuits appear truly random, called pseudorandomness, which is important for understanding quantum security and computation. A new mathematical tool is used to handle complex gates without slowing down the learning process.
What this means in practice
- •For quantum hardware engineers: Identify and verify unknown quantum circuit gates efficiently from their output states without full backward tracking.
- •For quantum cryptography developers: Clarify conditions under which quantum circuits achieve pseudorandomness, informing design of secure quantum protocols.
Authors
Srinivasan Arunachalam, Qizhao Huang, Makrand Sinha
Abstract
We give an efficient algorithm for learning $k$-dimensional brickwork random quantum circuits using only copies of the output state obtained by applying $U$ to the all-zero input. For a depth-$d$ circuit on $n$ sites with random $2\ell$-qubit gates, the algorithm learns the original circuit $U$ with high probability in $\text{poly}(n,2^{\ell d})$ time for every constant dimensional lattice. In particular, the algorithm is polynomial time as long as $\ell d = O(\log n)$. In one dimension, this reaches the natural boundary suggested by pseudorandomness: pseudorandom states require $\ell d=ω(\log n)$, and structured cryptographic constructions suggest that this scale may be achievable from above. In higher dimensions, it remains plausible that the same $\ell d=ω(\log n)$ scale remains the threshold for ancilla-free pseudorandomness, and our results help clarify the conditions under which pseudorandomness can arise in this setting. The main idea behind our algorithm is a local correlation criterion that identifies gates in the final layer without learning their entire backward light cones, avoiding a bottleneck in the previous approaches. A key technical ingredient is a Carbery-Wright type anticoncentration inequality for low-degree polynomials of Haar random unitaries whose small-ball exponent is independent of the matrix dimension. The dimension-independent exponent is crucial for handling gates of growing locality. This anticoncentration result may also be of independent interest.