On the pseudorandomness of simple quantum processes
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=Ot(n2log2 n) independent steps, the resulting n-qubit ensemble is an approximate unitary t-design with negligible error exp(−Ω(log2 n)), yet an efficient quantum algorithm distinguishes it from random using only Ot(log2 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.
Related
- No linear stretching of single-copy quantum pseudorandomness
- Learning Random Quantum Circuits and the Emergence of Pseudorandomness
- Nonequilibrium Dynamics of Simple Exclusion Processes Across Dimensions
- Time-temperature superposition from multi-temperature chirp rheometry of thermorheologically simple materials via physics-informed Gaussian processes
- Spectral and transmission properties of multiple correlated quantum dots made simple
BibTeX
@misc{dujmovic2026pseudorandomness,
title = {{On the pseudorandomness of simple quantum processes}},
author = {Jesko Dujmovic and Jonas Haferkamp and Alexander Poremba},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02100},
eprint = {2610.02100},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02100},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On the pseudorandomness of simple quantum processes
AU - Jesko Dujmovic
AU - Jonas Haferkamp
AU - Alexander Poremba
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.02100
UR - https://arxiv.org/abs/2610.02100
AB - 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^2log^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.
ER -