On the pseudorandomness of simple quantum processes

On the pseudorandomness of simple quantum processes

arXiv:2610.02100v1 [quant-ph] 1 Oct 2026

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 = Ot (n2 log2 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.

1

Introduction

The seminal work of Gowers [Gow96, Gow13] shows that random reversible circuits can achieve remarkable mixing properties: repeatedly composing random three-bit scramblers can produce global permutations on n-bit strings that match statistical properties of truly random permutations (see
e n3 t(n2 + t)(n3 + t) Figure 1). Specifically, they become approximately t-wise independent after O rounds: for any t distinct inputs, the joint distribution of their images is close to uniform over ordered tuples of t distinct outputs. These findings have had many applications across many areas of computer science; for example, informing the design of block ciphers [BS15], cryptographic protocols [CCMR25, CLZ26], hash functions [BCFM00], sampling-without-replacement methods [Tho13] and derandomization techniques [MOP20]. Gowers conjectured [Gow13] that these mixing properties suggest an even stronger possibility: a sufficiently deep random reversible circuit may actually be indistinguishable from a uniformly * Boston University. mail@ind-jesko.net † Ruhr-University Bochum. jonas.haferkamp@rub.de ‡ Boston University. poremba@bu.edu

1

Figure 1: A classical random reversible circuit consisting of simple 3-bit scrambling operations. random permutation to every efficient observer. In other words, they could form ensembles of cryptographic pseudorandom permutations [LR88]. This is known as the Gowers conjecture. While approximate t-wise independence only constrains the joint outputs on a prescribed number of inputs in a statistical sense, pseudorandomness requires security against all polynomialtime distinguishers, each of which may make its own polynomial number of queries. Importantly, passing statistical tests that show limited statistical independence, by itself, does not establish this stronger guarantee. Despite substantial recent progress on the statistical mixing of random circuits [BHH16, CHH+ 25, GHKO25, BH26], the computational conjecture still remains wide open as a positive resolution would imply the existence of one-way functions, and hence P ̸= NP. Hoory, Magen, Myers, and Rackoff [HMMR05] conjectured that approximate 4-wise independence should already suffice for pseudorandomnness provided one uses “locally composed” permutations. Their rationale was that 4-wise independence is the first threshold at which no obvious distinguishers are known. A common formulation of the conjecture assumes round locality: each output bit of a round depends on only constantly many input bits, although the round may act on all wires. Thus, the conjecture may be stated as follows: Conjecture 1.1 (HMMR Conjecture). Let {νn }n be an efficiently samplable distribution on reversible rounds on n bits, each of whose output bits depends on at most a constant number of input bits. If the composition of T = poly(n) independent samples from {νn }n is approximately 4-wise independent with exponentially small error, then the resulting ensemble is a pseudorandom permutation ensemble. The fact that 3-wise independence is insufficient follows from algebraic examples [HMMR05]. The motivation behind the 4th-order threshold comes from group theory. Any set of permutations that satisfies 4-transitivity will, after enough compositions, at least result in the alternating group [DM96, Cam99]. This made the HMMR conjecture highly plausible. In a recent breakthrough, however, Dujmovic, Pelecanos, and Tessaro [DPT25] refuted this round-local formulation, even with any constant order of independence. Quantum pseudorandomness. The classical questions above have direct quantum analogues: can simple quantum processes, likewise, appear highly complex? Investigating these questions in the more general quantum case could potentially shed new light on the classical setting. Random quantum circuits are among the simplest models of complex quantum dynamics (see Figure 2) and have a wide range of applications across quantum information science, such as in learning theory [AGL+ 23, SHH25], many-body experiments [SKYH25, MCSH25], and especially in blackhole physics and quantum gravity [HP07, LSH+ 13, RY17, LLZZ18, KP23, PRV26, SML+ 25]. One may naturally ask whether the same conjectures hold if we replace reversible gates by local quantum gates and uniform permutations by unitaries drawn from the Haar measure—the uniform 2

Figure 2: A simple nearest-neighbor random quantum circuit, where each box is a two-qubit quantum gate sampled independently from the Haar measure over the unitary group U(4). probability measure over the unitary group [Haa33, Mel24]. In particular, one may ask: Are sufficiently deep random quantum circuits pseudorandom? The statistical counterpart of t-wise independence in the quantum setting is what is known as a unitary t-design [DCEL09, GAE07, CLLW15]—an ensemble matching the first t unitary moments of the Haar measure. A pseudorandom unitary [JLS18, MPSY, MH25], by contrast, only needs to fool observers with limited computational resources. In the statistical setting, it is well known that local random circuits form approximate designs in depth polynomial in n and t [BHH16, Haf22, CHH+ 24, BH26]. As in the classical case, however, the depth depends on t, whereas pseudorandomness requires a single polynomial-depth ensemble which remains secure against all efficient quantum distinguishers. This distinction is precisely the driving motivation for the quantum Gowers conjecture1 which we hinted at earlier; it asks whether random quantum circuits (see Figure 2) can form pseudorandom unitaries after some sufficient polynomial depth. Recent developments make this question especially timely. Advances in quantum complexity theory [Kre21] provide strong evidence that pseudorandom unitaries can exist without one-way functions—the de-facto minimal assumption in theoretical cryptography [BS15]. This striking observation has led to the pursuit of quantum cryptography from new assumptions which may plausibly hold even if one-way function exist do not exist [KT24, BHHP24, HH24, HM25, FGSY26, CEG+ 26, GKT26]. The quantum Gowers conjecture is central among these assumptions, as it is arguably the simplest and most natural way to generate quantum pseudorandomness; in particular, it may plausibly hold even in a world in which BQP = QMA [Kre21]. At the same time, the conjecture is also widely believed to be true among quantum information theorists. Despite substantial recent progress on constructing pseudorandom unitaries from standard cryptographic assumptions [JLS18, LQS+ 24, AGKL24, MPSY, CDX+ 24, MH25, SHH25, FLM+ 26], the quantum analog of the Gowers conjecture still remains wide open—just like its classical counterpart. The Quantum HMMR conjecture. To what extent do random quantum circuits mix just like random classical circuits? Interestingly, the quantum setting has a strikingly similar threshold behavior as in the classical HMMR setting [HMMR05]. The Clifford group [NC01] forms an exact unitary 3-design [Web16], yet is efficiently distinguishable from a genuine Haar random unitary: its action on a computational-basis state produces a stabilizer state, which can be recognized efficiently [Mon17, GIKL24]. Moreover, classification results for unitary t-groups show that t = 4 is an inherent algebraic threshold at which more complex behavior must emerge: in dimension d ≥ 3, 1 To the best of our knowledge, explicit formulations of the conjecture first appeared in [BHHP24, FGSY25].

3

no finite subgroup of the unitary group U(d) forms an exact unitary t-design for t ≥ 4 [BNRT20]. The absence of a group design for the fourth moment raises an important question which is implicit in many prior works in the literature [ZKGG16, CMR22, HMMH+ 23, KKSZ26, HJH26]; namely Does Haar-like behavior of unitary designs already appear at the fourth moment? This motivates the following natural quantum analog of the HMMR conjecture [HMMR05]. Conjecture 1.2 (Quantum HMMR Conjecture). Let {νn }n be an efficiently samplable family of distributions on local quantum gates, each acting on a constant number of qubits independent of n. Let νn∗T denote the n-qubit ensemble obtained by independently composing T = poly(n) gates drawn from νn . If {νn∗T }n forms an approximate unitary 4-design with negligible error, then it is a pseudorandom unitary ensemble. Just like its classical counterpart, the quantum HMMR conjecture asks whether limited statistical properties can be viewed as evidence of computational pseudorandomness. The locality of the ensemble, likewise, serves as an important purpose as in the classical case: it ensures some amount of “simplicity” in contrast to an artificially engineered ensemble which may fail due to intricate algebraic structure [HMMR05]. Given that the HMMR conjecture has been refuted in the classical setting, one may ask to what extent random quantum circuits admit similar counterexamples, or whether there are differences between classical and quantum that are yet to be discovered.

1.1

Our contributions

Our limited progress on these conjectures reflects many important gaps in our understanding of how pseudorandomness arises within simple quantum processes. In this work, we develop the techniques to address them; specifically, we investigate when simple, local ensembles fail to become pseudorandom despite achieving strong statistical moment properties. This brings the study of pseudorandomness and statistical mixing of quantum processes on roughly the same theoretical footing as those of random classical circuits. Building on these no-go results, we then ask when genuine pseudorandomness can emerge; we explore how the physics notions of thermalization, scrambling and entanglement saturation can serve as new proxies for the emergence of pseudorandomness. We hope that this connection can inform the Gowers conjecture in both the classical and the quantum setting. We now give an overview of our main results. In what follows, we assume basic familiarity with standard concepts from the literature on unitary t-designs and Haar integration; we refer to the preliminary section in Section 3 for additional background on these topics. Refuting the Quantum HMMR conjecture. Our first contribution focuses on the natural quantum analog of HMMR conjecture [HMMR05] which deals with local quantum processes. We refute the Quantum HMMR conjecture, as described earlier, in full generality—essentially to the same extent as in the classical setting by [DPT25]. This is captured by the following theorem. Theorem 1.3 (Refutation of Quantum HMMR). For every fixed integer t ≥ 4, there exists an efficiently samplable family {νn }n of distributions on one- and two-qubit gates such that, for all sufficiently large n, the ensemble νn∗T obtained from T = Ot (n2 log2 n) independent steps is an approximate adaptive unitary tdesign with negligible error exp(−Ωt (log2 n)). Nevertheless, an efficient quantum algorithm distinguishes this ensemble from Haar with constant advantage using Ot (log2 n) parallel forward queries. 4

This rigorously shows that statistical moment properties, in general, fail to translate into computational pseudorandomness—even for simple processes that comprise local interactions. Interestingly, our approach deviates significantly from the classical counterexample of [DPT25] and instead relies on inherently quantum techniques which have no classical counterpart.2 Our approach is to apply a random nearest-neighbor Clifford gate at each step, except with some small probability 1/m with m = Θt (n2 ), when we instead apply a random non-Clifford single-qubit Z-rotation. The Clifford gates provide enough mixing without destroying stabilizer structure, while the occasional rotations allow the moments to approach those of the Haar measure. This approach is inspired by the structured ensembles in [HMMH+ 23, BL26]; in our case, however, we analyze a single i.i.d. local walk. A standard spectral gap analysis does not suffice for us: converting a moment bound into an adaptive-query bound incurs an exponential blow-up in n, and running the walk long enough to compensate for this factor would introduce too many non-Clifford gates. The key is to use more information about the spectrum of the moment operator. We know that the local Clifford walk converges rapidly to the Clifford twirl, but this alone does not give Haar moments since the Clifford twirl fixes more operators than the Haar twirl does. However, for fixed t, the fixed-point space of the t-fold Clifford twirl has dimension bounded independently of n [GNW21]. Thus, Clifford mixing supresses most of the spectrum and only constantly many eigenvalues need to be handled by the rare non-Clifford rotations. In this subspace of constant dimension it then suffices to apply known spectral bounds on doped Clifford circuits [BH26]. To prove the adaptive design property, we fix an adaptive t-query algorithm and express the acceptance probability using the spectral decomposition of the moment operator. The exponentially small eigenvalues already compensate for the dimension factor in the usual bound. The remaining contribution is a sum of constantly many decaying exponentials, one for each of the remaining eigenvalues. Instead of bounding the coefficients separately, we exploit the fact that the first few values are bounded because they are differences of acceptance probabilities. This strategy is similar in spirit to the polynomial method, where the boundedness of the outcome probabilities themselves is exploited to argue about the distinguishability of two quantum algorithms. The boundedness of the outcome probability was also directly used in [BL26]. Separating unitary designs from pseudorandom unitaries. The above counterexample to the quantum HMMR conjecture relies crucially on the fact that the ensemble only matches constant moments of the Haar measure. Could an ensemble that matches much higher (say, polynomial) moments of the Haar measure be sufficient to achieve pseudorandomness? Clearly, matching increasingly higher moments seems to rule out more and more statistical tests. We prove that that the answer is no in general; however, to show this we must deviate from the prior setting of local ensembles and explore new constructions. While this statement is well-known classically, the quantum case appears much more subtle and has remained open for quite some time. Our second contribution is the (to the best of our knowledge) first rigorous separation between arbitrary polynomial-order unitary designs and pseudorandom unitaries. Theorem 1.4 (Separating Adaptive Unitary Designs from Pseudorandom Unitaries). Let n ≥ 64 and 1 ≤ t ≤ 2n/4−4 be an integer (depending on n). For every 0 < ε ≤ 1/2, there exists an adaptive unitary 2t(t−1) t-design in depth poly(n, t, log(1/ε)) with error 2n + ε, and yet an efficient quantum algorithm using O(nt) forward queries and poly(n, t) time can distinguish it from Haar with constant advantage. 2 Interestingly, our counterexample does not require the use of a counter as in the classical setting [DPT25].

5

The basic idea behind the specific circuit ensemble is to engineer a special fixed subspace in which the ensemble retains a controlled amount of detectable structure, while exhibiting strong mixing behavior on the orthocomplement of the subspace. We now describe our circuit ensemble in more detail. First, we pick the one-dimensional subspace S = span{|+⟩⊗n }. Our construction then uses what we call the “FB ensemble”: we construct unitaries of the form U = FB, where F is a diagonal phase function circuit, and where B is a block-diagonal circuit that leaves S invariant and mixes its orthogonal complement. Before we explain the full construction in detail, we will first consider a simpler ensemble of the form U = FB∞ , for an idealized unitary B∞ . This is a product of two unitary operators, where • F = ∑ x (−1) f (x) | x ⟩⟨ x | is a phase function operator that maps |+⟩⊗n to a binary phase state |ψ f ⟩ = 2−n/2 ∑ x (−1) f (x) | x ⟩, for a 2t-wise independent function3 f , and • B∞ is a Haar random unitary which leaves the subspace S invariant; in other words, B∞ is a block-diagonal unitary such that B∞ = 1S ⊕ BS⊥ , where BS⊥ ∼ µ H , i.e., BS⊥ is sampled according to the Haar measure over the unitary group acting on S⊥ = span{|+⟩⊗n }⊥ . We now explain why this ensemble remains distinguishable from a Haar random unitary. Suppose that we query the unitary m many times on input |+⟩⊗n within S. This results in m copies of a binary phase state |ψ f ⟩⊗m . By design, these binary phase states are chosen precisely so that they match strong statistical properties of the Haar measure; for example, when m = t, we know that 2t-wise independence ensures that these states form a state t-design with error O(t2 /2n ), and thus approximately match t moments of the Haar measure [BS19]. However, for a slightly larger number of copies, say m = O(nt), we can exploit the fact that binary phase states become learnable, as shown by Arunachalam, Bravyi, Dutt, and Yoder [ABDY23]. Using their derivative-measurement technique, we find that each copy reveals a relative phase f ( x ) + f (y) for a uniformly random pair of distinct inputs, which is a linear equation in the 2nt seed bits. A simple finite-field character-sum bound shows that only m = O(nt) such equations determine the phase function up to an additive constant with high probability. Gaussian elimination then allows us to recover a candidate, and testing it on fresh copies distinguishes our ensemble from Haar with constant advantage. Next, we explain why the invariance of U = FB∞ on the special subspace S = span{|+⟩⊗n } does not spoil the overall unitary t-design property. Our key insight is that U = FB∞ can be viewed as a special case of the "PFC ensemble" of Metger, Poremba, Sinha and Yuen [MPSY24]. To see why this is the case, notice that every computational basis permutation P fixes |+⟩⊗n , and hence Haar invariance on S⊥ tells us that PB∞ has the same distribution as B∞ . We can therefore insert an independent uniform permutation without changing the ensemble: FB∞

7→

FPB∞ = P( P† FP) B∞ .

For each fixed P, the conjugated phases P† FP remain 2t-wise independent. Moreover, B∞ supplies the other crucial role of the Clifford collision-breaking operator: on t copies, it places all but O(t2 /2n ) expected weight in the distinct subspace, spanned by computational basis tuples with pairwise distinct labels, uniformly over the input. On this subspace, phase averaging removes all matrix entries except those relating permutations of the same tuple, while the random basis permutation makes these tuples uniform. To formally carry out the proof of the approximate adaptive unitary  −1 j for uniformly random and independent coefficients a ∈ F n . As a x ∑2t 2 j j j =0 we explain in Section 5.1, this ensemble requires merely 2nt seed bits and is 2t-wise independent. 3 Concretely, we choose f ( x ) = tr F2n /F2



6

t-design property, we rely on a recent positive-operator analysis of the PFC construction due to Cui, Schuster, Brandão, and Huang [CSBH25]. Their proof technique allows us to turn this collision bound into an O(t2 /2n ) unitary t-design error—even with respect to adaptive t-query experiments, without a square-root loss which is inherent in [MPSY]. This completes our proof overview of the idealized U = FB∞ ensemble, and shows that it achieves the statistical moment property, despite its efficiently detectable structure on the special subspace S = span{|+⟩⊗n }. Finally, we replace the idealized operator B∞ by an explicit random circuit that fixes |+⟩⊗n . The key step is a decomposition of every special unitary on S⊥ into 2n − 1 operations, each applying a unitary to n − 1 qubits conditioned on the remaining qubit being in the state |−⟩. We combine this decomposition with controlled versions of the constant-depth generators of [ABH+ 26]. Next, we use bounds on Kazhdan constants which result in a walk on O(n) efficiently implementable circuits with an inverse-polynomial spectral gap. This gap lets us approximate the t moments of B∞ in depth poly(n, t, log(1/ε)), with error small enough to control adaptive t-query experiments. Since every step fixes |+⟩⊗n , the phase-learning distinguisher still applies to U = FB. Unlike our first construction, however, the walk samples controlled circuits rather than individual local gates, and hence the separate phase circuit F remains essential for the construction. Pseudorandomness and maximal scrambling. Our two no-go results suggest that both locality and the number of matched moments play a role in the emergence of pseudorandomness: • locality constrains the kinds of algebraic structure that can arise, and in turn limits what an efficient distinguisher can exploit, as in the FB ensemble; the more structure we build into the ensemble, the more opportunities we give a distinguisher to take advantage of it. • moment matching is equally important to defeat broad classes of statistical tests, as repeated local dynamics do not provide a guarantee on randomness. Our quantum HMMR counterexample shows that local iterated ensembles can still retain efficiently detectable stabilizer structure when it matches only a constant number of moments of the Haar measure. We should therefore try to match more moments while keeping the process local. But how many moments should we match before we can reasonably expect pseudorandomness to kick in? In Section 6, we explore an explicit connection to the notion of scrambling from many-body physics. Scrambling describes how initially local information spreads across many degrees of freedom until it becomes inaccessible to local observations. This is closely related to diffusion in classical block ciphers, where changes in a few input bits spread across many output bits [HMMR05, BS15]. The connection to unitary designs provides a natural scale for our question: Liu, Lloyd, Zhu, and Zhu [LLZZ18] showed that higher moment matching leads to saturation at progressively higher orders in a hierarchy of entanglement entropies. Eventually, this process reaches a limit: when t = Θ(n) all entanglement entropies are saturated, which is known as maximal scrambling. Our results suggest, however, that even maximal scrambling does not imply pseudorandomness, at least generically. The FB ensemble can reach this regime, with expected min-entropy within a constant of the maximum across every fixed balanced crossed cut of its Choi state, yet remain efficiently distinguishable from Haar with constant advantage using only O(n2 ) forward queries. Increasing the depth of B improves mixing without changing the relation U |+⟩⊗n = F |+⟩⊗n , so the same phase-learning distinguisher continues to work. This suggests caution when using unitary designs to model scrambling in quantum many-body physics and black-hole evolution: even 7

maximally scrambled systems may exhibit some amount of structure that is accessible to efficient experiments. This challenges the notion that maximal scrambling is synonymous with Haar behavior. Pseudorandomness, on the other hand, still remains a reliable proxy. Can maximal scrambling still teach us something about pseudorandomness? Neither counterexample rules out pseudorandomness when independent local dynamics match moments up to the maximal scrambling scale, which suggests that a genuine threshold behavior may occur. We therefore conjecture that an ensemble obtained by independently composing T = poly(n) local gates drawn from the same efficiently samplable distribution is pseudorandom whenever it forms an approximate unitary t-design for t = Θ(n) with negligible additive error. Known results on local random quantum circuits already suffice to achieve this regime, giving polynomial-depth designs at t = Θ(n) [BHH16], so this conjecture offers a possible route towards the quantum Gowers conjecture. Recent results showing uniformly small outcome probabilities at the same design order provide further evidence for the significance of this threshold [HJH26]. More generally, this connection suggests studying growing-order independence in local reversible circuits as a way to move beyond the classical HMMR counterexamples, and may provide a new perspective on the Gowers conjecture in both the classical and the quantum setting.

2

Related work

The closest classical precursor to our work is that of Dujmovic, Pelecanos, and Tessaro [DPT25], which refuted the conjecture of Hoory, Magen, Myers, and Rackoff [HMMR05] by constructing locally composed permutations with approximate independence of any prescribed constant order that fail to become pseudorandom. Their notion of locality allows a round to act on all wires, provided each output bit depends on only constantly many input bits. Our first result gives a quantum analogue under the requirement that each step acts on at most two qubits. Our proof, however, uses inherently quantum techniques to balance moment matching and stabilizer structure. [HMMH+ 23] shows that unitary designs can be obtained with a number of non-Clifford gates independent of the system size, for fixed design order and error. Bittel and Leone [BL26] strengthen this to adaptive queries and give an efficient test for the stabilizer structure that survives at low non-Clifford count. These results provide distinguishable designs beyond the Clifford 3-design example [Web16, GIKL24]. Our construction deviates from these two works as it obtains a negligible error adaptive design via a homogenous i.i.d. walk on only one- and two-qubit gates. Our higher-order separation is related to constructions and learning algorithms for quantum phase states. Brakerski and Shmueli [BS19] showed that binary phase states defined by 2t-wise independent functions form approximate state t-designs. Arunachalam, Bravyi, Dutt, and Yoder [ABDY23] developed derivative measurements for learning polynomial phase states, which we use to recover the seed of our phase family. Our second main result extends these learning algorithms into a fine-grained query setting. The analysis of our second ensemble crucially builds on the PFC construction of Metger, Poremba, Sinha, and Yuen [MPSY24] and the adaptive-query methods of Cui et al. [CSBH25]. Our work shows how to embed structure into the PFC ensemble in a way that does not spoil the design property. A different obstruction to pseudorandomness was established by Cui et al. [CSM+ 25], who showed that evolution under constant-local, time-independent Hamiltonians is efficiently distinguishable from Haar measure, irrespective of the evolution time. Their obstruction already prevents sufficiently accurate unitary 2-designs. Importantly, it does not separate moment matching from 8

pseudorandomness: both properties fail in their setting. Our local-circuit counterexample instead achieves any prescribed constant design order with negligible additive error, so its distinguishability cannot be explained by such a low-moment obstruction. Liu, Lloyd, Zhu, and Zhu [LLZZ18] showed that statistical moments can be viewed as a proxy for Haar randomness through the lens of entanglement entropies: they showed that increasing design order controls progressively higher Rényi entanglement entropies, with sufficiently accurate designs of order Θ(n) giving near-maximal expected min-entropy. In our work, we discuss explicit connections to computational pseudorandomness. Concurrent work of Raza, Eisert, and Fefferman [REF26] studies the relationship between statistical and computational pseudorandomness from a complementary direction: they show that design-level randomness is not necessary for constructing pseudorandom unitaries, identifying a substantially weaker “distinctness” property that suffices in the non-adaptive setting. Our results show that even strong unitary-design guarantees need not be sufficient for pseudorandomness, so together the two works delineate the gap between statistical and computational notions of quantum randomness from opposite sides. AI Statement. The conceptual ideas behind all of the main results are due to the authors. Prior to the release of ChatGPT Astra, we had obtained preliminary versions of Theorem 1.3 and Theorem 1.4 without substantial use of AI tools. After its release, we used ChatGPT Astra to improve and simplify our constructions further, so as to obtain the best bounds and parameters for all of our theorems. The model was used to assist with some parts of the technical write-up, for devising figures and for the literature review. We give special credit to ChatGPT Astra for its contribution to the formulation and proof of Lemma 4.3. The authors checked the results and take full responsibility for their correctness. Acknowledgements. We thank Ran Canetti and Angelos Pelecanos for many useful discussions. Organization. In Section 3, we present mathematical preliminaries and a minimal background on quantum information. The proof behind the counterexample to the quantum HMMR conjecture in Theorem 1.3 appears in Section 4.1. Our separation between unitary designs and pseudorandom unitaries in Theorem 1.4 is shown in Section 5. In Section 6, we explore connections to many-body physics and scrambling, and present new conjectures for when pseudorandomness can emerge.

3

Preliminaries

We write [n] = {1, . . . , n} and |S| for the cardinality of a finite set S. If X is distributed according to a probability measure µ, we write X ∼ µ and EX ∼µ for the corresponding expectation. We use Ot (·), Ωt (·), and Θt (·) when the implicit constants may depend on t. A function negl : N → R≥0 is negligible if, for every polynomial p, we have negl(n) < p(1n) , for all sufficiently large n. Operators, norms, and vectorization. We use L(V ) to denote the set of linear operators acting on a finite-dimensional complex √ vector spaces V. The d-dimensional identity operator is Id . For X ∈ L(Cd ), we use ∥ X ∥1 = Tr X † X for the trace norm, ∥ X ∥2 = (Tr X † X )1/2 for the Frobenius norm, ∥ X ∥∞ for the operator norm. 9

Haar measure and moment operators. The Haar measure µ H is the unique (left and right) invariant uniform probability measure over the unitary group U(d); for any integrable function f , it comes with the invariance [Haa33, Sim96] of the form Z U( d )

f (UV )d µ H (U ) =

For brevity, we often write

R U( d )

Z U( d )

f (U ) d µ H (U ) =

f (U ) d µ H (U ) =

Z U( d )

f (VU )d µ H (U ).

(1)

E [ f (U )], where we use the notation U ∼ µ H

U ∼µ H

to describe that the unitary U is sampled uniformly according to the Haar measure over U(d). More generally, for a unitary ensemble ν, the notation U ∼ ν means that U is sampled according to ν. For U ∼ ν and V ∼ η sampled independently, ν ∗ η is the distribution of UV. The notation ν∗r describes a product of r independent samples (Ur Ur−1 . . . U1 ), where Ui ∼ ν for i ∈ [r ]. (t) Given a unitary ensemble ν and t ∈ N, we define the t-fold twirl Tν over ν as the map h i (t) X 7 → T ν ( X ) = E U ⊗ t X (U † ) ⊗ t . (2) U ∼ν

We denote the corresponding vectorized moment operator of order t as h i ⊗t (t) Mν = E U ⊗t ⊗ U . U ∼ν

(t)

(t)

(t)

(3)

(t)

Thus vec(Tν ( X )) = Mν vec( X ) for every X. We use Tµ H and Mµ H to denote the t-fold twirl and moment operator for the Haar measure. Adaptive unitary designs. A t-query quantum oracle-algorithm AU with access to an n-qubit unitary oracle U ∈ U(2n ) is a sequence of (n + m)-qubit unitaries of the form A t · U · A t −1 · U · A t −2 · · · A 1 · U · A 0

(4)

where At , At−1 , . . . , A1 , A0 act on registers AB, for an n-qubit register A and m-qubit ancilla register B, for m ∈ N. The state of a t-query oracle algorithm AU on input |0n+m ⟩ is defined as n+m |AU ⟩. t ⟩ = A t · U · A t −1 · U · A t −2 · · · A 1 · U · A 0 | 0

(5)

An (adaptive) approximate unitary t-design approximately matches the first t moments of the Haar measure. We give a formal definition below. Definition 3.1 (Approximate unitary t-design). Let n, t ∈ N. An ensemble of n-qubit unitaries ν is an ϵ-approximate adaptive unitary t-design if any adaptive t-query quantum oracle algorithm AU can distinguish U ∼ ν from a Haar random unitary U ∼ µ H with advantage at most ϵ; taking the supremum over all such AU with two-outcome measurements ( MA , I − MA ), this means δt (ν, µ H ) := sup

h i h i U U U E Tr MA · |AU ⟩⟨A | − E Tr M · |A ⟩⟨A | ≤ ϵ. A t t t t

A,MA U ∼ν

U ∼µ H

(6)

Next, we introduce the computational analog of pseudorandom unitaries [JLS18, MPSY, MH25]. This requires us to formally define the notion of a quantum polynomial-time algorithm. 10

Pseudorandom unitaries. A quantum polynomial-time (QPT) algorithm A is a uniform family of circuits {An }n∈N such that there is a polynomial p(n) with the property that the circuit size of An is bounded by p(n); here, uniform means that there exists a polynomial-time classical algorithm which, on input 1n , outputs a classical description of An . A QPT algorithm, may also initialize some number of ancilla qubits to |0⟩ and trace them out at the end of the computation. Definition 3.2 (Pseudorandom unitary). A unitary ensemble of {Un }n∈N is called a pseudorandom unitary if, for all n, Un = {Uk }k∈Kn , is a set of n-qubit unitaries with key space Kn such that • (Efficient generation:) There exists a QPT algorithm running in time poly(n) that implements the n-qubit unitary Uk on input k, for any key k ∈ Kn . (·)

• (Pseudorandomness:) For any QPT oracle-algorithm {An }n∈N which runs in time poly(n) and makes poly(n) queries, followed by an efficient two-outcome measurement ( MAn , I − MAn ), h i h i Uk U U k − E M · |A ⟩⟨A | ≤ negl(n). E Tr MAn · |AU ⟩⟨A | Tr n n An n n U ∼µ H

k ∼Kn

Distinct subspace. The set of t-fold tuples over [d] = {1, 2, . . . , d} is denoted by [d]t . We call a tuple x = ( x1 , . . . , xt ) ∈ [d]t distinct if xi ̸= x j for all i ̸= j. We denote the set of distinct tuples in [d]t by dist(d, t). We define the projector onto the t-fold distinct subspace as Πdist(d,t) =

∑

| x1 , . . . , xt ⟩⟨ x1 , . . . , xt |.

(7)

x1 ,...,xt ∈[d] xi ̸ = x j (i ̸ = j )

For example, the projector onto the two-fold distinct subspace is Πdist(d,2) = I − ∑ x | x, x ⟩⟨ x, x |.

4

Refuting the Quantum HMMR conjecture

We prove Theorem 1.3 by adding rare single-qubit non-Clifford gates to a local Clifford walk. The Clifford updates produce rapid mixing, while the non-Clifford gates handle the remaining low-order moment obstructions. Because non-Clifford gates appear infrequently, the resulting circuits still retain enough stabilizer structure to be efficiently distinguished from the Haar measure. Let C n denote the n-qubit Clifford group modulo global phase, equipped with the uniform distribution whenever it is used as an ensemble. Fix a finite inverse-closed generating set G ⊆ C 2 containing the identity. We arrange the qubits on a ring, with indices understood modulo n. For an integer m ≥ 2, one update is sampled as follows: • With probability 1 − 1/m, choose an edge (i, i + 1) uniformly among the n edges and apply a random gate from G to those two qubits. We denote this local Clifford distribution by χn . • With probability 1/m, apply a uniformly random rotation4 eiϕZ to the first qubit. We denote this single-qubit distribution by ξ n . 4 Note that, for fixed t, a simple discretization of the rotation angles reproduces the continuous t-th moment exactly,

while finite-precision implementation introduces only negligible total error. We omit these implementation details.

11

Thus, the one-step distribution of our walk is of the form νn = (1 − m−1 )χn + m−1 ξ n .

(8)

We call a choice of the ξ n branch an insertion, including its identity outcome. Every update acts on at most two neighboring qubits, and all updates are independent samples from the same distribution. Theorem 1.3 (Refutation of Quantum HMMR). For each fixed integer t ≥ 4, there are an integer At ≥ 1 and a constant κt > 0 such that, for sufficiently large n, setting T = 3m⌈log2 n⌉ = Ot (n2 log2 n)

m = A t n2 ,

(9)

results in an iterated ensemble νn∗T based on the local ensemble νn in (8), and which forms an adaptive unitary t-design with negligible error 2 δt (νn∗T , µ H ) ≤ e−κt log n . (10) Nevertheless, a uniform polynomial-time algorithm distinguishes this ensemble from Haar with constant advantage using O(log2 n) parallel forward queries. We need the following standard lemma that writes the expected outcome probability of a quantum experiment as a linear function in the moment operator: Lemma 4.1 (Acceptance probabilities from moment operators). Let t ∈ N and let AU be any adaptive t-query algorithm AU with forward access to an n-qubit unitary, and which performs a two-outcome measurement ( MA , I − MA ). Let d = 2n . Then, there exists a matrix ΛA , depending only on the algorithm A and its measurement, such that, for every unitary ensemble ν, h i   (t) U † E Tr MA · |AU , ∥ΛA ∥1 ≤ d2t . (11) t ⟩⟨At | = Tr ΛA · Mν U ∼ν

Proof. For strings a = ( a1 , . . . , at ), b = (b1 , . . . , bt ) ∈ [d]t define

|ϕa,b ⟩ := At (| at ⟩⟨bt | ⊗ IB ) At−1 · · · A1 (| a1 ⟩⟨b1 | ⊗ IB ) A0 |0n+m ⟩. Writing U ⊗ IB = ∑ a,b∈[d] Uab | a⟩⟨b| ⊗ IB in each oracle call yields

|AU t ⟩ =

∑

 t

 U a b ∏ i i |ϕa,b ⟩.

a,b∈[d]t i =1

Let G be the d2t × d2t matrix with entries G(a,b),(a′ ,b′ ) = ⟨ϕa,b | MA |ϕa′ ,b′ ⟩. Then U Tr MA |AU t ⟩⟨At |





=

∑



a,b,a′ ,b′

⊗t

∏ Ua b U i i

i

 ai′ bi′

G(a′ ,b′ ),(a,b) . ⊗t

Since ⟨a, a′ |U ⊗t ⊗ U |b, b′ ⟩ = ∏i Uai bi Uai′ bi′ and G is Hermitian, this equals Tr[Λ†A U ⊗t ⊗ U ] for the realigned matrix (ΛA )(a,a′ ),(b,b′ ) := G(a,b),(a′ ,b′ ) . Averaging over U ∼ ν proves formula. 12

1/2 For the norm bound, G ⪰ 0 is the Gram matrix of the vectors MA |ϕa,b ⟩, and MA ⪯ I gives 2 Tr G ≤ ∑a,b ∥ϕa,b ∥ . The map X 7→ ∑ a,b (| a⟩⟨b| ⊗ IB ) X (|b⟩⟨ a| ⊗ IB ) = I A ⊗ Tr A X multiplies the trace by d, and the Ai preserve it. Applying this at each of the t oracle positions gives ∑a,b ∥ϕa,b ∥2 = dt , so ∥ G ∥1 = Tr G ≤ dt . Realignment only permutes entries, so ∥ΛA ∥2 = ∥ G ∥2 ≤ ∥ G ∥1 ≤ dt . Finally, ΛA is a d2t × d2t matrix, hence ∥ΛA ∥1 ≤ dt ∥ΛA ∥2 ≤ d2t .

The next lemma summarizes results which are shown in [GNW21] and [BH26]: (t)

(t)

Lemma 4.2 (Spectral gaps of the Clifford walk). Fix t ≥ 4. The moment operators MC and Mµ H are n orthogonal projectors onto the Clifford- and Haar-invariant subspaces, respectively, with the latter contained in the former. For all sufficiently large n, t −2

rank MC = Dt := ∏(2 j + 1). (t) n

(12)

j =0

There are universal constants γ, a > 0 such that the following holds: The local Clifford moment operator has absolute spectral gap at least γ/n outside the Clifford-invariant subspace: (t)

(t)

Mχn − MC

n

∞

≤ 1−

γ . n

(13)

On the Clifford-invariant subspace, the insertion averaged between Clifford twirls has spectral gap at least a outside the Haar-invariant subspace. Equivalently, (t)

MC

n

(t)
(t) (t) (t)
I − Mξ n MC ⪰ a MC − Mµ H . n

n

(14)

After subtracting the Haar moment from a suitable power of the walk’s moment operator, all but constantly many eigenvalues will be exponentially small in n. The contribution of the remaining eigenvalues to an algorithm’s acceptance-probability difference is a finite spectral expansion of j the form u j = ∑i bi λi , where j counts repetitions. Bounding the individual coefficients bi could introduce an unwanted dependence on the dimension. Instead, we use that acceptance probabilities are bounded: the following combinatorial lemma bounds the entire expansion from its first few values. Lemma 4.3. Let D ≥ 1 and 0 < ρ < 1. Suppose D

u j = ∑ bi λ i

j

( j ≥ 1),

|λi | ≤ ρ.

i =1

If |u1 |, . . . , |u D | ≤ B, then, for every j ≥ D,

|u j | ≤ B · D · 2

D



 j+D−2 · ρ j− D . D−1

13

(15)

Proof. The generating function of the sequence is N (z)

∑ u j +1 z j = q ( z ) ,

j ≥0

D

q ( z ) = ∏ (1 − λ i z ),

deg N ≤ D − 1.

i =1

Writing q(z) = ∑kD=0 qk zk , the elementary symmetric coefficient bound gives |qk | ≤ ( Dk)ρk . Consequently, the coefficient of zℓ in N (z), for 0 ≤ ℓ ≤ D − 1, is ℓ

Nℓ = ∑ qk uℓ−k+1 , k =0

ℓ

  D k | Nℓ | ≤ B ∑ ρ ≤ B2D . k k =0

D −1 D Thus ∑ℓ= 0 | Nℓ | ≤ BD2 . On the other hand, expanding the D geometric series in 1/q ( z ) shows r that its coefficient of z has absolute value at most   r+D−1 r ρ. D−1

For j ≥ D and 0 ≤ ℓ ≤ D − 1, the index r = j − 1 − ℓ lies between j − D and j − 1. Each corresponding coefficient is therefore bounded by ( j+DD−−1 2)ρ j− D . Taking the coefficient of z j−1 in N (z)/q(z) proves (15).

4.1

Proof of Theorem 1.3

We will now put everything together to obtain a proof of Theorem 1.3. To obtain the desired efficient N ab a b i iX iZ i distinguisher, will use the following stabilizer test. For x = ( a, b) ∈ F2n ii 2 , write Wx = and let S(ψ) = { x : Wx |ψ⟩ = ±|ψ⟩} be the binary subspace of Pauli stabilizer labels. Lemma 4.4 (Testing states with many stabilizers). For 19 ≤ h ≤ n − 2, a uniform polynomial-time test using 12h + 10 copies accepts every pure state with dim S(ψ) ≥ n − h with probability at least 5/8, and accepts a Haar-random state with probability at most 1/2 + 2−Ω(n) . This is the Bell-difference test in [BL26, Theorem 2 and Supplement, proof of Theorem 4]. It takes 3h + 2 Bell-difference samples and computes the subspace of their span commuting with all samples. If the subspace is nontrivial, it selects a uniform nonidentity Pauli from it, measures that Pauli on two fresh copies, and accepts if the outcomes agree; otherwise it outputs a fair bit. This gives exactly 4(3h + 2) + 2 copies, with binary linear algebra for the classical processing. Proof of Theorem 1.3. Set p = 1/m and (t)

(t)

(t)

M = Mνn = (1 − p)Mχn + pMξ n . All these moment operators fix the Haar-invariant subspace. We first show that M has a gap of (t) order 1/m outside that subspace. For v orthogonal to the image of Mµ H , write v = x + y, where (t)

x = MC v, n

(t)

y = I − MC

14

n

v.

(t)

Since I − Mξ n is positive semidefinite and has norm at most two, Lemma 4.2 gives (t)

(t)

(t)

⟨v, ( I − Mξ n )v⟩ ≥ 12 ⟨ x, ( I − Mξ n ) x ⟩ − ⟨y, ( I − Mξ n )y⟩ ≥ 2a ∥ x ∥2 − 2∥y∥2 . (t)

The first inequality follows by applying ∥u + w∥2 ≥ 12 ∥u∥2 − ∥w∥2 to ( I − Mξ n )1/2 x and ( I − (t)

Mξ n )1/2 y. Combining it with (13) gives   γ 2 2 ⟨v, ( I − M)v⟩ ≥ ap − 2p ∥y∥2 ≥ ap ∥ x ∥ + ( 1 − p ) 2 2 ∥v∥ n

(16)

for sufficiently large n, since p = Ot (n−2 ). (t) (t) On the space ker MC , the Rayleigh quotient of M is at most 1 − (1 − p)γ/n. ker MC has n n codimension at most Dt . Then, by the min-max principle at most Dt eigenvalues exceed 1 − (1 − p)γ/n, which gives M ⪰ −(1 − (1 − p)γ/n) I, so every negative eigenvalue has absolute value at most (1 − (1 − p)γ/n). (t) Consider one length-m segment and subtract its Haar moment, obtaining B = Mm − Mµ H . Equation (16) and the preceding bounds imply that all eigenvalues of B have absolute value at most ρ := e−a/2 < 1 for large n. Except for at most Dt eigenvalues, they have absolute value at most  γm  ηn = (1 − (1 − p)γ/n)m ≤ exp − . (17) 2n The Haar eigenvalues of B are zero. Choose the integer At large enough that, with d = 2n , d2t ηn ≤ e−n . Now fix any adaptive t-query algorithm AU and measurement ( MA , I − MA ), and let ΛA be   (t) the matrix from Lemma 4.1. Since B j = Mmj − Mµ H , the scalar a j = Tr Λ†A B j ∈ [−1, 1]. Split its spectral expansion as a j = u j + v j , where u j contains the contributions of the at most Dt eigenvalues of B larger than ηn in absolute value. By Lemma 4.1, j

|v j | ≤ d2t ηn ≤ e−n

( j ≥ 1).

Thus the first Dt values of u j have absolute value at most two. Moreover, u j is a sum of at most Dt j

terms bi λi with |λi | ≤ ρt . Applying Lemma 4.3 gives, for j ≥ Dt ,   Dt j + Dt − 2 | a j | ≤ 2Dt 2 ρ j − Dt + e − n . Dt − 1

(18)

We can now choose j = 3⌈log2 n⌉. Since Dt is fixed and ρt < 1, the polynomial factor in j 2 is dominated by the exponential decay. Hence | a T/m | ≤ e−2κt log n for a constant κt > 0 and sufficiently large n. The algorithm and measurement were arbitrary, so 2

δt (νn∗T , µ H ) ≤ e−2κt log n . To distinguish the walk, let J be the number of insertions among the T updates. Then J ∼ Bin( T, 1/m), E[ J ] = T/m, and the Chernoff bound gives 2

Pr[ J > 2T/m] ≤ (e/4) T/m = e−Ω(log n) . 15

(19)

Outside this event there are at most h = 2T/m = 6⌈log2 n⌉ single qubit non-Clifford gates. At a single qubit Z rotation gate on qubit i, the stabilizers commuting with Zi remain stabilizers. Commutation with Zi imposes at most one binary linear constraint on the stabilizer labels, so this subspace has codimension at most one. Using dim S(|0n ⟩) = n gives dim S(U |0n ⟩) ≥ n − h.

(20)

Prepare 12h + 10 = O(log2 n) copies of U |0n ⟩ by parallel forward queries and apply Lemma 4.4. 2 The walk acceptance is at least 5/8 − e−Ω(log n) , while Haar acceptance is at most 1/2 + 2−Ω(n) .

5

Separating higher-order unitary designs from pseudorandomness

In this section we will prove Theorem 1.4, which formally separates the notion of pseudorandom unitaries from the statistical notion of polynomial-order unitary designs.

5.1

The FB ensemble

Our construction in Theorem 1.4 is based on a product U = FB of two operators: a block-diagonal operator B that fixes the subspace span{|+⟩⊗n } while randomizing its orthogonal complement, and a diagonal phase function operator F that maps |+⟩⊗n to a phase state. For the remainder of the section, we let d = 2n denote the dimension of the Hilbert space. The phase operator. We begin by describing the phases. Identify the computational basis with the finite field Fd , using a fixed binary basis, that is, a basis of Fd as a vector space over F2 . This representation can be chosen uniformly in polynomial time by constructing a degree-n irreducible polynomial over F2 and using its polynomial basis.5 For a uniformly random seed a = ( a0 , . . . , a2t−1 ) ∈ F2t d , define 2t−1

pa (X ) = ∑ a j X j ,

f a ( x ) = trFd /F2 ( p a ( x )),

j =0

Fa = ∑ (−1) f a (x) | x ⟩⟨ x |.

(21)

x ∈Fd

j

Here trFd /F2 (z) = ∑nj=−01 z2 is the absolute field trace. The seed has 2nt bits, and Fn,t denotes the distribution of Fa . Lemma 5.1 (Statistical independence of the phases). Suppose 2t ≤ d. The signs of Fa on any set of at most 2t distinct basis labels are independent uniform elements of {+1, −1}. For every t ≥ 1, given a, the unitary Fa has an exact circuit of size poly(n, t) using clean work qubits. Moreover, its classical description is computable in poly(n, t) time. Proof. For distinct x1 , . . . , x j with j ≤ 2t, consider the map a 7−→ ( p a ( x1 ), . . . , p a ( x j )) 5 Theorem 2.2 in [Sho90] gives a deterministic algorithm with running time polynomial in the degree and the prime characteristic, which is polynomial in n here because the characteristic is fixed at two.

16

j

from F2t d to Fd . Its first j columns form a Vandermonde matrix with determinant ∏u<v ( xv − xu ) ̸ = 0. It is therefore surjective, and each output has exactly d2t− j preimages. A uniform seed consequently produces independent uniform field values at the prescribed labels. The absolute trace is an F2 -linear map into F2 . It is nonzero: its defining polynomial has degree 2n−1 < d and leading coefficient one, and so cannot vanish on every element of Fd . It follows that its two fibers both have size d/2. Applying this map to the independent field values proves sign-independence. Next, we discuss implementations. Horner’s rule uses O(t) field operations, each having Boolean complexity poly(n) in the fixed polynomial basis. The trace is binary linear. Reversibly compute f a ( x ) using CNOT and Toffoli gates, apply Z to its output bit, and uncompute. This implements | x ⟩|0⟩ 7→ (−1) f a (x) | x ⟩|0⟩ with the stated resources. ⊗n . Write N = d − 1. As an The second factor will be an explicit random circuit fixing |+⟩
idealized version, let B∞ denote the Haar ensemble on U (|+⟩⊗n )⊥ , with each unitary extended by the identity on span{|+⟩⊗n }. We use the same identity-extension convention for special unitaries on this orthogonal complement. Our concrete approach is to approximate the moments of B∞ using polynomial-depth circuits. We first analyze Fa B∞ and then replace the ideal B∞ by the finite circuit.

5.2

The FB∞ ensemble is an approximate design

We show that FB∞ fools adaptive queries by controlling collisions among computational-basis labels. The argument compares the output of any fixed query algorithm with a common reference state: both our ensemble and Haar measure contain this state as a positive component, with the missing weight bounded by a collision probability. We follow the positive-operator approach of [CSBH25, Secs. IV.2–IV.3]. For an ensemble ν on U(d), write (q)

Qν = EC∼ν (C † )⊗q Πdist(d,q) C ⊗q ,

(q)

ηq ( ν ) = ∥ I − Q ν ∥ ∞ .

ηq (ν) can be interpreted as the largest average collision probability over all inputs on q copies, and (q)

(1 − ηq (ν)) I ⪯ Qν ⪯ I. The corresponding bounds needed for B∞ and Haar measure are proved in Section A. Write (d)q = d(d − 1) · · · (d − q + 1), and |Ωh ⟩ = d−q/2 ∑ | x ⟩ X | x ⟩Y . x ∈[d]q

Let R(σ ) permute the q tensor factors according to σ ∈ Sq , and set J0 := ∑ R X (σ ) ⊗ RY (σ ). σ ∈ Sq

We denote the distinct-subspace projectors on X and Y by Π X and ΠY , respectively. Lemma 5.2 (Positive representation of adaptive queries). Fix an adaptive q-query algorithm, where 1 ≤ q ≤ d. There is a positive linear map Λ, depending only on the algorithm, such that its averaged output state under an ensemble ξ is ρξ = Λ( Jξ ), where ⊗q

Jξ = d2q EU ∼ξ (UX† )⊗q |Ωdq ⟩⟨Ωdq |UX . 17

The proof of Lemma 5.2 is standard and can be found in [CSBH25]. We give a proof consistent with the notation in Appendix C. We will also use the following reference state ρ∗ := Λ( J∗ ),

J∗ :=

dq J0 ( IX ⊗ ΠY ). (d)q

ρ∗ is a density operator depending only on the algorithm and can be viewed as the Gaussian average restricted to the distinct subspace. Moreover, the Gaussian average is related to the frame operator of the permutation basis, which approximately equals the Haar projector due to the approximate orthogonality of permutations [Har23]. The strategy of Lemma 5.3 is then to reduce the analysis to this Gaussian reference state and then exploit its explicit form. We include a proof that ρ∗ is a density operator in Section C. The proof is also contained in different notation in [CSBH25]. Define (q) (q) Qν = E (C † )⊗q Πdist(d,q) C ⊗q , ηq ( ν ) = ∥ I − Q ν ∥ ∞ . (22) C ∼ν

The quantity ηq (ν) is the maximum average collision probability over all joint inputs, including (q)

entangled inputs. Since 0 ⪯ Qν ⪯ I, it lies in [0, 1] and satisfies (q)

(1 − ηq (ν)) I ⪯ Qν ⪯ I.

(23)

For the Haar measure and polynomial q, ηq is well known to be exponentially small (see e.g. [MPSY24]) and the proof for B∞ is an elementary extension of the same argument. We include a quantitative proof of these bounds in in Section A. Lemma 5.3 (Indistinguishability from collision bounds). Let 1 ≤ q ≤ d, let F be a diagonal ensemble with 2q-wise independent signs, and let P be a uniform computational-basis permutation. Then, for every ensemble ν, δq ( F ∗ P ∗ ν, µ H ) ≤ ηq (ν) + ηq (µ H ). Proof. Fix a query algorithm and use Lemma 5.2. For a fixed distinct tuple x, the tuple P−1 x is uniform over the (d)q distinct tuples. Hence J F ∗ P ( Π X ⊗ ΠY ) =

dq J0 (Π X ⊗ ΠY ). (d)q

(24)

† )⊗q and averaging over C ∼ ν yields Conjugating by (CX

J F ∗ P ∗ ν ⪰ ( IX ⊗ ΠY ) J F ∗ P ∗ ν ( IX ⊗ ΠY ) dq (q) = J0 ( Qν ⊗ ΠY ) (d)q

⪰ (1 − ηq (ν)) J∗ .

(25) (26) (27)

Here, the last inequality holds by (23). Applying the positive map Λ gives ρ F∗ P∗ν ⪰ (1 − ηq (ν))ρ∗ . Since both states have trace one, this implies 1 ∥ ρ F ∗ P ∗ ν − ρ ∗ ∥1 ≤ ηq ( ν ). 2 Taking C Haar random gives the same comparison with error ηq (µ H ), because FPC is then Haar random. The lemma then follows from applying the triangle inequality. 18

We now apply the criterion to the fixed-vector ensemble. Lemma 5.4 (Indisinguishability for FB∞ ). For 1 ≤ q ≤ t and 2t ≤ d, the phase ensemble Fn,t from Section 5.1 satisfies q ( q − 1) q ( q − 1) 2q(q − 1) δq ( Fn,t ∗ B∞ , µ H ) ≤ + ≤ . d d+1 d Proof. Every computational-basis permutation fixes |+⟩⊗n , so PB∞ has the same distribution as B∞ . The phases are 2q-wise independent by Lemma 5.1. Apply Lemma 5.3 and the collision bounds of Lemma A.2.

5.3

Learning the planted phase state

Here, we will prove the following lemma: Lemma 5.5. Any ensemble of the form FB with F is a random phase drawn as Fa in Section 5.1 and B leaving the |+n ⟩ state invariant can be distinguished from Haar in polynomial time using parallel queries. Every forward query on |+⟩⊗n produces the same phase state. We learn this state by extracting relative phases, each of which gives a linear constraint on its seed. 5.3.1

Relative-phase measurements and recovery

We use the derivative measurement of Arunachalam, Bravyi, Dutt, and Yoder [ABDY23, Definition 1], with a change of binary coordinates to randomize its direction. Lemma 5.6 (Derivative sampling). Let d = 2n , n ≥ 1, and f : Fd → F2 . For every integer J ≥ 1, a quantum procedure using at most one copy of |ψ f ⟩ = d−1/2 ∑ x (−1) f (x) | x ⟩ and poly(n, J ) operations either aborts, with probability d− J , or returns a uniform unordered distinct pair { x, y} and the bit f ( x ) + f (y). Proof. Sample J independent uniform Fd elements and take the first nonzero one as h, and abort if all are zero, which happens with probability d− J . Since h ̸= 0, it extends to a binary basis h, h2 , . . . , hn of Fd . Every x ∈ Fd is then uniquely of the form x = bh + yz with b ∈ F2 , z = (z2 , . . . , zn ) ∈ F2n−1 , and yz = ∑in=2 zi hi . Gaussian elimination finds the coordinate map bh + yz 7→ (b, z), which is invertible and F2 -linear on n-bit strings and is therefore implemented by O(n2 ) CNOT gates. After this change of coordinates, measure the last n − 1 qubits in the computational basis. Each outcome z has probability 2/d, and the remaining qubit is

(−1) f (yz ) |0⟩ + (−1) f (yz +h) |1⟩ √ . 2 Measuring it in the X basis alway gives f (yz ) + f (yz + h). Return {yz , yz + h} and f (yz ) + f (yz + h). Every distinct pair { x, y} has exactly one direction h = x + y and one coset for that direction. Its probability is therefore (d − 1)−1 (2/d) = (d2) performed before using the input copy.

−1

. All preprocessing takes polynomial time and is

For the analysis, write p a ( X ) = ∑ Lj=−01 a j X j and f a ( x ) = trFd /F2 ( p a ( x )), for L = 2t. Different seeds can represent the same trace function, and a constant difference changes the state only by a global sign. All other differences are separated by the following estimate. 19

Lemma 5.7 (Separation of the phase family). Let d = 2n ≥ 16 and 2 ≤ L ≤ d1/4 . If a, a′ ∈ FdL and g = f a + f a′ is nonconstant, then a uniform unordered distinct pair satisfies Pr[ f a ( x ) + f a (y) = f a′ ( x ) + f a′ (y)] ≤

5 . 8

Proof. We use the additive-character Weil √ bound in characteristic two: if P ∈ Fd [ X ] has odd degree e, then6 | ∑ x∈Fd (−1)tr( P(x)) | ≤ (e − 1) d. To meet the degree hypothesis, we first remove the even n exponents from p a + p a′ without changing its trace. Frobenius invariance of the trace and x2 = x give     tr(cx2m ) = tr (cx2m )2

n −1

= tr c2

n −1

xm .

Repeatedly apply this identity to each even nonconstant exponent and collect equal powers. The resulting polynomial P has degree less than L, only odd nonconstant exponents, and g( x ) = tr( P( x )). Since g is nonconstant, P has positive odd degree e. The Weil bound applied to P thus gives, for µ g = d−1 ∑ x (−1) g(x) , √ √ |µ g | ≤ (e − 1)/ d ≤ ( L − 2)/ d ≤ d−1/4 ≤ 12 . It remains to pass from single values of g to pairs. Since the sums are in F2 , the event f a ( x ) + f a (y) = f a′ ( x ) + f a′ (y) is exactly the event g( x ) = g(y). Set s x = (−1) g(x) ∈ {±1}, so that 1g(x)= g(y) = (1 + s x sy )/2. We sum over all ordered pairs gives ∑ x,y s x sy = (∑ x s x )2 = d2 µ2g , and each of the d diagonal terms is s2x = 1, so ∑ x̸=y s x sy = d2 µ2g − d. Averaging over the d(d − 1) ordered pairs with x ̸= y, which induces the uniform distribution on unordered distinct pairs, yields ! dµ2g − 1 1 + µ2g 1 5 Pr [ g( x ) = g(y)] = 1+ ≤ ≤ , 2 d−1 2 8 x ̸=y where the first inequality is equivalent to µ2g ≤ 1 and the second uses |µ g | ≤ 12 . Proposition 5.8 (Learning up to global phase). Let d = 2n ≥ 16 and 2 ≤ L ≤ d1/4 . For every 0 < δ < 1, a uniform quantum algorithm uses at most K = O(nL + log(1/δ)) copies of |ψa ⟩ and returns b a ∈ FdL with |ψba ⟩ = ±|ψa ⟩ with probability at least 1 − δ. Its worst-case running time is poly(n, L, log(1/δ)). On arbitrary inputs it either reports failure or returns a seed from this same family. Proof. Fix the binary basis e1 , . . . , en of Fd and write a j = ∑nℓ=1 a jℓ eℓ . Apply Lemma 5.6 independently to the copies, using J = ⌈log(2K/δ)/ log d⌉ trials per direction and reporting failure on any abort. The probability of an abort is at most Kd− J ≤ δ/2. Conditional on not aborting, the resulting pairs remain independent and uniform. Each sample ( xi , yi , bi ) gives the binary linear equation L −1 n

  j j a tr e ( x + y ) ∑ ∑ j ℓ ℓ i i = bi .

j=0 ℓ=1

6 This is the case p = 2 of Theorem 5.38 in [LN97], applied to the character z 7 → (−1)tr(z) , which is nontrivial because

the trace is surjective.

20

Form their matrix W ∈ F2K×nL and solve Wb a = b by Gaussian elimination, identifying seeds with their binary coordinate vectors. Reject an inconsistent system and otherwise return any solution. Field arithmetic computes every entry of W in polynomial time. On the promised input the solution set is a + ker W. Every row annihilates the binary subspace {c ∈ FdL : f c is constant}, whereas Lemma 5.7 implies that any fixed c ∈ FdL with f c nonconstant is annihilated by all K independent rows with probability at most (5/8)K . Hence

∑

Pr[ker W ̸= {c ∈ FdL : f c is constant}] ≤

Pr[Wc = 0] ≤ 2nL (5/8)K ≤ δ/2.

c∈FdL f c nonconstant

Otherwise every solution is b a = a + c for some c ∈ FdL with f c constant, and |ψba ⟩ = (−1) f c (0) |ψa ⟩. Adding the abort probability gives total failure at most δ.

5.4

Proof of Theorem 1.4

We are now in a position to replace the B∞ ensemble by an approximate t-design in the fixed-vector subpsace. This will conclude the proof of Theorem 1.4. We use the machinery from [ABH+ 26]. For a compact group G and a subset S ⊆ G, the Kazhdan constant is

K( G; S) = inf inf sup ∥ρ( g)v − v∥, ρ ∥v∥=1 g∈S

where ρ ranges over continuous unitary representations of G with no nonzero invariant vectors, and v lies in the representation space. Generating sets are understood to generate G topologically. We will use multiple standard results about Kazhdan constants (compare [Kas07]): Lemma 5.9 (Bounding the largest eigenvalue with the Kazhdan constant [CHH+ 24, Lemma 2.17]). Let G be a compact group (finite or Lie) topologically generated by a finite subset S which is closed under taking inverses. Then for any finite-dimensional continuous unitary representation ρ of G, ! K( G; S)2 1 ρ ( g ) − Eν ∼ µ ( G ) ρ ( ν ) ≤ 1 − λmax , (28) ∑ 2 |S| | S | g∈S where λmax (·) denotes the largest eigenvalue. If S contains the identity, then Equation (28) holds with λmax (·) replaced with the operator norm ∥·∥. Moreover, we will use the following reduction lemma: Lemma 5.10 ([Kas07]). Let Hi be subgroups of G and Si ⊆ Hi . Then, we have ! ! [ [ 1 K G; Si ≥ K G; Hi inf K ( Hi ; Si ) . 2 i i i

(29)

Finally, we use the main result from [ABH+ 26] (see also [BH26]): Theorem 5.11. There is a set of unitaries S = {V1 , ...V25 } on n qubits such that each Vj is a constant depth circuit and S has a uniformly lower bounded Kazhdan constant in SU(2n ). 21

The aim of this
section will be to combine these ingredients with the following decomposition ⊗ n ⊥ of SU (|+⟩ ) that we prove in Appendix B. Lemma 5.12. Let n ≥ 1, for i ∈ {1, . . . , n} and V ∈ SU(2n−1 ), write Ci (V ) = |+⟩⟨+|i ⊗ I + |−⟩⟨−|i ⊗ V, (30)
where V acts on all qubits other than i. Every U ∈ SU (|+⟩⊗n )⊥ admits a factorization into 2n − 1 such gates, U = C1 (U1 ) · · · Cn−1 (Un−1 )Cn (Un )Cn−1 (Un+1 ) · · · C1 (U2n−1 ). (31) We will now complete the proof of Theorem 1.4. √ Proof of Theorem 1.4. Define Hi := Ci (SU(2n−1 )). As K( G; G ) ≥ 2 [Kas07] for any compact
S −1 group G, we can apply the short-product lemma [CHH+ 24] to obtain that K(SU (|+⟩⊗n )⊥ ; 2n j =1 H j ) = − 1 Ω(n ) (where we identify n + j with n − j). We can then apply Lemma 5.10 for the sets S j := C j (S). As C j (S) has a uniformly lower bounded Kazhdan constant in C j (SU(2n−1 )) by Theorem 5.11, the finite inverse-closed generating set Putting everything together.

Ŝ := { I } ∪

n [

1 (S j ∪ S− j )

j =1

contains the identity and satisfies K(SU (|+⟩⊗n )⊥ , Ŝ) = Ω(n−1 ) with |Ŝ| = O(n). Finally, for the spectral gap of the uniform probability distribution on this generator set that yields ∆ = Ω(n3 ) by Lemma 5.9. Denote by νŜ the uniform probability distribution over elements in Ŝ. The gap can be easily amplified by taking νŜ∗r to yield ε-approximate designs in depth r = O( ∆1 (2nt + log(1/ε))) = O(n3 (2nt + log(1/ε)) (see e.g. [BHH16]). In particular, choosing ε = e−n we end up with polynomially deep circuits. We can then plug Br := νŜ∗r into the position of B∞ in FB∞ . As FB∞ is indistinguishable from Haar for polynomial t by Lemma 5.4 and νŜ∗r is indistinguishable from B∞ using t copies via the above we obtain the desired construction. In particular, the ensemble is over circuits of polynomial depth for every fixed polynomial t = poly(n) it yields an approximate t-design. However, because of Lemma 5.5 the ensemble can be efficiently distinguished from Haar. This means, the ensemble fails to be pseudorandom according to Definition 3.2. This completes the proof of Theorem 1.4.

6

Pseudorandomness and Maximal Scrambling

In this section, we explore how genuine pseudorandomness can emerge in simple quantum processes by drawing on an explicit connection to many-body physics. Local random quantum circuits are among the simplest models of time-dependent quantum dynamics, where information initially stored in a small subsystem spreads globally through interactions with the rest of the system. This process, known as scrambling, is closely related to thermalization: as information spreads, it becomes increasingly difficult to recover from local observations [HP07, LLZZ18]. For local random circuits, matching progressively higher moments of the Haar measure requires increasing circuit depth [BHH16], making the unitary design order a natural way to describe how randomness develops over time. 22

Design order Haar-like entropies t = Θ(n)

Max-scrambling

··· 3 2

Min-scrambling

1

Figure 3: The hierarchy of scrambling and unitary design order, following [LLZZ18]. At t = Θ(n), moment matching achieves a saturation via near-maximal expected min-entropy across a fixed balanced crossed cut, and hence near-maximal expected entropies at every positive Rényi order. Liu, Lloyd, Zhu, and Zhu [LLZZ18] showed that higher and higher moment matching (in the form of unitary t-designs) implies a saturation in the hierarchy of entanglement entropies. Eventually, this process reaches a limit: when t = Θ(n) all entanglement entropies are saturated, which is known as maximal scrambling (see Figure 3). At this point, the system appears effectively thermal: initially localized information has fully dispersed and becomes inaccessible to local probes. Maximal scrambling therefore suggests a physically motivated regime in which moment matching might be sufficient for genuine pseudorandomness. Once all these entanglement entropies have saturated, it seems plausible that an efficient observer should have little remaining structure to exploit. There is a closely related intuition behind the HMMR conjecture and the design of block ciphers: diffusion spreads changes in a few input bits across many output bits, while sufficiently strong statistical independence limits the correlations exploited by differential and linear attacks [HMMR05, BS15]. Connections between these attacks and scrambling have also been studied quantitatively [CMR22]. In the quantum setting, this motivates the following question: Does maximal scrambling imply computational pseudorandomness? Our results suggest caution; they show that the answer is still no, at least in the general case. As a byproduct of our separation between unitary designs and pseudorandom unitaries in Theorem 1.4, we find that the FB ensemble can yield an (approximate) unitary t-design in the maximal scrambling regime t = Θ(n), and still admit enough structure to be efficiently distinguishable from Haar. This means that maximally scrambled systems need not, in general be pseudorandom. To state this more precisely, let n be even and divide both the input reference AB and the output CD into equal halves. We can associate each unitary U with its normalized Choi state

|U ⟩ ABCD = 2−n/2

∑ | x⟩ AB ⊗ U |x⟩CD ,

(32)

x ∈{0,1}n

and let ρ AC (U ) = TrBD (|U ⟩⟨U |). Entanglement across AC : BD measures how the input subsystems have been mixed among the output subsystems. The min-entropy Smin (ρ) = − log2 ∥ρ∥∞ has maximal value n for this reduced state.

23

Using Theorem 1.4 and the results in [LLZZ18], we can conclude the following7 : there exists a polynomial-depth circuit ensemble ensemble ν = {νn } that forms an approximate unitary t-design with t = Θ(n) and sufficiently small error such that, for sufficiently large even n,
E Smin ρ AC (U ) ≥ n − 8 U ∼νn

for every fixed balanced crossed cut AC : BD. Nevertheless, an efficient quantum algorithm can distinguish ν from Haar measure with constant advantage using O(n2 ) forward queries. To obtain this result, it suffices to use the FB construction with t = Θ(n) and choose the mixing circuit B deep enough to control Choi moments of order ∼ 4n. This gives the expected min-entropy bound above. Importantly, increasing the depth of B preserves the relation U |+⟩⊗n = F |+⟩⊗n , so the same phase-learning algorithm continues to distinguish the ensemble. Thus the ensemble exhibits near-maximal entanglement entropies while preserving algebraic structure that an efficient observer can learn. This suggests some caution when using unitary designs to model scrambling in many-body physics and black-hole evolution [HP07, LLZZ18, PRV26], as even maximally scrambled systems can exhibit non-trivial structure which is accessible to efficient experiments. Moreover, it suggests that pseudorandomness can serve as much more reliable proxy for Haar randomness, providing a new frontier for complexity beyond maximal scrambling. At the same time, our results suggest a new conjecture for how pseudorandomness may very well emerge in simple quantum processes. Matching moments up to t = Θ(n) has a clear physical motivation through maximal scrambling, and our separation at this order relies on a artificial non-local structured ensemble. This leaves open a promising intermediate regime, where we retain the structure of independent local interactions to ensure some amount of "simplicity" while also matching the statistical moments up to the maximal scrambling scale. Motivated by these principles, we therefore put forward the following new conjecture. Conjecture 6.1 (Pseudorandomness in the Maximal Scrambling Regime). Let {νn }n be an efficiently samplable ensemble of local quantum gates on n qubits, and let νn∗T denote the ensemble obtained by independently composing T = poly(n) gates drawn from νn . If {νn∗T }n forms an approximate unitary t-design for t = Θ(n) with negligible error, then {νn∗T }n is a pseudorandom unitary ensemble. As in the quantum HMMR conjecture, each gate acts non-trivially on only a constant number of qubits, and the distribution νn may depend on n. Importantly, neither of our counterexamples applies to this setting: the near-Clifford argument establishes designs only at fixed constant order, and the FB ensemble uses a separate, artificial phase circuit and a structured nonlocal mixing. Known results on local random quantum circuits already give polynomial-depth designs at t = Θ(n) [BHH16]. Haferkamp and Hunter-Jones [HJH26] recently showed that their outcome probabilities become uniformly small at order t = Θ(n), which can be seen as further evidence for this threshold. More generally, it suggests studying growing-order independence in local reversible circuits as a possible way to make progress beyond the classical HMMR counterexamples. We hope that the study of this connection to scrambling and entanglement saturation provides a new research direction for the Gowers conjecture in both the classical and the quantum setting. 7 Technically, the entropy saturation results for t = Θ ( n ) in [LLZZ18] only hold for exact unitary t-designs; however,

we found that the argument can be extended to our approximate designs as the error is negligibly small.

24

References [ABDY23]

Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt, and Theodore J. Yoder. Optimal algorithms for learning quantum phase states, 2023.

[ABH+ 26]

Anurag Anshu, Shankar Balasubramanian, Jonas Haferkamp, Aram W Harrow, and Xinyu Tan. Depth-1 expanders on the unitary group and applications. arXiv preprint arXiv:2609.01605, 2026.

[AGKL24]

Prabhanjan Ananth, Aditya Gulati, Fatih Kaleoglu, and Yao-Ting Lin. Pseudorandom isometries. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 226–254. Springer, 2024.

[AGL+ 23]

Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, and Umesh Vazirani. A polynomial-time classical algorithm for noisy random circuit sampling. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC ’23, page 945–957. ACM, 2023.

[BCFM00]

Andrei Z. Broder, Moses Charikar, Alan M. Frieze, and Michael Mitzenmacher. Minwise independent permutations. Journal of Computer and System Sciences, 60(3):630– 659, 2000.

[BH26]

Tim Baer and Jeongwan Haah. Random unitary circuits with constant spectral gap, 2026.

[BHH16]

Fernando G. S. L. Brandão, Aram W. Harrow, and Michał Horodecki. Local random quantum circuits are approximate polynomial-designs. Communications in Mathematical Physics, 346(2):397–434, August 2016.

[BHHP24]

John Bostanci, Jonas Haferkamp, Dominik Hangleiter, and Alexander Poremba. Efficient quantum pseudorandomness from hamiltonian phase states, 2024.

[BL26]

Lennart Bittel and Lorenzo Leone. Adaptively secure unitary designs with constant non-clifford cost. Phys. Rev. Lett., 136:210802, May 2026.

[BNRT20]

Eiichi Bannai, Gabriel Navarro, Noelia Rizo, and Pham Huu Tiep. Unitary t-groups. Journal of the Mathematical Society of Japan, 72(3):909–921, 2020.

[BS15]

Dan Boneh and Victor Shoup. A Graduate Course in Applied Cryptography. 2015.

[BS19]

Zvika Brakerski and Omri Shmueli. (pseudo) random quantum states with binary phase, 2019.

[Cam99]

Peter J Cameron. Permutation groups, volume 45. Cambridge University Press Cambridge, 1999.

[CCMR25]

Ran Canetti, Claudio Chamon, Eduardo R Mucciolo, and Andrei E Ruckenstein. Towards general-purpose program obfuscation via local mixing. In Theory of Cryptography Conference, pages 37–70. Springer, 2025.

25

[CDX+ 24]

Chi-Fang Chen, Jordan Docter, Michelle Xu, Adam Bouland, Fernando G.S.L. Brandão, and Patrick Hayden. Efficient unitary designs from random sums and permutations. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), page 476–484. IEEE, October 2024.

[CEG+ 26]

Jose Carrasco, Jens Eisert, Soumik Ghosh, Dominik Hangleiter, Nicky Kai Hong Li, and Ryan Sweke. Instantiating microcrypt: Obstacles and opportunities via tailored state certification, 2026.

[CHH+ 24]

Chi-Fang Chen, Jeongwan Haah, Jonas Haferkamp, Yunchao Liu, Tony Metger, and Xinyu Tan. Incompressibility and spectral gaps of random circuits, 2024.

[CHH+ 25]

Chi-Fang Chen, Jeongwan Haah, Jonas Haferkamp, Yunchao Liu, Tony Metger, and Xinyu Tan. Incompressibility and spectral gaps of random circuits. In 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS), pages 1304–1312. IEEE, 2025.

[CLLW15]

Richard Cleve, Debbie Leung, Li Liu, and Chunhao Wang. Near-linear constructions of exact unitary 2-designs. arXiv preprint arXiv:1501.04592, 2015.

[CLZ26]

Ran Canetti, Ji Luo, and Yiding Zhang. How to encrypt with random reversible circuits: Functional, homomorphic and cca-secure. In Annual International Cryptology Conference, pages 539–580. Springer, 2026.

[CMR22]

Claudio Chamon, Eduardo R. Mucciolo, and Andrei E. Ruckenstein. Quantum statistical mechanics of encryption: Reaching the speed limit of classical block ciphers. Annals of Physics, 446:169086, 2022.

[CSBH25]

Laura Cui, Thomas Schuster, Fernando G. S. L. Brandão, and Hsin-Yuan Huang. Unitary designs in nearly optimal depth, 2025.

[CSM+ 25]

Laura Cui, Thomas Schuster, Liang Mao, Hsin-Yuan Huang, and Fernando Brandao. Random unitaries from hamiltonian dynamics, 2025.

[DCEL09]

Christoph Dankert, Richard Cleve, Joseph Emerson, and Etera Livine. Exact and approximate unitary 2-designs and their application to fidelity estimation. Physical Review A—Atomic, Molecular, and Optical Physics, 80(1):012304, 2009.

[DM96]

John D. Dixion and Brian Mortimer. Permutation groups. Springer New York, 1996.

[DPT25]

Jesko Dujmovic, Angelos Pelecanos, and Stefano Tessaro. When simple permutations mix poorly: Limited independence does not imply pseudorandomness. Cryptology ePrint Archive, Paper 2025/2282, 2025.

[FGSY25]

Bill Fefferman, Soumik Ghosh, Makrand Sinha, and Henry Yuen. The hardness of learning quantum circuits and its cryptographic applications, 2025.

[FGSY26]

Bill Fefferman, Soumik Ghosh, Makrand Sinha, and Henry Yuen. The Hardness of Learning Quantum Circuits and Its Cryptographic Applications. In Shubhangi Saraf, editor, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026), 26

volume 362 of Leibniz International Proceedings in Informatics (LIPIcs), pages 56:1–56:21, Dagstuhl, Germany, 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. [FLM+ 26]

Ben Foxman, Alex Lombardi, Fermi Ma, Barak Nehoran, and John Wright. Quantum lazy sampling and path recording for any group, 2026.

[GAE07]

David Gross, Koenraad Audenaert, and Jens Eisert. Evenly distributed unitaries: On the structure of unitary designs. Journal of mathematical physics, 48(5), 2007.

[GHKO25]

William Gay, William He, Nicholas Kocurek, and Ryan O’Donnell. Pseudorandomness properties of random reversible circuits, 2025.

[GIKL24]

Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang. Improved stabilizer estimation via bell difference sampling. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1352–1363, 2024.

[GKT26]

Aditya Gulati, Dakshita Khurana, and Kabir Tomer. How not to build microcrypt, 2026.

[GNW21]

David Gross, Sepehr Nezami, and Michael Walter. Schur–weyl duality for the clifford group with applications: Property testing, a robust hudson theorem, and de finetti representations. Communications in Mathematical Physics, 385(3):1325–1393, 2021.

[Gow96]

W. T. Gowers. An almost m-wise independent random permutation of the cube. Combinatorics, Probability and Computing, 5(2):119–130, 1996.

[Gow13]

Timothy Gowers. How not to prove that p is not equal to np. Gowers’s Weblog, October 2013. Accessed: 2026-07-08.

[GVL13]

Gene H Golub and Charles F Van Loan. Matrix computations, volume 3. JHU press, 2013.

[Haa33]

Alfréd Haar. Der maßbegriff in der theorie der kontinuierlichen gruppen. Annals of Mathematics, 34(1):147–169, 1933.

[Haf22]

Jonas Haferkamp. Random quantum circuits are approximate unitary t-designs in depth o(nt5+o(1)). Quantum, 6:795, 2022.

[Har13]

Aram W Harrow. The church of the symmetric subspace. arXiv:1308.6595, 2013.

[Har23]

Aram W Harrow. Approximate orthogonality of permutation operators, with application to quantum information. Letters in Mathematical Physics, 114(1):1, 2023.

[HH24]

Taiga Hiroka and Min-Hsiu Hsieh. Computational complexity of learning efficiently generatable pure states, 2024.

[HJH26]

Nicholas Hunter-Jones and Jonas Haferkamp. Ideal random quantum circuits pass the lxeb test, 2026.

[HM25]

Taiga Hiroka and Tomoyuki Morimae. Quantum Cryptography and Meta-Complexity, page 545–574. Springer Nature Switzerland, 2025. 27

arXiv preprint

[HMMH+ 23] Jonas Haferkamp, Felipe Montealegre-Mora, Markus Heinrich, Jens Eisert, David Gross, and Ingo Roth. Efficient unitary designs with a system-size independent number of non-Clifford gates. Communications in Mathematical Physics, 397:995–1041, 2023. [HMMR05]

Shlomo Hoory, Avner Magen, Steven Myers, and Charles Rackoff. Simple permutations mix well. Theoretical Computer Science, 348:251–261, 2005.

[HP07]

Patrick Hayden and John Preskill. Black holes as mirrors: quantum information in random subsystems. Journal of High Energy Physics, 2007(09):120, September 2007.

[JLS18]

Zhengfeng Ji, Yi-Kai Liu, and Fang Song. Pseudorandom quantum states. In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology – CRYPTO 2018, pages 126–152, Cham, 2018. Springer International Publishing.

[Kas07]

Martin Kassabov. Symmetric groups and expander graphs. Inventiones mathematicae, 170(2):327–354, 2007.

[KKSZ26]

Ágoston Kaposi, Zoltán Kolarovszki, Adrian Solymos, and Zoltán Zimborás. Generalized group designs: constructing novel unitary 2-, 3- and 4-designs. Quantum, 10:2008, February 2026.

[KP23]

Isaac H. Kim and John Preskill. Complementarity and the unitarity of the black hole S-matrix. Journal of High Energy Physics, 2023(2), February 2023.

[Kre21]

William Kretschmer. Quantum Pseudorandomness and Classical Complexity. In Min-Hsiu Hsieh, editor, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021), volume 197 of Leibniz International Proceedings in Informatics (LIPIcs), pages 2:1–2:20, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.

[KT24]

Dakshita Khurana and Kabir Tomer. Founding quantum cryptography on quantum advantage, or, towards cryptography from #p-hardness, 2024.

[LLZZ18]

Zi-Wen Liu, Seth Lloyd, Elton Zhu, and Huangjun Zhu. Entanglement, quantum randomness, and complexity beyond scrambling. Journal of High Energy Physics, 2018(7), 2018.

[LN97]

Rudolf Lidl and Harald Niederreiter. Finite fields. Number 20. Cambridge university press, 1997.

[LQS+ 24]

Chuhan Lu, Minglong Qin, Fang Song, Penghui Yao, and Mingnan Zhao. Quantum pseudorandom scramblers. Cryptology ePrint Archive, Paper 2024/1470, 2024.

[LR88]

Michael Luby and Charles Rackoff. How to construct pseudorandom permutations from pseudorandom functions. SIAM Journal on Computing, 17(2):373–386, 1988.

[LSH+ 13]

Nima Lashkari, Douglas Stanford, Matthew Hastings, Tobias Osborne, and Patrick Hayden. Towards the fast scrambling conjecture. Journal of High Energy Physics, 2013(4), April 2013. 28

[MCSH25]

Liang Mao, Laura Cui, Thomas Schuster, and Hsin-Yuan Huang. Random unitaries that conserve energy, 2025.

[Mel24]

Antonio Anna Mele. Introduction to Haar Measure Tools in Quantum Information: A Beginner’s Tutorial. Quantum, 8:1340, May 2024.

[MH25]

Fermi Ma and Hsin-Yuan Huang. How to construct random unitaries. In Proceedings of the 57th Annual ACM symposium on theory of computing, pages 806–809, 2025.

[Mon17]

Ashley Montanaro. Learning stabilizer states by Bell sampling, 2017.

[MOP20]

Sidhanth Mohanty, Ryan O’Donnell, and Pedro Paredes. Explicit near-ramanujan graphs of every degree. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 510–523, 2020.

[MPSY]

Tony Metger, Alexander Poremba, Makrand Sinha, and Henry Yuen. Simple constructions of linear-depth t-designs and pseudorandom unitaries. IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS 2024).

