Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.02100

On the pseudorandomness of simple quantum processes

Jesko Dujmovic, Jonas Haferkamp, Alexander Poremba

quant-phcs.CRSubmitted Oct 1, 2026• Announced Oct 2, 2026• 0 citations
arXivHTMLPDF

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.

Little sign of AI-generated textAI use disclosed
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.

Related papers

Efficient unitary designs and pseudorandom unitaries from permutations

Chi-Fang Chen, Adam Bouland, Fernando G. S. L. Brandão +3 more

In this work we give an efficient construction of unitary $k$-designs using $\tilde{O}(k\cdot poly(n))$ quantum gates, as well as an efficient construction of a parallel-secure pseudorandom unitary (PRU). Both results are obtained by giving an efficient quantum algorithm that lifts random permutations over $S(N)$ to random unitaries over $U(N)$ for $N=2^n$. In particular, we show that products of exponentiated sums of $S(N)$ permutations with random phases approximately match the first $2^{Ω(n)}$ moments of the Haar measure. By substituting either $\tilde{O}(k)$-wise independent permutations, or quantum-secure pseudorandom permutations (PRPs) in place of the random permutations, we obtain the above results. The heart of our proof is a conceptual connection between the large dimension (large-$N$) expansion in random matrix theory and the polynomial method, which allows us to prove query lower bounds at finite-$N$ by interpolating from the much simpler large-$N$ limit. The key technical step is to exhibit an orthonormal basis for irreducible representations of the partition algebra that has a low-degree large-$N$ expansion. This allows us to show that the distinguishing probability is a low-degree rational polynomial of the dimension $N$.

arXiv:2404.16751•Apr 25, 2024•38 citations

Random unitaries from Hamiltonian dynamics

Cui, Laura, Thomas Schuster, Mao, Liang +2 more

The nature of randomness and complexity growth in systems governed by unitary dynamics is a fundamental question in quantum many-body physics. This problem has motivated the study of models such as local random circuits and their convergence to Haar-random unitaries in the long-time limit. However, these models do not correspond to any family of physical time-independent Hamiltonians. In this work, we address this gap by studying the indistinguishability of time-independent Hamiltonian dynamics from truly random unitaries. On one hand, we establish a no-go result showing that for any ensemble of constant-local Hamiltonians and any evolution times, the resulting time-evolution unitary can be efficiently distinguished from Haar-random and fails to form a $2$-design or a pseudorandom unitary (PRU). On the other hand, we prove that this limitation can be overcome by increasing the locality slightly: there exist ensembles of random polylog-local Hamiltonians in one-dimension such that under constant evolution time, the resulting time-evolution unitary is indistinguishable from Haar-random, i.e. it forms both a unitary $k$-design and a PRU. Moreover, these Hamiltonians can be efficiently simulated under standard cryptographic assumptions.

arXiv:2510.08434•Oct 9, 2025•27 citations

Strong unitary designs in optimal depth and space

Teodor Parella-Dilmé, Júlia Barberà-Rodríguez, Salvatore F. E. Oliviero +1 more

Unitary designs provide finite-moment approximations to Haar-random unitaries, with wide-ranging applications across physics and quantum information, from scrambling and black-hole dynamics to foundational primitives in quantum algorithms. Strong unitary designs capture a more demanding operational notion of approximation, requiring indistinguishability from Haar randomness even for quantum algorithms that may access a unitary not only in the forward direction, but also through its inverse, transpose, and complex conjugate. Motivated by the physical requirement that scrambling arise within the system itself, Schuster, Ma, Lombardi, Brandão, and Huang (arXiv:2509.26310) left open whether strong unitary designs can be generated in logarithmic depth using only the system qubits. For every fixed design order $k$ and measurable-error tolerance, we construct strong approximate unitary $k$-designs in optimal $Θ(\log n)$ all-to-all circuit depth using only the $n$ original system qubits. Our new ingredient is a logarithmic-depth Pauli-mixing bound for the perfect-matching ensemble, whose layers pair the qubits uniformly at random and apply independent random two-qubit gates. This bound controls the mixed forward-reverse two-query case, which we combine with existing design and gluing results to obtain strong unitary designs of arbitrary fixed order.

quant-pharXiv:2608.13491•Aug 14, 2026•5 citations

Distinctness threshold for pseudorandom unitaries

Asad Raza, Jens Eisert, Bill Fefferman

