PaperlayerView exact revision on arXiv

Source-linked AI summary

On the pseudorandomness of simple quantum processes

Jesko Dujmovic, Jonas Haferkamp, Alexander Poremba

arXiv:2610.02100v1quant-phcs.CR

TL;DR

The paper asks whether statistical moment matching in simple quantum processes can guarantee computational pseudorandomness. It constructs counterexamples, including local quantum-gate ensembles that match fixed-order moments yet remain efficiently distinguishable.

  • Problem

    Approximate unitary designs match Haar moments, but pseudorandomness requires fooling computationally bounded distinguishers, and the relationship between these guarantees remains open.

    Source: §1 · p. 2

  • Method

    The paper constructs local quantum-gate ensembles and adaptive unitary designs, then gives efficient quantum algorithms that distinguish them from Haar-random unitaries.

    Source: §1.1 · pp. 4–5

  • Results

    T = O_t(n^2 log^2 n) local-gate steps yield an approximate adaptive unitary t-design with error exp(−Ω_t(log^2 n)), yet an efficient algorithm distinguishes it from Haar with constant advantage using O_t(log^2 n) parallel forward queries.

    Source: §1.1 · p. 4

  • Takeaways & Limitations

    Statistical moment properties alone do not guarantee computational pseudorandomness, even for ensembles built from local interactions.

    Source: §1.1 · p. 4

    The counterexamples do not apply to the setting where each gate acts on a constant number of qubits and the gate distribution may depend on n.

    Source: §6 · p. 24

Abstract