[MPSY24]

Tony Metger, Alexander Poremba, Makrand Sinha, and Henry Yuen. Simple Constructions of Linear-Depth t-Designs and Pseudorandom Unitaries . In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 485–492, Los Alamitos, CA, USA, October 2024. IEEE Computer Society.

[NC01]

Michael A Nielsen and Isaac L Chuang. Quantum Computation and Quantum Information, volume 2. Cambridge university press Cambridge, 2001.

[PRV26]

Alexander Poremba, Seyoon Ragavan, and Vinod Vaikuntanathan. Cloning Games, Black Holes and Cryptography. In Shubhangi Saraf, editor, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026), volume 362 of Leibniz International Proceedings in Informatics (LIPIcs), pages 109:1–109:21, Dagstuhl, Germany, 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.

[REF26]

Asad Raza, Jens Eisert, and Bill Fefferman. Distinctness threshold for pseudorandom unitaries. arXiv preprint arXiv:2609.03065, 2026.

[RY17]

Daniel A. Roberts and Beni Yoshida. Chaos and complexity by design. Journal of High Energy Physics, 2017(4), April 2017.

[SHH25]

Thomas Schuster, Jonas Haferkamp, and Hsin-Yuan Huang. Random unitaries in extremely low depth. Science, 389(6755):92–96, 2025.

