arXiv:2610.02135
Random Quantum Circuits Beyond Moment Matching
Shih-Han Hung
Abstract
Random quantum circuits aim to efficiently reproduce the statistical properties of ideal random quantum evolution. One approach is to construct approximate unitary designs, which match the moments of Haar-random unitaries up to a prescribed order with controlled error. We establish quantitative guarantees for how accurately these designs reproduce the distribution of each output probability. We show that, for every strong $\varepsilon$-approximate unitary $k$-design on $n$ qubits, the distribution of each output probability is within $O(k^{-1/2}(1+k/2^n)^{-1/2}+\varepsilon)$ in Kolmogorov distance of the Porter-Thomas distribution, a beta distribution with parameters $1$ and $2^n-1$. This bound is optimal up to constant factors, implying that a substantially better uniform bound requires additional structure. We then show that a mild form of local invariance suffices. We prove that any such design that is invariant under unitary translations acting on a single qubit approximates Porter-Thomas to total variation distance $O(k^{-1/2}+\varepsilon)$. Every strong $\varepsilon$-approximate unitary $k$-design invariant on $\log k+O(1)$ qubits achieves error $2^{-Ω(k)}+O(\varepsilon)$ in Kolmogorov distance and $2^{-Ω(k)}+O(\varepsilon\log(2/\varepsilon))$ in total variation distance. These results identify the distributional accuracy guaranteed by moment matching and the structure that improves it. As an application, we show that the Shannon entropy of the output distribution of a strong $\varepsilon$-approximate $k$-design is concentrated around its Haar value $n-Θ(1)$: its mean differs from the Haar mean by $O(k^{-1/4}+\varepsilon^{1/2})$ and its standard deviation is $O(2^{-n/2}+k^{-1/8}+\varepsilon^{1/4})$. Consequently, a trusted device sampling such circuits generates $n-O(1)$ bits of entropy per sample, which makes them useful for random number generation.
AI Summary
The paper asks what unitary-design moment matching implies about the distribution of a fixed output probability $|\langle x|U|y\rangle|^2$, beyond anti-concentration. It assumes **strong relative-error** $\varepsilon$-approximate $(k,k)$-designs, a stronger condition than standard or additive-error designs. For dimension $N=2^n$, every such design has Kolmogorov distance $O(k^{-1/2}(1+k/N)^{-1/2}+\varepsilon)$ from the Haar marginal $\mathrm{Beta}(1,N-1)$, called Porter–Thomas here. A matching worst-case lower bound establishes optimality up to constants. Local unitary invariance improves the guarantees: invariance on one qubit gives total variation error $O(k^{-1/2}+\varepsilon)$. Invariance on $m$ qubits with $2^m\geq2\pi k$ and $N>2^{m+1}$ gives Kolmogorov error $2^{-\Omega(k)}+O(\varepsilon)$ and total variation error $2^{-\Omega(k)}+O(\varepsilon\log(2/\varepsilon))$. The generic bounds use polynomial majorants and minorants, Gaussian quadrature, and Christoffel-function estimates; the lower bound embeds extremal scalar moment-matching measures into unitary ensembles. Local invariance supplies an independent beta-distributed multiplicative smoothing factor, analyzed through density estimates or Fourier methods in logarithmic coordinates. An application bounds the output Shannon entropy’s mean error from its Haar value by $O(k^{-1/4}+\varepsilon^{1/2})$ and its standard deviation by $O(2^{-n/2}+k^{-1/8}+\varepsilon^{1/4})$. Limitations include single-probability rather than general joint-distribution guarantees, no exponential-rate result for plain brickwork circuits, and no adversarial randomness certification. Discrete gate approximations preserve Kolmogorov but not continuous-law total variation guarantees; randomness extraction assumes trusted execution.
The technical contributions were checked and the manuscript proofread using Claude~Fable~5, Claude~Fable~5.1, and ChatGPT~5.6-Sol, and the paper was revised based on the issues found by these tools.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 79 pages. v2: added results on one-qubit local invariance and entropy concentration