arXiv:2610.02100
On the pseudorandomness of simple quantum processes
Jesko Dujmovic, Jonas Haferkamp, Alexander Poremba
Abstract
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 on this longstanding conjecture. Our first result shows that statistical moment matching in the form of unitary designs does not generically lead to pseudorandomness---even for the simplest quantum processes: for every fixed $t$, we give an efficiently samplable family $\{ν_n\}_n$ of distributions on one- and two-qubit gates such that, after $T=O_t(n^2\log^2 n)$ independent steps, the resulting $n$-qubit ensemble is an approximate unitary $t$-design with negligible error $\exp(-Ω(\log^2 n))$, yet an efficient quantum algorithm distinguishes it from random using only $O_t(\log^2 n)$ queries. This refutes the unitary analog of the Hoory--Magen--Myers--Rackoff conjecture (ICALP '04) for permutations. Our second result is a stronger separation between unitary designs and pseudorandom unitaries at polynomially bounded moments; our counterexample, however, requires highly structured ensembles, in contrast with the simple local walks from before. This suggests caution when using unitary designs to model information scrambling in black-hole physics, as even maximally scrambled systems can exhibit structure which is accessible to efficient experiments. Motivated by these findings, we then propose new conjectures for how pseudorandomness can plausibly emerge within simple quantum processes, such as random quantum circuits.
AI Summary
The paper asks whether Haar moment matching implies computational pseudorandomness when unitaries arise from simple local dynamics. It gives two separations, distinguishing fixed-order local walks from structured ensembles matching polynomially many moments. For every fixed $t\geq4$, it constructs an i.i.d. walk on one- and nearest-neighbor two-qubit gates whose $T=O_t(n^2\log^2 n)$ steps form an approximate adaptive unitary $t$-design with error $\exp[-\Omega_t(\log^2 n)]$, yet admit an efficient distinguisher using $O_t(\log^2 n)$ parallel forward queries. This refutes the stated quantum HMMR conjecture. The walk combines local Clifford mixing with rare non-Clifford rotations. Its analysis separates rapidly decaying spectral modes from a constant-dimensional slow sector, controlling adaptive acceptance probabilities without an exponential dimension penalty. The distinguisher tests surviving Pauli stabilizers. A second construction achieves adaptive design error $2t(t-1)/2^n+\varepsilon$ in depth $\operatorname{poly}(n,t,\log(1/\varepsilon))$, for $1\leq t\leq2^{n/4-4}$, while allowing distinction in $\operatorname{poly}(n,t)$ time with $O(nt)$ forward queries. It plants a learnable, limited-independence phase state on one input and randomizes its orthogonal complement. Collision-based positive-operator bounds establish the design property; derivative measurements recover the phase seed. The second ensemble can also have near-maximal expected Choi min-entropy while remaining distinguishable. However, it uses structured controlled circuits and a separate phase circuit, not an i.i.d. local-gate walk. Neither separation addresses local walks matching $t=\Theta(n)$ moments; pseudorandomness in that regime is proposed as a conjecture, not proved.
The model was used to assist with some parts of the technical write-up, for devising figures and for the literature review.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.