[Sho90]

Victor Shoup. New algorithms for finding irreducible polynomials over finite fields. Mathematics of computation, 54(189):435–447, 1990.

[Sim96]

Barry Simon. Representations of finite and compact groups. Number 10. American Mathematical Soc., 1996.

[SKYH25]

Thomas Schuster, Dominik Kufel, Norman Y Yao, and Hsin-Yuan Huang. Hardness of recognizing phases of matter. arXiv preprint arXiv:2510.08503, 2025. 29

[SML+ 25]

Thomas Schuster, Fermi Ma, Alex Lombardi, Fernando Brandao, and Hsin-Yuan Huang. Strong random unitaries and fast scrambling. arXiv preprint arXiv:2509.26310, 2025.

[Tho13]

Mikkel Thorup. Bottom-k and priority sampling, set similarity and subset sums with minimal independence. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing, pages 371–380. ACM, 2013.

[Web16]

Zak Webb. The clifford group forms a unitary 3-design, 2016.

[ZKGG16]

Huangjun Zhu, Richard Kueng, Markus Grassl, and David Gross. The clifford group fails gracefully to be a unitary 4-design. arXiv preprint arXiv:1609.08172, 2016.

A

Bounds on the collision probability

For q ≤ d, recall the definitions (q)

Qν = E (C † )⊗q Πdist(d,q) C ⊗q , C ∼ν

