Source-linked AI summary
Learning Random Quantum Circuits and the Emergence of Pseudorandomness
Srinivasan Arunachalam, Qizhao Huang, Makrand Sinha
TL;DR
Learning random brickwork circuits from output-state copies is difficult when state access forces reliance on large lightcones. The paper uses two-site correlations and dimension-free Haar-unitary anticoncentration to recover circuits in polynomial time when ℓd=O(log n).
Problem
The paper asks whether fixed-dimensional brickwork random circuits can be learned in polynomial time from output-state copies when ℓd=O(log n).
Source: §1 · p. 2Method
The learner identifies gates layer by layer using correlations between two output sites, without reconstructing their full backward lightcones.
Source: §1.2 · p. 6, §1.3 · p. 6Results
With high probability, the algorithm exactly recovers the circuit from state copies and runs in polynomial time when ℓd=O(log n).
Source: §1.1 · p. 3Takeaways & Limitations
The result extends efficient exact learning to larger dimension and gate locality at the ℓd=O(log n) scale using only state access.
Source: §1.2 · p. 6The stated anticoncentration step fixes all but at most 2kd gates and takes probability over the remaining independent Haar-random unitaries.
Source: §5.1.2 · pp. 26–27
Abstract
from arXiv · showhide
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.
1 Introduction
The introduction frames learning and pseudorandomness as recovering versus concealing structure, then asks how locality and depth shape these questions for brickwork circuits.
1 Introduction
- In one dimension, the paper places the learning question near the pseudorandomness boundary, while higher-dimensional ancilla-free thresholds remain open.For gates of locality ℓ, the combined scale ℓd is used to rule out pseudorandom states when ℓd=O(log n).Source: §1 · p. 2
1.1 Main results
- With state copies, the algorithm exactly recovers the original circuit with high probability and runs in polynomial time when ℓd=O(log n).The stated setup uses depth-d, k-dimensional brickwork circuits with gates sampled from a random public gateset.Source: §1.1 · p. 3
- The paper establishes a dimension-free small-ball exponent for low-degree Haar-unitary polynomials, addressing a bottleneck for growing gate locality.The authors identify dimension independence as crucial because the gate dimension can become large.Source: §1.1 · p. 4
1.2 Prior Work and Discussion
- Unlike MPS learners that may return a different preparation, this work combines polynomial time at ℓd=O(log n), state-copy access, and exact recovery of the original circuit.Existing MPS methods can yield O(n)-depth implementations for O(1)-local one-dimensional circuits.Source: §1.2 · p. 6
1.3 Overview of the Learning Algorithm
- Removing a candidate gate makes two chosen output sites separable; with the gate present, typical circuits yield correlation at least 2^-O(ℓd), enabling gate identification by testing inverse candidates.The learner estimates the two-site reduced state to distinguish the correct inverse from incorrect candidates.Source: §1.3 · p. 7
1.4 Overview of the Anticoncentration Proof
- The anticoncentration proof reduces Haar-unitary polynomials to Laurent polynomials under the Weyl measure, then uses interpolation and univariate extremal bounds related to Remez inequalities.The Weyl measure captures Haar-unitary eigenvalues in a uniformly random order.Source: §1.4 · p. 8
2 LLM Methodology
The authors report LLM-based tool use transparently, distinguishing occasional research support from work they attribute to themselves. Tools helped locate mathematical techniques for the anticoncentration proof, while the authors developed and verified the resulting arguments.
Writing and exposition
- The authors followed Simons Institute guidance for reporting tool use but referred to tools generically to avoid implying endorsement.They state that the paper was written by the authors and that mathematical arguments and citations were independently verified.Source: §2 · pp. 9–10
Coming up with the approach/Proof development
- The authors attribute the research questions and most key ideas to themselves, while describing the LLM’s contribution to the anticoncentration proof as pointing them toward relevant mathematical ideas and techniques.They marked approach and proof development “No*” because the authors adapted the techniques and developed the proofs themselves.Source: §2 · p. 9
- An LLM suggestion to consult the Weyl Integration formula led the authors to develop interpolation-based proofs with a dimension-free small-ball exponent.The authors say an earlier approach had a polylogarithmic dimension dependence.Source: §2 · p. 10
Other supporting tasks
- LLM-based tools were used occasionally for literature searches, suggestions, intermediate-assumption testing, tables or figures, LaTeX assistance, and proofreading.The authors say the tools did not contribute to identifying or correcting consequential errors.Source: §2 · p. 10
3 Preliminaries
The preliminaries establish notation for vectors, states, norms, and unitary groups, then introduce the Weyl measure and its use in computing Haar averages of class functions.
3.1 Notation
- The notation uses [k] for {1, …, k}, bold letters for vectors, density matrices and reduced states for quantum states, and indicator functions for events.The paper also uses L∞ and L2 norms with respect to the measure understood from context.Source: §3.1 · p. 10
- U(m) denotes the m × m unitary group, Haar(m) its normalized Haar measure, and U(1)^m the product of uniform measures on the complex unit circle.U(1) is called the torus.Source: §3.1 · p. 10
3.2 Weyl Measure and Weyl Integration
- The Weyl measure describes the eigenvalues of a Haar-random unitary in uniformly random order and is a probability measure on U(1)^m.The Weyl integration formula computes the Haar average of a bounded measurable class function by averaging its diagonal-unitary values under this measure.Source: §3.2 · pp. 10–11
4 Carbery-Wright Inequality over the Unitary Group
The section proves a Carbery-Wright-type anticoncentration inequality for polynomials on the unitary group by reducing it to a polytorus inequality and then to a univariate extremal bound.
4 Carbery-Wright Inequality over the Unitary Group
- The section establishes a Carbery-Wright-type anticoncentration inequality for complex polynomials on U(m) with bounded total degree.The proof is organized as reductions through the polytorus and a univariate extremal inequality.Source: §4 · p. 11
4.1 Reduction to the Polytorus
- A Haar-unitary polynomial is reduced to a Laurent polynomial on the polytorus by diagonalizing around a point where its modulus is maximal.The reduction uses the Weyl integration formula and applies the polytorus bound before averaging over the remaining unitary.Source: §4.1 · p. 13
4.2 Reduction to Univariate Extremal Inequalities
- An interpolation parameter turns the polytorus small-value event into a measure bound for univariate exponential functions with frequencies controlled by the Laurent degree.The resulting functions attain their maximum at zero, allowing the univariate extremal inequality to bound the small-value set.Source: §4.2 · p. 14
4.3 Proof of the Univariate Extremal Inequality
- The univariate bound is proved by adapting a Nazarov-Sodin-Volberg analytic inequality to exponential sums and transferring a large-measure set to a suitable interval.The proof normalizes the function, controls it on the complex disk, and uses a change of variables to place the set in the interval required by the analytic inequality.Source: §4.3 · pp. 16–17
5 Learning Random Circuits with State Access
This section presents an algorithm for exactly recovering a random brickwork circuit from copies of its output state by identifying gates through local correlations. It constructs boundary-gate assignments and uses multigate anticoncentration to show that the true gate label is the unique minimizer.
5 Learning Random Circuits with State Access
- The proof uses dimension-independent anticoncentration for a constant-degree correlation polynomial, essential for handling gates of growing locality.Its small-ball exponent depends on polynomial degree, not gate dimension.Source: §5 · p. 21
- Applying each candidate gate’s inverse makes the correlation zero for the correct gate, while incorrect guesses retain correlation at least 2^-O(ℓd), detectable by tomography on BD.The required precision is roughly 2^-O(kℓd); learning one gate takes poly(n, δ^-1)2^O(kℓd) time.Source: §5 · p. 21
5.1.1 Lower Bound on L∞Norm of Two-point Correlation Polynomial
- For an incorrect candidate, the correlation-gap proof constructs boundary-gate assignments yielding constant two-point correlation, even when all gates outside the boundary are fixed arbitrarily.The boundary consists of O(d) gates along two paths from a common gate.Source: §5.1.1 · p. 23, §5.1 · p. 23
- A SWAP-based boundary-gate assignment leaves a residual SWAP after applying an incorrect candidate inverse, while the two one-site marginals remain maximally mixed.The construction assigns gates affecting either routed half within the boundary, so it does not depend on fixed gates outside that boundary.Source: §5.1.1 · p. 24
5.1.2 Anti-concentration for the Two-point Correlation Function
- Multigate anticoncentration yields a high-probability lower bound on the two-point correlation for an incorrect candidate; the polynomial has degree at most 16 in each free unitary.The free unitaries are independent Haar-random, and the degree bound covers the candidate gate appearing both in the circuit and its inverse.Source: §5.1.2 · p. 26
5.1.3 Putting Everything Together
- With probability at least 1 − δ over N, the true label is the unique minimizer with probability at least 1 − δ/2 over the random label assignment.The true candidate has correlation zero deterministically; the proof applies a union bound over incorrect labels and gate locations.Source: §5.1.3 · pp. 27–28