Pseudorandomness is increasingly recognized as a key property of ensembles in quantum information theory, statistical mechanics, and quantum many-body physics. Yet it appears in two conceptually different forms: statistical pseudorandomness, embodied by unitary designs, and computational pseudorandomness captured by pseudorandom unitaries (PRUs). The relationship between these two forms of pseudorandomness remains surprisingly poorly understood. Existing PRU constructions reveal this interplay where a statistically randomizing ingredient, a unitary design, is combined with classical cryptographic primitives to produce computational pseudorandomness. We show that statistical pseudorandomness is not necessary for computationally pseudorandom unitaries. We do this by replacing the unitary $2$-design layer in the existing constructions with ensembles that are not even state $1$-designs, yet are sufficiently {\em distinct}, a property we identify to be necessary for any PRU. This yields new non-adaptively secure PRU ensembles whose computational pseudorandomness is obtained without an underlying statistically pseudorandom quantum ensemble, such as a $2$-design. We characterize distinctness via an entangled analogue of anticoncentration and use it to show that distinctness already captures constraints on coherence and imaginarity of PRUs, while identifying broad classes of inputs for which the latter obstruction disappears, enabling real-valued PRUs even for certain (maximally) entangled states. As an application, we use lack of distinctness to constrain the conjectured pseudorandomness of the random phase-Hadamard ensemble to form a PRU.

quant-pharXiv:2609.03065•Sep 4, 2026•2 citations

Efficient Unitary Designs from Random Sums and Permutations

Chi-Fang Chen, Jordan Docter, Michelle Xu +3 more

A unitary k-design is an ensemble of unitaries that matches the first$k$moments of the Haar measure. In this work, we provide two efficient constructions of k-designs on n-qubits using new random matrix theory techniques. Our first construction is based on exponentiating sums of random i.i.d. Hermitian matrices and uses O(k2n2)-many gates. In the spirit of central limit theorems, we show that this random sum approximates the Gaussian Unitary Ensemble (GUE). We then show that the product of just two exponentiated GUE matrices is already approximately Haar random. Our second construction is based on products of exponentiated sums of random permutations and uses Õ($k$poly ($n$)) many gates. The$k$dependence is optimal (up to polylogarithmic factors) and is inherited from the efficiency of existing k-wise independent permutations. Furthermore, replacing random permutations with quantum-secure pseudorandom permutations (PRPs), we also obtain a pseudorandom unitary (PRU) ensemble that is secure under nonadaptive queries. A central feature of both proofs is a new connection between the polynomial method in quantum query complexity and the large-dimension ($N$) expansion in random matrix theory. In particular, the first construction uses the polynomial method to control high moments of certain random matrix ensembles without requiring delicate Weingarten calculations. In doing so, we define and solve a moment problem on the unit circle, asking whether a finite number of equally weighted points can reproduce a given set of moments. In our second construction, the key step is to exhibit an orthonormal basis for irreducible representations of the partition algebra that has a low-degree large-$N$expansion. This allows us to show that the distinguishing probability is a low-degree rational polynomial of the dimension$N$.

Annual Symposium on Foundations of Computer Science•Oct 27, 2024•19 citations

Efficient Unitary T-designs from Random Sums

Chi-Fang Chen, Jordan Docter, Michelle Xu +2 more

Unitary $T$-designs play an important role in quantum information, with diverse applications in quantum algorithms, benchmarking, tomography, and communication. Until now, the most efficient construction of unitary $T$-designs for $n$-qudit systems has been via random local quantum circuits, which have been shown to converge to approximate $T$-designs in the diamond norm using $O(T^{5+o(1)} n^2)$ quantum gates. In this work, we provide a new construction of $T$-designs via random matrix theory using $\tilde{O}(T^2 n^2)$ quantum gates. Our construction leverages two key ideas. First, in the spirit of central limit theorems, we approximate the Gaussian Unitary Ensemble (GUE) by an i.i.d. sum of random Hermitian matrices. Second, we show that the product of just two exponentiated GUE matrices is already approximately Haar random. Thus, multiplying two exponentiated sums over rather simple random matrices yields a unitary $T$-design, via Hamiltonian simulation. A central feature of our proof is a new connection between the polynomial method in quantum query complexity and the large-dimension ($N$) expansion in random matrix theory. In particular, we show that the polynomial method provides exponentially improved bounds on the high moments of certain random matrix ensembles, without requiring intricate Weingarten calculations. In doing so, we define and solve a new type of moment problem on the unit circle, asking whether a finite number of equally weighted points, corresponding to eigenvalues of unitary matrices, can reproduce a given set of moments.