(q)

ηq ( ν ) = ∥ I − Q ν ∥ ∞ .

(33)

The quantity ηq (ν) is the maximum average collision probability over all joint inputs, including (q)

entangled inputs. Since 0 ⪯ Qν ⪯ I, it lies in [0, 1] and satisfies (q)

(1 − ηq (ν)) I ⪯ Qν ⪯ I.

(34)

We will use the following standard consequence of the Schur–Weyl duality (see e.g. [Har13]). Lemma A.1 (Two-copy symmetric twirl). For N ≥ 1, let Πsym project onto the symmetric subspace of (C N )⊗2 . If X = Πsym XΠsym , then E V ⊗2 X ( V † ) ⊗2 =

V ∼µ H

Tr X Πsym . N ( N + 1)/2

(35)

Lemma A.2 (Collision probability). For d = 2n , n ≥ 1, and 1 ≤ q ≤ d, Haar measure β ∞ on the group fixing |+⟩⊗n satisfies q ( q − 1) q ( q − 1) ηq ( β ∞ ) ≤ , ηq ( µ H ) ≤ . (36) d d+1 The Haar bound also holds in every integer dimension D ≥ 2, with d replaced by D. Proof. Let Π= = ∑ x | x, x ⟩⟨ x, x |, S = span{|+⟩⊗n }, and N = d − 1. The vectors |k x ⟩ = | x ⟩ − d−1/2 |+⟩⊗n satisfy ∑ x |k x ⟩⟨k x | = I(|+⟩⊗n )⊥ and ∥k x ∥2 = 1 − 1/d. Moreover,

