arXiv:2609.39821
Learning Random Quantum Circuits and the Emergence of Pseudorandomness
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.
AI Summary
The paper asks when local random quantum circuits can be reconstructed from copies of a single output state, and how learnability constrains pseudorandomness. It considers depth-$d$ brickwork circuits on $n$ sites of a fixed-dimensional lattice, with $\ell$ qubits per site and two-site gates. The learning model uses a public set of $M=64n^2d^2/\delta^2$ independently Haar-sampled, finite-precision gates; unknown circuit locations receive uniformly random labels from this set. For fixed lattice dimension $k$ and $d\leq0.01n^{1/k}$, the algorithm exactly recovers the gate labels from copies of $U|0\rangle^{\otimes n\ell}$ in sample and time complexity $\operatorname{poly}_k(n,d,\delta^{-1})2^{O_k(\ell d)}$, with high probability over the gateset, circuit and measurements. This is polynomial when $\ell d=O(\log n)$. It peels off layers by testing candidate inverse gates: the correct inverse eliminates correlations between selected output sites, while incorrect candidates leave a detectable correlation gap. The analysis constructs Bell-pair routing witnesses involving only $O_k(d)$ gates, avoiding reconstruction of full lightcones. A technical ingredient is a Haar-unitary small-ball bound for degree-$s$ polynomials: $\Pr[|P(U)|\leq\varepsilon\|P\|_\infty]\leq64m^2\varepsilon^{1/(24\pi s)}$. Its exponent is independent of matrix dimension; the proof combines Weyl integration, interpolation and a univariate Remez inequality. Exact recovery is restricted to the specified discrete public-gateset model, rather than unrestricted continuous Haar gates. The paper does not establish pseudorandomness above the learning regime. The scale $\ell d=\omega(\log n)$ is necessary for one-dimensional pseudorandom states; whether it marks an ancilla-free threshold in higher dimensions remains open.
The main idea for proving the improved anticoncentration bound was provided by an LLM.
Central claim may not hold: The abstract claims recovery of the original Haar-random circuit without stating the essential known finite-codebook assumption; without that side information, exact original-circuit recovery is not identifiable even at depth one. The abstract omits the theorem's restriction d ≤ 0.01 n^(1/k), although this restriction is asymptotically automatic in the highlighted ℓd = O(log n) regime.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.