Source-linked AI summary
Distinctness threshold for pseudorandom unitaries
Asad Raza, Jens Eisert, Bill Fefferman
TL;DR
The relationship between statistical pseudorandomness from designs and computational pseudorandomness in PRUs remains poorly understood. The paper identifies distinctness as a necessary property, characterizes it through entangled anticoncentration, and shows it can support PRU constructions without a design layer. It also derives resource constraints and identifies restricted input classes where real-valued PRUs are possible.
Problem
How statistical randomization relates to computational pseudorandomness in PRUs remains poorly understood, despite existing constructions combining designs with classical cryptographic primitives.
Source: §I · p. 2Method
The paper studies distinctness, proves its necessity for PRUs, characterizes it via entangled anticoncentration, and uses it to analyze constructions and input-dependent resource constraints.
Source: §I · pp. 2–3Results
Takeaways & Limitations
For non-adaptive forward-query PRUs, distinctness can replace the need for statistical pseudorandomness as the randomizing layer in the PFC framework.
Source: §I · p. 2, §2 · p. 6, C. Discussion and open questions · p. 9The paper’s PRU focus is limited to non-adaptive and forward-query security.
Source: §I · p. 2
Abstract
from arXiv · showhide
Pseudorandomness is increasingly recognized as a key property of ensembles in quantum information theory, statistical mechanics, and quantum many-body physics. Yet it appears in two conceptually different forms: statistical pseudorandomness, embodied by unitary designs, and computational pseudorandomness captured by pseudorandom unitaries (PRUs). The relationship between these two forms of pseudorandomness remains surprisingly poorly understood. Existing PRU constructions reveal this interplay where a statistically randomizing ingredient, a unitary design, is combined with classical cryptographic primitives to produce computational pseudorandomness. We show that statistical pseudorandomness is not necessary for computationally pseudorandom unitaries. We do this by replacing the unitary $2$-design layer in the existing constructions with ensembles that are not even state $1$-designs, yet are sufficiently {\em distinct}, a property we identify to be necessary for any PRU. This yields new non-adaptively secure PRU ensembles whose computational pseudorandomness is obtained without an underlying statistically pseudorandom quantum ensemble, such as a $2$-design. We characterize distinctness via an entangled analogue of anticoncentration and use it to show that distinctness already captures constraints on coherence and imaginarity of PRUs, while identifying broad classes of inputs for which the latter obstruction disappears, enabling real-valued PRUs even for certain (maximally) entangled states. As an application, we use lack of distinctness to constrain the conjectured pseudorandomness of the random phase-Hadamard ensemble to form a PRU.
I. Introduction
The paper identifies distinctness—the concentration of query-register weight on tuples with pairwise-distinct labels—as a necessary threshold for PRUs in the non-adaptive forward-query setting. It shows that distinctness can be achieved without a unitary or state design and connects it to entangled anticoncentration, resource constraints, and real-valued PRUs on restricted input classes.
I. Introduction
- Existing constructions use unitary or state 2-designs to concentrate query-register weight on tuples with pairwise-distinct labels, but distinctness is the more fundamental intermediate property.Such tuples have computational-basis labels that are pairwise distinct across the query registers.Source: §I · p. 2
- Every PRU in the studied setting must place all but negligible weight on the distinct subspace for every efficiently preparable input; otherwise collisions distinguish it from Haar evolution.The paper focuses on non-adaptive, forward-query-secure PRUs.Source: §I · p. 2
- A complex-valued random diagonal phase followed by Hadamards achieves the unitary 2-design construction’s O(t^2/2^n) distinctness bound while failing to be a state 1-design.This demonstrates that design-level statistical pseudorandomness is not required for this distinctness guarantee.Source: §I · p. 2
- A single layer of independent single-qubit 2-designs can replace PFC’s depth-log(n) global 2-design layer while still yielding a PRU.The paper presents this as evidence that the construction needs less statistical randomness at this stage.Source: §I · p. 2
- For polynomially many queries and negligible error, entangled anticoncentration is equivalent to distinctness and applies to arbitrary bipartite inputs, including entangled ones.This differs from standard anticoncentration, ordinarily formulated for fixed product-state inputs.Source: §I · p. 3
- Distinctness imposes imaginarity and coherence constraints, while real-valued distinct ensembles are possible on inputs with sufficiently small Bell overlap, including PPT states and some maximally entangled states.The paper reports real-valued PRUs secure on such restricted input classes.Source: §I · p. 3
A. Main results
The paper’s main results center on distinctness as a necessary PRU property and characterize it operationally through entangled anticoncentration. They also show that distinctness can arise without unitary or state designs, with consequences for constructions, resource requirements, and real-valued pseudorandomness.
A. Main results
- Distinctness is necessary for PRUs and has an operational characterization through an entangled version of anticoncentration.Source: A. Main results · p. 3
- The paper shows that distinctness can arise without unitary or state designs.Source: A. Main results · p. 3
- The results explore consequences of distinctness for PRU constructions, quantum resource requirements, and real-valued pseudorandomness.Source: A. Main results · p. 3
1. Distinctness as a property
Distinctness is necessary for PRUs and can be characterized through entangled anticoncentration in the polynomial-query regime. It also implies resource requirements and can be achieved by ensembles that are not state 1-designs.
a. Necessity of distinctness for PRUs and its operational characterization
- Entangled anticoncentration suppresses measurement collisions for arbitrary bipartite inputs, including entangled states, unlike standard anticoncentration on fixed product inputs.On product-state inputs, the restricted version recovers standard anticoncentration.Source: §1 · p. 4
- Every PRU must be negl(n)-distinct on efficiently preparable inputs, since collisions otherwise enable an efficient distinguisher.The condition also applies to PRUs with stronger security notions.Source: §1 · p. 4
- For polynomially many queries, δ-distinctness and δ-EAC are equivalent when δ is negligible.More generally, δ-distinctness implies δ-EAC, while δ-EAC implies (δ · t^2)-distinctness.Source: §1 · p. 4
b. Quantum resources for distinctness
- δ-distinctness already implies high imaginarity and coherence, so these quantum resources are required before an ensemble is fully pseudorandom.The bounds are E[Ip(U)] ≥ 1 − δ and E[Cp(U)] ≥ ln(1/δ).Source: §1 · p. 5
- A single layer of independent single-qubit 2-designs, such as random Cliffords, is negligibly distinct and can replace the depth-log(n) global 2-design layer in PFC.PRUs must be negligibly distinct, so the resource lower bounds for PRUs follow already at the distinct-subspace level.Source: §1 · p. 5
c. Is distinctness just a state 2-design in disguise?
- HF is O(t^2/N)-distinct yet fails to be a state 1-design, showing distinctness can hold without even state 1-design behavior.HF sends |0⟩ to |+⟩, which is Ω(1) far in trace distance from a single-copy Haar random state.Source: §1 · p. 5
2. Applications of distinctness
Distinctness supports new PRU constructions and acts as a test against conjectured ones. Restricting the allowed input states also permits real-valued PRUs for broad classes characterized by Bell overlap.
a. New PRU ensembles from new distinct ensembles
- A single layer of random single-qubit Cliffords supplies negligible distinctness and, with PF, yields a PRU while saving log(n) depth over the existing 2-design layer.The single layer is (2/3)^n-EAC, which implies negligible distinctness for polynomially many queries.Source: §2 · p. 6
- The HFC ensemble’s O(t^2/N)-distinctness can also be used to construct higher-order t-designs for t ≪ N.This follows the design principle used to build PRUs from distinct ensembles.Source: §2 · p. 6
c. Input-dependent distinctness and real-valued PRUs
- PFRHFC is a PRU, and replacing its trailing complex phase operator with a real-valued phase operator yields a real-valued PRU on restricted input states.The restricted-input real-valued construction also permits PFRCR.Source: §2 · pp. 6–7
b. Distinctness as a no-go test for PRUs
- The JLS conjecture cannot hold for polynomially many functions whose codomain is superpolynomially smaller than the domain; the stated necessary condition is log K > n − ω(log n).The analysis uses a distinguisher that applies the unitary to both halves of a Bell state and projects back onto that state.Source: §2 · p. 7
c. Input-dependent distinctness and real-valued PRUs
- Real-valued PRUs are secure on input ensembles with Bell overlap at most N/n^ω(1), including product and separable states and certain maximally entangled states.The criterion measures overlap with the canonical Bell state, not entanglement generally.Source: §2 · pp. 7–8
- On states with constant Bell overlap, orthogonal and unitary designs are equivalent up to error O(t/N); this includes all PPT states and some NPT states.Examples of the NPT class include Choi states of traceless unitaries.Source: §2 · p. 8
- Any state with Schmidt number at most N/n^ω(1) meets the Bell-overlap bound for real PRUs, including pure states with sufficiently small Schmidt rank.Schmidt number 1 covers product and separable states.Source: §2 · p. 8
B. Related work
The related work contrasts design-based PRU constructions with distinctness as a weaker ingredient, and connects that perspective to anticoncentration, resource constraints, and phase–Hadamard constructions.
B. Related work
- Earlier PRU constructions used unitary or state 2-designs to establish distinctness; this work treats distinctness as an ensemble property and replaces those stronger ingredients [MPSY24, MH24, LQS+25, FLM+26, SML+25, CSBH25].The related work distinguishes this approach from PC, which removes the phase layer while retaining a full random Clifford [FLM+26].Source: B. Related work · p. 8
- HFC achieves the unitary 2-design bound of O(2^-n)-EAC on arbitrary bipartite inputs despite failing to be a state 1-design.In the computationally bounded regime, O(2^-n)-EAC gives O(t^2/N)-distinctness; standard anticoncentration concerns fixed product inputs [HHRH25, HBVSE18, DHJB22].Source: B. Related work · p. 8
- A depth-one ensemble of independent single-qubit Clifford gates is distinct for polynomially many queries and can yield a PRU in the PFC construction.This replaces the depth-log(n) global unitary 2-design layer while retaining computational security for polynomially many queries.Source: B. Related work · p. 8
- The phase–Hadamard lower bound rules out PRUs from polynomially many layers when phase functions have codomain size K ≤ N/n^ω(1), but does not refute the full-alphabet conjecture [JLS18].The related work notes that the binary case was already obstructed by the impossibility of real PRUs [HBK24].Source: B. Related work · p. 9
- Distinctness already implies PRU-related coherence and imaginarity requirements, including a robust coherence bound for ensembles with small off-diagonal entries [HBK24, BY26].The discussion also compares real PRUs on bounded-Bell-overlap inputs with prior results on mutually orthogonal inputs [BM24].Source: B. Related work · p. 9
- The Bell-overlap condition includes product and separable states, including some states with negative partial transpose, while real PRUs remain secure on qualifying inputs [BM24, GHH+25].The passage contrasts this class with prior results on mutually orthogonal inputs and PPT inputs.Source: B. Related work · p. 9
C. Discussion and open questions
The discussion presents distinctness as a route to weaker, task-matched randomness conditions and identifies open questions about stronger query access, real-valued pseudorandomness, and uses beyond PRUs.
a. Distinctness in stronger query models and beyond
- Whether distinctness extends to inverse, transpose, conjugate, controlled, or adaptive queries—and separates from design properties there—remains open.The authors also ask whether depth-one independent single-qubit Clifford gates are non-plussed distinct and could yield a PRU [FLM+26].Source: C. Discussion and open questions · p. 10
b. Real-valued pseudorandomness and applications
- The obstruction to real-valued pseudorandomness is sufficiently large overlap with the canonical maximally entangled Bell state, not entanglement by itself.The discussion proposes classifying physically relevant bounded-Bell-overlap inputs and notes that real-versus-complex PRU distinguishers may witness Bell overlap.Source: C. Discussion and open questions · p. 10
c. Distinctness beyond PRUs
- Distinct ensembles may be cheaper than unitary designs in randomized measurements, benchmarking, sampling, and cryptographic protocols where repeated output labels are the relevant failure mode.The authors frame identifying which applications need design-level randomness as future work.Source: C. Discussion and open questions · p. 10
d. Outlook
- The authors present distinctness as a possible intermediate notion for a modular theory that identifies the randomness required for cryptographic applications.They hope this viewpoint can replace unnecessarily strong conditions with operational criteria.Source: C. Discussion and open questions · p. 10
AI statement
The authors report the project timeline and describe the role of AI tools in developing and checking the work.
AI statement
- The authors began the project in early 2025 and obtained preliminary versions of the main results, except Theorem III.5.They say ChatGPT 5.6 Sol proposed Theorem III.5 as a counterexample to their conjecture that a negl(n)-distinct ensemble must be entangling.Source: AI statement · p. 11
- ChatGPT 5.5 and 5.6 Pro assisted with literature search, exposition, technical verification, and proof strategies for the main results.Source: AI statement · p. 11
- The authors say they independently verified all proofs and take full responsibility for the content.Source: AI statement · p. 11
II. Preliminaries
The preliminaries establish notation and the parallel forward-query security setting, then introduce design and distinct-subspace concepts used in the paper.
II. Preliminaries
- The paper sets N = 2^n, uses t for the number of oracle queries, and focuses on polynomially many parallel forward-only queries.The authors state that lower bounds in this weakest security regime also apply to stronger PRU notions.Source: §II · pp. 11–12
- The distinct subspace corresponds to pairwise-distinct computational-basis tuples, while its complement detects collisions on the full t-copy space or a bipartition.Source: §II · p. 11
- A parallel forward PRU is efficiently computable and indistinguishable from Haar-random evolution to efficient non-adaptive forward-query distinguishers.Source: §II · p. 12
- The paper also considers PRUs secure when distinguishers may query only on input states from a specified set.Source: §II · p. 13
- Unitary t-designs and additive-error variants are introduced alongside state t-designs, whose inputs are t copies of a single state.The twirling channel is also called the t-th moment operator.Source: §II · pp. 13–14
III. Necessity and characterization of distinctness
For polynomially many queries and negligible error, distinctness and entangled anticoncentration characterize one another. Distinctness is necessary for PRUs, while a single layer of single-qubit Clifford gates can provide it within a PRU construction.
III. Necessity and characterization of distinctness
- For polynomially many queries and negligible error, distinctness is equivalent to entangled anticoncentration.Distinctness implies entangled anticoncentration, and entangled anticoncentration implies distinctness with a query-count-dependent bound.Source: §III · pp. 14–15
- Every PRU is negligibly distinct on efficiently preparable inputs, since an efficient collision test would otherwise distinguish it from Haar evolution.The result also states that PRUs are negligibly entangled-anticoncentrating on such inputs.Source: §III · p. 16
- A single layer of random single-qubit Clifford gates is negligibly distinct; when gates are independently sampled from the single-qubit Clifford group or an exact single-qubit 2-design, the ensemble is δ-EAC with δ = (2/3)n.Source: §III · p. 17
IV. Necessary quantum resources for the distinctness
Distinctness imposes constraints on the quantum resources of unitary ensembles. Since PRUs must be negligibly distinct, they must also satisfy the resulting coherence and imaginarity requirements.
IV. Necessary quantum resources for the distinctness
- The section treats coherence and imaginarity as separate unitary resources constrained by distinctness.The two results establish necessary conditions for distinctness in terms of these respective quantities.Source: §IV · pp. 18–19
- PRUs have average imaginarity 1 − negl(n) and average coherence ω(log n).These resource bounds follow by applying the distinctness constraints to the necessity of distinctness for PRUs.Source: §IV · p. 20
V. Real valued PRUs beyond PPT input states
The paper extends real-valued PRU guarantees beyond product and PPT inputs by classifying inputs through Bell overlap. It also gives distinctness guarantees for Hadamard–phase ensembles that do not form state 1-designs.
V. Real valued PRUs beyond PPT input states
- PFRCR and PFRHFR are PRUs on inputs with small Bell overlap, including separable, PPT, and certain NPT Choi-state inputs.The text identifies traceless-unitary Choi states as maximally entangled examples with zero Bell overlap.Source: §V · pp. 21, 24
- Orthogonal 2-designs are O(t^2/N)-distinct on state ensembles with constant Bell overlap.This input-dependent distinctness bound is used to obtain real-valued design guarantees.Source: §V · pp. 22–23
- For inputs with Bell overlap O(1), PFRCR and PFRHFR give real-valued approximate unitary t-designs.The corresponding corollaries apply to both ensembles on the bounded-Bell-overlap input class.Source: §V · p. 23
- On bounded-Bell-overlap inputs, unitary and orthogonal twirls are equivalent under the result in Proposition V.6.The paper describes this state class as larger than the PPT-only class covered by the earlier comparison it cites.Source: §V · p. 23
- The pairwise Schmidt-number class with bound k has Bell overlap at most k, and the ensembles give O(t/N)-approximate additive unitary t-designs on separable inputs.For PRUs, the text says the tolerated Schmidt number can be at most N/n^ω(1).Source: §V · pp. 24–25
VI. Distinctness without designs
- The complex-phase HF ensemble is O(1/N)-EAC and therefore O(t^2/N)-distinct, despite not being a state 1-design.The paper presents this as distinctness without requiring a unitary or state design.Source: §VI · p. 25
N (I + SWAP). Hence,
A real-valued binary phase operator preserves HF's entangled anticoncentration guarantee on inputs with bounded Bell overlap. The proof transfers the HFH bound to HF while preserving Bell overlap.
N (I + SWAP). Hence,
- HF with a real-valued binary phase operator is O(1/N)-EAC on states with Bell overlap O(1).The guarantee is input-restricted to the stated Bell-overlap class.Source: N (I + SWAP). Hence · p. 27
- The Hadamard-transformed input preserves Bell overlap, allowing the HFH bound to transfer to HF.The operator-norm bound is unchanged by the right-most Hadamard in HFH.Source: N (I + SWAP). Hence · pp. 27–28
- The proof establishes positivity of the XOR-collision operator J by rewriting it as a sum of rank-one positive semidefinite operators.This positivity supports the bound used in the real-phase argument.Source: N (I + SWAP). Hence · pp. 27–28
VII. Constraints on the JLS conjecture
The section tests the conjecture that a constant number of alternating Hadamard and random phase layers yields a pseudorandom unitary [JLS18]. It rules this out for the stated small phase-alphabet regime and gives a Bell-type distinguisher.
VII. Constraints on the JLS conjecture
- The result challenges the conjecture that a constant number of alternating Hadamards and random phase unitaries yields a PRU [JLS18].Source: §VII · p. 28
- For uniformly random functions with log K ≤ n − ω(log n), the resulting phase–Hadamard ensemble cannot form a PRU.The theorem considers polynomially many layers.Source: §VII · pp. 28–29
- A Bell-type distinguisher queries the unitary on a Bell state and measures in the Bell basis to distinguish the ensemble from Haar evolution.Source: §VII · p. 29