| x, x ⟩ =

1 1 |+⟩⊗2n + √ |+⟩⊗n ⊗ |k x ⟩ + |k x ⟩ ⊗ |+⟩⊗n + |k x ⟩⊗2 . d d

(37)

The subgroup acts as 1 ⊕ V on S ⊕ (|+⟩⊗n )⊥ . Averaging over its central phases 1 ⊕ eiθ I(|+⟩⊗n )⊥ removes cross terms between the three displayed summands. On S ⊗2 the averaged collision

30

operator has eigenvalue 1/d. On (S ⊗ (|+⟩⊗n )⊥ ) ⊕ ((|+⟩⊗n )⊥ ⊗ S), identified with C2 ⊗ (|+⟩⊗n )⊥ , it is   1 1 1 ⊗ I(|+⟩⊗n )⊥ , d 1 1
⊗2 which is already invariant and has norm 2/d. On (|+⟩⊗n )⊥ , Lemma A.1 gives a multiple of the symmetric projector with coefficient 2 2( d − 1) ∑ x ∥ k x ∥4 ≤ . = 2 N ( N + 1)/2 d d Hence † ⊗2 ⊗2 E ( B∞ ) Π= B∞ ⪯

B∞ ∼ β ∞

2 I. d

(38)

For full Haar measure, Π= has symmetric support and trace d, so the same lemma gives 2Πsym /(d + (i,j)

1). Finally, I − Πdist(d,q) ⪯ ∑i< j Π= , with identities on the other copies: every nondistinct tuple has an equal pair. Conjugating and averaging this inequality, then summing the (2q) two-copy bounds, proves both assertions. For q = 1 the sum is empty.