from arXiv · show

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 $\{\nu_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(-\Omega(\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.

1 Introduction

The introduction asks whether simple local quantum processes can become pseudorandom, and whether approximate unitary designs at constant or growing order ensure security against efficient distinguishers. It gives counterexamples and motivates a conjecture that polynomially many local gates with approximate design behavior at order Θ(n) and negligible additive error may yield pseudorandomness.

1 Introduction

  • The paper positions its quantum question alongside Gowers’s conjecture that sufficiently deep random reversible circuits may be indistinguishable from uniformly random permutations to efficient observers.Approximate t-wise independence constrains outputs on prescribed inputs, while pseudorandomness must withstand polynomial-time distinguishers making their own polynomial number of queries.Source: §1 · pp. 1–2
  • The introduction frames the open quantum Gowers question: local random circuits may form pseudorandom unitaries, whereas unitary t-designs match Haar moments but do not alone guarantee security against efficient distinguishers.The Quantum HMMR conjecture [HMMR05] posits that local-gate ensembles achieving an approximate unitary 4-design with negligible error are pseudorandom.Source: §1 · pp. 3–4

1.1 Our contributions

  • With T=O_t(n^2 log^2 n), a one- and two-qubit walk is an approximate adaptive unitary t-design with error exp(-Ω_t(log^2 n)), yet O_t(log^2 n) parallel queries distinguish it from Haar with constant advantage, for fixed t≥4.This refutes the Quantum HMMR conjecture for local quantum processes.Source: §1.1 · p. 4
  • The local walk mixes nearest-neighbor Clifford gates with rare random non-Clifford Z-rotations, preserving stabilizer structure while letting its moments approach Haar moments.The rotation probability is 1/m for m=Θ_t(n^2); Clifford mixing reduces the moment analysis to a constant-dimensional fixed-point space.Source: §1.1 · p. 5
  • The cited construction can be distinguished from Haar by an efficient quantum algorithm running in poly(n, t) time, with constant advantage, using O(nt) forward queries.Source: §1.1 · p. 5
  • The second construction preserves a special subspace S=span{|+⟩^⊗n}: queries there yield binary phase states whose phase function can be learned from O(nt) copies, enabling Haar distinction.The phase function is 2t-wise independent, while the idealized FB∞ ensemble achieves adaptive unitary t-design error O(t^2/2^n).Source: §1.1 · pp. 6–7
  • An explicit circuit replaces the idealized operator while fixing |+⟩^⊗n, using controlled operations and an inverse-polynomial-gap walk to approximate its moments without defeating the phase-learning distinguisher.The construction samples controlled circuits rather than individual local gates, so the separate phase circuit remains essential.Source: §1.1 · p. 7
  • The FB ensemble can attain near-maximal scrambling yet remain distinguishable from Haar with constant advantage using O(n^2) forward queries.Its expected min-entropy is within a constant of maximum across every fixed balanced crossed cut of its Choi state; increasing B’s depth preserves the phase-learning relation.Source: §1.1 · pp. 7–8
  • The authors conjecture that independently composing T = poly(n) local gates from one efficiently samplable distribution is pseudorandom when it forms an approximate unitary t-design at t = Θ(n) with negligible additive error.They suggest this may mark a genuine threshold, since their counterexamples do not rule out pseudorandomness at the maximal scrambling scale.Source: §1.1 · p. 8
  • Polynomial-depth local random circuits achieve t = Θ(n) designs, while uniformly small outcome probabilities at that order further support the significance of this threshold.The connection suggests studying growing-order independence in local reversible circuits beyond classical HMMR counterexamples and as a perspective on the Gowers conjecture.Source: §1.1 · p. 8

2 Related work

Prior work establishes both classical and quantum sources of distinguishable designs and obstructions to pseudorandomness. This paper’s results complement those works by separating design guarantees from computational pseudorandomness, including for simple local quantum walks.

Related work

  • The quantum local-circuit result parallels Dujmovic, Pelecanos, and Tessaro’s refutation of HMMR using locally composed permutations, but balances moment matching with stabilizer structure using quantum techniques.The paper contrasts its one- and two-qubit steps with classical rounds that may act on all wires if each output bit depends on constantly many inputs.Source: §2 · p. 8
  • Earlier work obtained distinguishable designs with few non-Clifford gates, while Bittel and Leone also gave an efficient test for surviving stabilizer structure; this work instead uses a homogeneous i.i.d. walk with negligible-error adaptive designs.The cited earlier constructions use non-Clifford gate counts independent of system size for fixed order and error.Source: §2 · p. 8
  • The higher-order separation builds on binary phase-state designs and derivative-measurement learning, extending those learning algorithms to a fine-grained query setting and embedding structure into the PFC ensemble.The analysis also uses adaptive-query methods of Cui et al..Source: §2 · p. 8
  • Constant-local, time-independent Hamiltonian evolution is distinguishable from Haar regardless of evolution time, but that obstruction also prevents sufficiently accurate unitary 2-designs.Unlike that setting, this paper’s local-circuit counterexample achieves any prescribed constant design order with negligible additive error.Source: §2 · pp. 8–9
  • Higher design order controls progressively higher Rényi entanglement entropies, and sufficiently accurate Θ(n)-designs give near-maximal expected min-entropy.The cited work connects statistical moments to entanglement entropy; this paper discusses connections to computational pseudorandomness.Source: §2 · p. 9
  • Concurrent work shows that design-level randomness is not necessary for non-adaptive pseudorandom unitaries, while this paper shows strong unitary-design guarantees need not be sufficient.Together the works delineate the gap between statistical and computational notions from opposite directions.Source: §2 · p. 9

3 Preliminaries

The preliminaries establish notation for unitary ensembles and their moments, then state the adaptive-design and pseudorandom-unitary notions used in the paper. They also define the distinct subspace and standard operator and probability notation.

Preliminaries

  • The notation section supplies finite-set and operator conventions, defines trace, Frobenius, and operator norms, and calls an error function negligible when it is eventually below every inverse polynomial.It also uses O_t, Ω_t, and Θ_t when constants may depend on t.Source: §3 · p. 9
  • For a unitary ensemble, the Haar measure is the invariant uniform distribution, and ν∗r denotes the product of r independent samples from ν.The notation ν∗η denotes the distribution of UV for independent U∼ν and V∼η.Source: §3 · p. 10
  • The t-fold twirl and its vectorized moment operator are the moment representations used for ensembles, with corresponding Haar versions denoted by µH.The supplied passages introduce these objects and notation.Source: §3 · p. 10
  • An adaptive t-query algorithm interleaves oracle calls with operations on its query and ancilla registers, and an adaptive approximate t-design limits its distinguishing advantage against Haar.The definition takes the supremum over adaptive algorithms with two-outcome measurements.Source: §3 · p. 10
  • A pseudorandom unitary ensemble requires efficient keyed generation and security against quantum polynomial-time oracle algorithms making polynomially many queries.The passages specify uniform circuit families and efficient two-outcome measurements.Source: §3 · pp. 10–11
  • The t-fold distinct subspace is spanned by computational-basis tuples whose labels are pairwise distinct.For two labels, its projector excludes the basis states with equal labels.Source: §3 · p. 11

4 Refuting the Quantum HMMR conjecture

The paper refutes the Quantum HMMR conjecture with a local walk that achieves negligible-error adaptive designs yet remains efficiently distinguishable from Haar. Its proof combines spectral control of moment operators with a stabilizer-based test.

4 Refuting the Quantum HMMR conjecture

  • The walk mixes local Clifford updates with rare single-qubit non-Clifford rotations, preserving enough stabilizer structure for efficient distinguishability while the rotations address residual moment obstructions.Each update acts on at most two neighboring qubits, and updates are independent samples from the same distribution.Source: §4 · pp. 11–12
  • The update chooses a neighboring-pair Clifford gate with probability 1−1/m and a random Z rotation on the first qubit with probability 1/m.The rotation branch includes its identity outcome as an insertion; fixed-t angle discretization can reproduce the moment exactly, with finite-precision implementation adding negligible error.Source: §4 · p. 11
  • Acceptance probabilities of adaptive t-query experiments are linear functions of the moment operator, allowing the spectral bounds to control distinguishing advantage.The proof represents each experiment with a matrix whose norm is bounded in terms of the query dimension.Source: §4 · pp. 12–13
  • The proof uses a local Clifford moment-operator gap outside the Clifford-invariant space and a constant gap for insertions within that space outside the Haar-invariant space.After subtracting the Haar moment, all but constantly many eigenvalues become exponentially small; bounded acceptance probabilities control the remaining finite spectral expansion.Source: §4 · p. 13

4.1 Proof of Theorem 1.3

  • The proof chooses the walk length so the moment-operator difference from Haar is exponentially small outside a fixed-dimensional exceptional spectral contribution, yielding negligible adaptive-design error.For fixed t, the number of eigenvalues above the small threshold is bounded by a constant depending on t.Source: §4.1 · p. 15
  • With high probability the walk has at most 6⌈log2 n⌉ single-qubit non-Clifford gates, leaving many stabilizers that the Bell-difference test can detect.The test uses 12h+10 copies and accepts states with at least n−h stabilizer dimension with probability at least 5/8, versus at most 1/2+2^-Ω(n) for Haar states.Source: §4.1 · pp. 14–16
  • The distinguisher prepares O(log^2 n) copies in parallel: its acceptance is at least 5/8−e^-Ω(log^2 n) on the walk and at most 1/2+2^-Ω(n) on Haar.This implements the stabilizer test using 12h+10 copies.Source: §4.1 · pp. 14, 16

5 Separating higher-order unitary designs from pseudorandomness

This section establishes a separation between pseudorandom unitaries and polynomial-order unitary designs. It constructs polynomial-depth ensembles that are approximate t-designs for every fixed polynomial t yet efficiently distinguishable from Haar, using a learnable planted phase state and collision bounds to establish adaptive-query indistinguishability for a Haar-based version.

5.1 The FB ensemble

  • The phase signs are independent and uniform on any set of at most 2t basis labels when 2t≤d, and each phase unitary has an exact poly(n, t)-size circuit.The ensemble uses U=FB, with B fixing |+⟩⊗n and randomizing its orthogonal complement, while F maps that vector to a phase state.Source: §5.1 · p. 16

5.2 The FB∞ensemble is an approximate design

  • For q≤t and 2t≤d, Fn,t satisfies the phase-independence condition for the FB∞ indistinguishability criterion, whose error is controlled by collision probabilities.The general criterion applies when F has 2q-wise independent signs and compares adaptive q-query outputs with Haar using collision bounds.Source: §5.2 · pp. 18–19

5.3 Learning the planted phase state

  • Any ensemble FB with the specified random phase F and a B that fixes |+⟩⊗n is distinguishable from Haar in polynomial time using parallel queries.Each forward query on |+⟩⊗n produces the same phase state, which can be learned by extracting relative phases that constrain its seed.Source: §5.3 · p. 19

5.3.1 Relative-phase measurements and recovery

  • A quantum procedure recovers a seed whose associated phase state matches the target up to global phase with probability at least 1−δ, with worst-case running time poly(n, L, log(1/δ)).Derivative sampling returns a uniform unordered distinct pair and bit f(x)+f(y); each relative phase gives a linear constraint on the seed.Source: §5.3.1 · pp. 19–20, §5.3 · p. 19

5.4 Proof of Theorem 1.4

  • The proof replaces B∞ on the fixed-vector complement with an approximate t-design, using Kazhdan-constant and spectral-gap machinery that includes 25 constant-depth unitaries.The cited generator set has a uniformly lower-bounded Kazhdan constant in SU(2n).Source: §5.4 · pp. 21–22
  • For every fixed polynomial t=poly(n), the construction gives an approximate t-design using polynomial-depth circuits.Choosing ε=e^-n yields polynomially deep circuits.Source: §5.4 · p. 22
  • Despite this design property, the ensemble is efficiently distinguishable from Haar and thus fails pseudorandomness under Definition 3.2.The distinguishing claim follows from Lemma 5.5.Source: §5.4 · p. 22

6 Pseudorandomness and Maximal Scrambling

The section asks whether maximal scrambling implies computational pseudorandomness. It shows that, in general, an ensemble can match moments at the maximal-scrambling scale yet remain efficiently distinguishable, and proposes a conjecture for local processes.

6 Pseudorandomness and Maximal Scrambling

  • An approximate unitary t-design at t=Θ(n) can have near-maximal expected min-entropy across a fixed balanced crossed cut and still be distinguishable from Haar with constant advantage using O(n^2) forward queries.Thus, maximal scrambling does not in general imply pseudorandomness.Source: §6 · pp. 23–24
  • The construction deepens the mixing circuit to control Choi moments while preserving U|+⟩^⊗n = F|+⟩^⊗n, so the phase-learning algorithm still distinguishes it.The ensemble therefore has near-maximal entanglement entropies while retaining efficiently learnable algebraic structure.Source: §6 · p. 24
  • The section conjectures that efficiently samplable local-gate ensembles forming negligible-error approximate unitary t-designs at t=Θ(n) are pseudorandom after polynomially many independent gates.Each gate acts non-trivially on only a constant number of qubits, and the gate distribution may depend on n.Source: §6 · p. 24
  • Neither counterexample covers that conjectured setting: the near-Clifford argument proves designs only at fixed constant order, while the FB ensemble uses structured nonlocal mixing.The section frames this as an open intermediate regime combining local interactions with moment matching at the maximal-scrambling scale.Source: §6 · p. 24

A Bounds on the collision probability

This appendix bounds collision probability for Haar measure on the group fixing |+⟩^⊗n. Its proof uses a two-copy symmetric twirl and bounds contributions from distinct-pair events.

A Bounds on the collision probability

  • The proof applies the two-copy symmetric twirl to operators supported on the symmetric subspace.The twirl lemma is stated for N≥1 and the symmetric subspace of (C^N)^⊗2.Source: A Bounds on the collision probability · p. 30
  • The Haar collision-probability bound also holds in every integer dimension D≥2, with d replaced by D.The cited lemma states the bound for Haar measure on the group fixing |+⟩^⊗n.Source: A Bounds on the collision probability · p. 30
  • The proof separates the averaged collision operator across S⊗2 and the mixed S and S⊥ subspaces after averaging central phases.On S⊗2, the operator has eigenvalue 1/d; the passage also describes the mixed-subspace component.Source: A Bounds on the collision probability · pp. 30–31
  • To prove both assertions, the argument bounds nondistinct tuples by a sum over equal-pair events and combines the resulting two-copy bounds.For q=1, the equal-pair sum is empty.Source: A Bounds on the collision probability · p. 31

B Proof of Lemma 5.12

The proof constructs a factorization for special unitaries fixing a growing sequence of subspaces. It uses cosine–sine decomposition at each step and corrections that preserve determinant one and the fixed subspaces.

B Proof of Lemma 5.12

  • At each step, a unitary fixing F_k is decomposed into L_k, R_k, and M_{k+1}, with M_{k+1} fixing F_{k+1} pointwise.The cosine–sine decomposition is applied using the identity block on E_k.Source: B Proof of Lemma 5.12 · pp. 31–32
  • The cosine–sine step uses A_k and D_k, with C and S diagonal and C^2+S^2=I.The proof absorbs P_k and Q_k into the middle factor and extends it by the identity on F_k.Source: B Proof of Lemma 5.12 · pp. 31–32
  • Determinant corrections on A_k preserve the fixed subspaces and keep det M_{k+1}=1 throughout the iteration.The proof starts from M_1=H^⊗n U H^⊗n, which fixes F_1.Source: B Proof of Lemma 5.12 · p. 32
  • Any U∈SU(2^n−1) fixing the specified subspace admits a computational-basis factorization with L_k, R_k, and V_n in SU(2^n−1).The proof obtains this by iteratively factoring a unitary while enlarging the subspace it fixes pointwise.Source: §5.4 · p. 22, B Proof of Lemma 5.12 · pp. 31–32

C Proof of Lemma 5.2

The proof represents an adaptive algorithm’s averaged output as a positive linear map applied to the ensemble’s Choi operator. It uses gate teleportation and causality to show the map preserves normalization on the reference operator.

Proof of Lemma 5.2

  • For any adaptive q-query algorithm with 1 ≤ q ≤ d, a positive linear map depending only on the algorithm satisfies ρξ = Λ(Jξ).The proof also establishes Tr Λ(J∗) = 1.Source: C Proof of Lemma 5.2 · pp. 32–33
  • Purification and fresh Bell pairs yield a normalized oracle-independent state; gate teleportation and contraction reproduce the algorithm’s output with amplitude d−q.The retained registers are the intended query inputs and Bell-pair halves.Source: C Proof of Lemma 5.2 · pp. 32–33
  • Causality gives ωj = τj ⊗ IYj/d and TrXj τj = ωj−1, supporting the normalization argument for Λ(J∗).The Bell-pair register is initially maximally mixed and independent of retained registers and the query input.Source: C Proof of Lemma 5.2 · p. 33
  • In the trace, terms with σ(j) ≠ j vanish, while σ(j) = j contributes a factor (d−j+1)/d before tracing Xj reduces τj to ωj−1.The surviving permutations act trivially on Xj.Source: C Proof of Lemma 5.2 · p. 33

Related papers

Loading 2610.02100v1…