arXiv:2402.09335•Feb 14, 2024•22 citations
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 ttt, we give an efficiently samplable family {νn}n\{ν_n\}_n{νn​}n​ of distributions on one- and two-qubit gates such that, after T=Ot(n2log⁡2n)T=O_t(n^2\log^2 n)T=Ot​(n2log2n) independent steps, the resulting nnn-qubit ensemble is an approximate unitary ttt-design with negligible error exp⁡(−Ω(log⁡2n))\exp(-Ω(\log^2 n))exp(−Ω(log2n)), yet an efficient quantum algorithm distinguishes it from random using only Ot(log⁡2n)O_t(\log^2 n)Ot​(log2n) 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.
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≥4t\geq4t≥4, it constructs an i.i.d. walk on one- and nearest-neighbor two-qubit gates whose T=Ot(n2log⁡2n)T=O_t(n^2\log^2 n)T=Ot​(n2log2n) steps form an approximate adaptive unitary ttt-design with error exp⁡[−Ωt(log⁡2n)]\exp[-\Omega_t(\log^2 n)]exp[−Ωt​(log2n)], yet admit an efficient distinguisher using Ot(log⁡2n)O_t(\log^2 n)Ot​(log2n) 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)/2n+ε2t(t-1)/2^n+\varepsilon2t(t−1)/2n+ε in depth poly⁡(n,t,log⁡(1/ε))\operatorname{poly}(n,t,\log(1/\varepsilon))poly(n,t,log(1/ε)), for 1≤t≤2n/4−41\leq t\leq2^{n/4-4}1≤t≤2n/4−4, while allowing distinction in poly⁡(n,t)\operatorname{poly}(n,t)poly(n,t) time with O(nt)O(nt)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=Θ(n)t=\Theta(n)t=Θ(n) moments; pseudorandomness in that regime is proposed as a conjecture, not proved.
In this work we give an efficient construction of unitary kkk-designs using O~(k⋅poly(n))\tilde{O}(k\cdot poly(n))O~(k⋅poly(n)) quantum gates, as well as an efficient construction of a parallel-secure pseudorandom unitary (PRU). Both results are obtained by giving an efficient quantum algorithm that lifts random permutations over S(N)S(N)S(N) to random unitaries over U(N)U(N)U(N) for N=2nN=2^nN=2n. In particular, we show that products of exponentiated sums of S(N)S(N)S(N) permutations with random phases approximately match the first 2Ω(n)2^{Ω(n)}2Ω(n) moments of the Haar measure. By substituting either O~(k)\tilde{O}(k)O~(k)-wise independent permutations, or quantum-secure pseudorandom permutations (PRPs) in place of the random permutations, we obtain the above results. The heart of our proof is a conceptual connection between the large dimension (large-NNN) expansion in random matrix theory and the polynomial method, which allows us to prove query lower bounds at finite-NNN by interpolating from the much simpler large-NNN limit. The key technical step is to exhibit an orthonormal basis for irreducible representations of the partition algebra that has a low-degree large-NNN expansion. This allows us to show that the distinguishing probability is a low-degree rational polynomial of the dimension NNN.
The nature of randomness and complexity growth in systems governed by unitary dynamics is a fundamental question in quantum many-body physics. This problem has motivated the study of models such as local random circuits and their convergence to Haar-random unitaries in the long-time limit. However, these models do not correspond to any family of physical time-independent Hamiltonians. In this work, we address this gap by studying the indistinguishability of time-independent Hamiltonian dynamics from truly random unitaries. On one hand, we establish a no-go result showing that for any ensemble of constant-local Hamiltonians and any evolution times, the resulting time-evolution unitary can be efficiently distinguished from Haar-random and fails to form a 222-design or a pseudorandom unitary (PRU). On the other hand, we prove that this limitation can be overcome by increasing the locality slightly: there exist ensembles of random polylog-local Hamiltonians in one-dimension such that under constant evolution time, the resulting time-evolution unitary is indistinguishable from Haar-random, i.e. it forms both a unitary kkk-design and a PRU. Moreover, these Hamiltonians can be efficiently simulated under standard cryptographic assumptions.
Unitary designs provide finite-moment approximations to Haar-random unitaries, with wide-ranging applications across physics and quantum information, from scrambling and black-hole dynamics to foundational primitives in quantum algorithms. Strong unitary designs capture a more demanding operational notion of approximation, requiring indistinguishability from Haar randomness even for quantum algorithms that may access a unitary not only in the forward direction, but also through its inverse, transpose, and complex conjugate. Motivated by the physical requirement that scrambling arise within the system itself, Schuster, Ma, Lombardi, Brandão, and Huang (arXiv:2509.26310) left open whether strong unitary designs can be generated in logarithmic depth using only the system qubits. For every fixed design order kkk and measurable-error tolerance, we construct strong approximate unitary kkk-designs in optimal Θ(log⁡n)Θ(\log n)Θ(logn) all-to-all circuit depth using only the nnn original system qubits. Our new ingredient is a logarithmic-depth Pauli-mixing bound for the perfect-matching ensemble, whose layers pair the qubits uniformly at random and apply independent random two-qubit gates. This bound controls the mixed forward-reverse two-query case, which we combine with existing design and gluing results to obtain strong unitary designs of arbitrary fixed order.
Pseudorandomness is increasingly recognized as a key property of ensembles in quantum information theory, statistical mechanics, and quantum many-body physics. Yet it appears in two conceptually different forms: statistical pseudorandomness, embodied by unitary designs, and computational pseudorandomness captured by pseudorandom unitaries (PRUs). The relationship between these two forms of pseudorandomness remains surprisingly poorly understood. Existing PRU constructions reveal this interplay where a statistically randomizing ingredient, a unitary design, is combined with classical cryptographic primitives to produce computational pseudorandomness. We show that statistical pseudorandomness is not necessary for computationally pseudorandom unitaries. We do this by replacing the unitary 222-design layer in the existing constructions with ensembles that are not even state 111-designs, yet are sufficiently {\em distinct}, a property we identify to be necessary for any PRU. This yields new non-adaptively secure PRU ensembles whose computational pseudorandomness is obtained without an underlying statistically pseudorandom quantum ensemble, such as a 222-design. We characterize distinctness via an entangled analogue of anticoncentration and use it to show that distinctness already captures constraints on coherence and imaginarity of PRUs, while identifying broad classes of inputs for which the latter obstruction disappears, enabling real-valued PRUs even for certain (maximally) entangled states. As an application, we use lack of distinctness to constrain the conjectured pseudorandomness of the random phase-Hadamard ensemble to form a PRU.
A unitary k-design is an ensemble of unitaries that matches the firstkkkmoments of the Haar measure. In this work, we provide two efficient constructions of k-designs on n-qubits using new random matrix theory techniques. Our first construction is based on exponentiating sums of random i.i.d. Hermitian matrices and uses O(k2n2)-many gates. In the spirit of central limit theorems, we show that this random sum approximates the Gaussian Unitary Ensemble (GUE). We then show that the product of just two exponentiated GUE matrices is already approximately Haar random. Our second construction is based on products of exponentiated sums of random permutations and uses Õ(kkkpoly (nnn)) many gates. Thekkkdependence is optimal (up to polylogarithmic factors) and is inherited from the efficiency of existing k-wise independent permutations. Furthermore, replacing random permutations with quantum-secure pseudorandom permutations (PRPs), we also obtain a pseudorandom unitary (PRU) ensemble that is secure under nonadaptive queries. A central feature of both proofs is a new connection between the polynomial method in quantum query complexity and the large-dimension (NNN) expansion in random matrix theory. In particular, the first construction uses the polynomial method to control high moments of certain random matrix ensembles without requiring delicate Weingarten calculations. In doing so, we define and solve a moment problem on the unit circle, asking whether a finite number of equally weighted points can reproduce a given set of moments. In our second construction, the key step is to exhibit an orthonormal basis for irreducible representations of the partition algebra that has a low-degree large-NNNexpansion. This allows us to show that the distinguishing probability is a low-degree rational polynomial of the dimensionNNN.
Unitary TTT-designs play an important role in quantum information, with diverse applications in quantum algorithms, benchmarking, tomography, and communication. Until now, the most efficient construction of unitary TTT-designs for nnn-qudit systems has been via random local quantum circuits, which have been shown to converge to approximate TTT-designs in the diamond norm using O(T5+o(1)n2)O(T^{5+o(1)} n^2)O(T5+o(1)n2) quantum gates. In this work, we provide a new construction of TTT-designs via random matrix theory using O~(T2n2)\tilde{O}(T^2 n^2)O~(T2n2) quantum gates. Our construction leverages two key ideas. First, in the spirit of central limit theorems, we approximate the Gaussian Unitary Ensemble (GUE) by an i.i.d. sum of random Hermitian matrices. Second, we show that the product of just two exponentiated GUE matrices is already approximately Haar random. Thus, multiplying two exponentiated sums over rather simple random matrices yields a unitary TTT-design, via Hamiltonian simulation. A central feature of our proof is a new connection between the polynomial method in quantum query complexity and the large-dimension (NNN) expansion in random matrix theory. In particular, we show that the polynomial method provides exponentially improved bounds on the high moments of certain random matrix ensembles, without requiring intricate Weingarten calculations. In doing so, we define and solve a new type of moment problem on the unit circle, asking whether a finite number of equally weighted points, corresponding to eigenvalues of unitary matrices, can reproduce a given set of moments.