B

Proof of Lemma 5.12

Lemma B.1 (Controlled decomposition of fixed-vector special unitaries). For i ∈ {1, . . . , n} and V ∈ U(2n−1 ), write Ci (V ) = |+⟩⟨+|i ⊗ I + |−⟩⟨−|i ⊗ V,
where V acts on all qubits other than i. Every U ∈ SU (|+⟩⊗n )⊥ admits a factorization U = C1 ( L1 ) · · · Cn−1 ( Ln−1 )Cn (Vn )Cn−1 ( Rn−1 ) · · · C1 ( R1 ), with all Lk , Rk , Vn ∈ SU(2n−1 ). Proof. We first work in the computational basis, writing (Z)

Ci Define

(V ) = |0⟩⟨0|i ⊗ I + |1⟩⟨1|i ⊗ V.

Fk = (C2 )⊗(k−1) ⊗ span{|0n−k+1 ⟩}.

We show that any Mk ∈ SU(2n ) fixing Fk pointwise can be written as (Z)

(Z)

Mk = C k ( L k ) Mk + 1 C k ( R k ) , where Lk , Rk ∈ SU(2n−1 ) and Mk+1 ∈ SU(2n ) fixes Fk+1 pointwise. For k < n, let Ak be the subspace with qubit k equal to 1, and let Dk be the subspace with qubit k equal to 0 and ( xk+1 , . . . , xn ) ̸= 0n−k . Then Fk⊥ = Ak ⊕ Dk . Write Ak = Ek ⊕ A′k , where Ek = (C2 )⊗(k−1) ⊗ span{|1⟩|0n−k ⟩}.

