Learning Random Quantum Circuits and the Emergence of Pseudorandomness
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ℓ-qubit gates, the algorithm learns the original circuit U with high probability in poly(n,2ℓ d) time for every constant dimensional lattice. In particular, the algorithm is polynomial time as long as ℓ d = O(log n). In one dimension, this reaches the natural boundary suggested by pseudorandomness: pseudorandom states require ℓ 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 ℓ 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.
Related
- Fermionic Porter-Thomas statistics and their emergence in random matchgate circuits
- Random quantum circuits, chaos and quantum thermalization
- Rare-History Transitions in Temporally Random Integrable Quantum Circuits
- One Gate at a Time: Complexity Growth in Random Quantum Circuits
- The quantum Mpemba effect in symmetric random Clifford circuits
BibTeX
@misc{arunachalam2026learning,
title = {{Learning Random Quantum Circuits and the Emergence of Pseudorandomness}},
author = {Srinivasan Arunachalam and Qizhao Huang and Makrand Sinha},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.39821},
eprint = {2609.39821},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.39821},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Learning Random Quantum Circuits and the Emergence of Pseudorandomness
AU - Srinivasan Arunachalam
AU - Qizhao Huang
AU - Makrand Sinha
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.39821
UR - https://arxiv.org/abs/2609.39821
AB - 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ℓ-qubit gates, the algorithm learns the original circuit U with high probability in poly(n,2^ℓ d) time for every constant dimensional lattice. In particular, the algorithm is polynomial time as long as ℓ d = O(log n). In one dimension, this reaches the natural boundary suggested by pseudorandomness: pseudorandom states require ℓ 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 ℓ 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.
ER -