Skip to content

Learning Random Quantum Circuits and the Emergence of Pseudorandomness

Sep 2026 · arXiv.org · Vol abs/2609.39821 · 0 citations · 41 references
Computer Science Physics

TL;DR

The main idea behind the 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.

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=\omega(\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=\omega(\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.

View source

Similar papers

Preprint Sep 2026

On the geometry and typicality of quantum magic

We prove that, for an $n$-qubit system of dimension $d=2^n$, every state satisfying $\operatorname{Tr}(\rho^2)\le 1/(d-a_\ast)$, with $a_\ast=0.458327\cdots$, lies inside the stabilizer polytope and is therefore magic-free. Combining this result with general geometric properties of high-dimensional polytopes, we establ...

Zhen-Huan Liu, Zi-Wen Liu · 2 citations
Preprint Sep 2026

Parallel classical simulation of noisy shallow circuits: no quantum advantage in 1D

We consider quantum circuits consisting of $d$ layers of nearest-neighbor two-qubit gates acting on $n$ qubits arranged on a line, where every qubit is independently depolarized with a constant probability before each layer. We describe a randomized parallel algorithm which samples from the output distribution of any s...

Robert Koenig, Marco Tomamichel · 1 citation
Preprint Aug 2026

(Almost) quadruply optimal unitary designs in 1D

We construct $n$-qubit approximate unitary $k$-designs in 1D systems, achieving circuit depth $O(\log(n/\varepsilon) + k\log k)$ with relative error $\varepsilon$ and requiring $O(nk\log k)$ magic gates. This matches existing lower bounds $\Omega(\log(n/\varepsilon) + k)$ for circuit depth, and $\widetilde{\Omega}(nk)$...

Guoding Liu, J. Helsen · 3 citations · ⚡1
Preprint Oct 2026

On the pseudorandomness of simple quantum processes

Can simple processes appear highly complex? Gowers (Comb. Prob. Comp.'96) conjectured that repeatedly composing local random reversible operations can yield global permutations that are indistinguishable from random. In this work, we study the unitary quantum analog of this question, in an attempt to make new progress...

Jesko Dujmovic, Jonas Haferkamp, Alexander Poremba · 0 citations
Preprint Aug 2026

Good Stabilizer Codes from Shallow Clifford Circuits with Random Matchings

Encoding quantum information with low circuit overhead is a fundamental challenge in fault-tolerant quantum computation. Random circuits provide a natural mechanism for rapidly spreading logical information through simple gates applied in parallel. Brown and Fawzi showed that random Clifford circuits on two-qubit Cliff...

E. Anand, Elia Gorokhovsky, Jennifer Hritz et al. · 1 citation

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.