31

We have dim Ek = 2k−1 and dim A′k = dim Dk = 2n−1 − 2k−1 > 0. The cosine–sine decomposition [GVL13], with the identity block placed on Ek , gives   IEk 0 0 e k ⊕ Q k ), Mk F ⊥ = ( e Lk ⊕ Pk )  0 C −S ( R k 0 S C in the order Ek ⊕ A′k ⊕ Dk , where C, S are diagonal and C2 + S2 = I. Absorbing Pk , Qk into the middle factor and extending by the identity on Fk yields (Z)

(Z)

e k ), Mk = C k ( e Lk ) Nk+1 Ck ( R where Nk+1 fixes Fk ⊕ Ek = Fk+1 pointwise. We now enforce determinant one. Since A′k ̸= {0}, choose unitaries Xk , Yk on Ak , acting identically on Ek , such that det Xk = (det e L k ) −1 ,

e k ) −1 . det Yk = (det R

For example, each correction can be a phase on one fixed unit vector in A′k , with the identity on its orthogonal complement. Set Lk = e L k Xk , (Z)

ek , Rk = Yk R

(Z)

(Z)

Mk+1 = Ck ( Xk† ) Nk+1 Ck (Yk† ).

(Z)

Then Mk = Ck ( Lk ) Mk+1 Ck ( Rk ) and det Lk = det Rk = 1. Both corrections fix Fk ⊕ Ek , so (Z)

Mk+1 still fixes Fk+1 pointwise. Moreover, det Ck (V ) = det V, and hence det Mk+1 = det Mk = 1. Starting with M1 = H ⊗n UH ⊗n , which fixes F1 , and iterating gives the computational-basis factorization. Conjugating by H ⊗n gives the claimed factorization, since (Z)

H ⊗ n Ci

(V ) H ⊗n = Ci H ⊗(n−1) V H ⊗(n−1) ,

and conjugation preserves SU(2n−1 ).

C

Proof of Lemma 5.2

Here, we prove the following restatement of Lemma 5.2: Fix an adaptive q-query algorithm, where 1 ≤ q ≤ d. There is a positive linear map Λ, depending only on the algorithm, such that its averaged output state under an ensemble ξ is ρξ = Λ( Jξ ), where ⊗q

Jξ = d2q EU ∼ξ (UX† )⊗q |Ωdq ⟩⟨Ωdq |UX . Proof of Lemma 5.2. Purify the query algorithm. At query j, retain its intended input as X j , introduce a fresh Bell pair Yj Zj in |Ωd ⟩, and continue the algorithm using Zj as the oracle output. Retaining all X j , Yj produces a normalized, oracle-independent state |Ψ⟩WXY . Gate teleportation gives

(⟨Ωd | XY ⊗ IZ )(UX ⊗ IYZ )(|χ⟩ X ⊗ |Ωd ⟩YZ ) = d−1 U |χ⟩ Z , 32

also when the input is entangled with a workspace. Contracting all retained pairs thus reproduces the algorithm’s output with amplitude d−q . Consequently, Λ( Z ) = TrXY [( IW ⊗ Z )|Ψ⟩⟨Ψ|] satisfies ρξ = Λ( Jξ ). Last, we show that ρ∗ = Λ( J∗ ) is a state: First, Λ is clearly positive and it remains to show that Λ( J∗ ) is normalized. Let ω j be the reduction of |Ψ⟩⟨Ψ| to the first j retained pairs. Causality gives ω j = τj ⊗ IYj /d,

TrXj τj = ω j−1 ,

ω0 = 1.

Indeed, Yj is initially maximally mixed and independent of the previously retained registers and X j ; later operations act only on their complement. Define Tj = ∑ Tr[( R X≤ j (σ ) ⊗ RY≤ j (σ ))( I ⊗ Πdist(d,j) )ω j ], T0 = 1. σ∈S j

When tracing out Yj , a term with σ ( j) ̸= j vanishes: its diagonal entries would require two labels of a distinct tuple to coincide. If σ ( j) = j, there are d − j + 1 choices for the last label. The factor IYj /d therefore contributes (d − j + 1)/d. The surviving permutations act trivially on X j , so tracing X j replaces τj by ω j−1 . Hence Tj =

d−j+1 Tj−1 , d

Tr Λ[ J0 ( IX ⊗ ΠY )] = Tq =

Thus Tr Λ( J∗ ) = 1.

33

(d)q . dq

Related documents

• On the pseudorandomness of simple quantum processes#1157448
• Generating quantum ensembles via reverse-time quantum diffusions#1035514
• Pseudo Entropy in Quantum Spin Chains: from Integrability to Chaos#798434
• Pseudo Entropy in Quantum Spin Chains: from Integrability to Chaos#797021
• Causal-Order Identification of Memoryless Sequential Quantum Processes from Restricted Projective Data#1011093