No linear stretching of single-copy quantum pseudorandomness

arXiv:2606.24736 · quant-ph, cs.CR · Submitted 2026-06-23 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: Today's paper: "No linear stretching of single-copy quantum pseudorandomness".

Mira: Pseudorandom states are fundamental quantum primitives, and this work establishes a black-box separation between single-copy secure pseudorandom states (1PRS) with different output lengths.

Kai: First, who's behind it and why it matters.

Paper summary: Kai: So we're diving into "No linear stretching of single-copy quantum pseudorandomness" today. We're looking at how this paper establishes a black-box separation between different output lengths for these quantum states, which is a pretty big deal.

Mira: Exactly, Kai; the core thesis seems to be that while classical PRGs can always be stretched to longer lengths iteratively, that doesn't seem true for single-copy secure pseudorandom states in the quantum setting. The paper claims they can separate 1PRS with output length m(n) = 1 point 1n from those with length (n two plus epsilon) <ref:2606.24736#pg0,1PRS with output length $m(n) = 1.1n>.

Lev: From a quantum error-correction perspective, if this separation holds, it means that any construction aiming for very long stretches in the quantum domain would require fundamentally different assumptions than what we see in classical stretching constructions. If we're thinking about implementing these on real hardware, that kind of resource constraint is something we need to keep in mind.

Kai: Right, Lev; so the paper sets up this separation using a specific quantum oracle construction based on the Common Haar Random State model from Chen, Coladangelo, and Sattath CCS25. It seems they're building a scenario where one type of state exists relative to that oracle, but the longer-length states don't exist for any positive epsilon.

Mira: That reliance on the CHRS model is interesting because it ties the separation directly to accessing a family of states sampled from specific Haar measures. It suggests that even with access to this rich set of states, there’s a structural limitation preventing arbitrary linear stretching.

Lev: I wonder what this means for practical error correction; if an algorithm needs that kind of stretching, and it can only be realized in a way bounded by polynomial copies of the CHRS states as Corollary four point six suggests, that constrains how much complexity we can actually build on physical systems <ref:2606.24736#pg1>.

Kai: So, to recap the summary, the paper proves there's a black-box separation: 1PRS with length 1 point 1n exists relative to an oracle O, but no 1PRS with length (n two plus epsilon) exists for any epsilon > zero <ref:2606.24736#pg0>. This is achieved by defining an oracle O = (O one O two) and showing that any generator must have a succinct implementation <ref:2606.24736#pg0>.

Mira: And the mechanism they use to show the impossibility of stretching is through an attack leveraging this structural property. The adversary queries O two to find "succinct" implementations, and then either uses permutation tests in Case A or projective measurements in Case B depending on which case applies <ref:2606.24736#pg0>.

Lev: That attack mechanism sounds like it would translate into very specific resource constraints for any hypothetical algorithm trying to achieve that large output length without the oracle's help. It suggests that the complexity required for stretching scales much faster than linearly, perhaps quadratically in the length of the state itself, given their findings about m = (n two plus epsilon) <ref:2606.24736#pg0>.

Paper summary: Kai: That’s what it looks like from a hardware standpoint—the resource demands just don't align with what we can construct efficiently under these black-box conditions. So, this paper is demonstrating that you can't just take a short stretch and linearly extend it indefinitely using the same underlying mechanism in this setting.

Mira: Precisely; the key finding is that stretching a 1PRS from 1 point 1n to (n two plus epsilon) is impossible relative to these specific oracles, which highlights a fundamental difference between classical and quantum pseudorandomness resource bounds <ref:2606.24736#pg0>.

Lev: If this result holds up under different oracle definitions, it really suggests that the difficulty isn't just in finding a better algorithm for stretching, but in the inherent structure of quantum states themselves when constrained by black-box access to these random families.

Kai: So, moving into the conclusion section of "No linear stretching of single-copy quantum pseudorandomness," we look at what this separation actually means for the field beyond just proving a bound.

Mira: The authors are pointing out that this result establishes a clear boundary in what's achievable for 1PRS without resorting to more powerful access models, which is important because it clarifies the limits of our current understanding of these primitives <ref:2606.24736#pg0>.

Lev: I think the implication for error correction is that we need to be careful when designing protocols that rely on stretching these states, because if you need a very long stretch, you’re likely looking at something outside this proven black-box regime.

Kai: So, to summarize the conclusion simply: they've shown that in the context of this specific oracle construction, single-copy secure pseudorandom states with lengths of 1 point 1n are achievable, but there's a hard barrier against achieving lengths that grow as fast as n squared <ref:2606.24736#pg0,single-copy secure pseudorandom states>.

Mira: The title itself speaks to this limitation; it explicitly states "No linear stretching," which is a strong claim about the nature of quantum randomness in this black-box environment.

Lev: If we look at the broader implications, this result helps delineate where quantum pseudorandomness might be fundamentally weaker or stronger than its classical counterpart when viewed through the lens of resource constraints.

Kai: It suggests that if you want to build systems requiring arbitrarily long stretches, you can’t just rely on a short stretch and assume it scales nicely; you need a different approach entirely for the construction.

Mira: Ultimately, the paper is drawing attention to the distinction between what's possible with limited access versus what's possible with more powerful tools like querying the inverse of the generation algorithm, which is where we might actually find those longer stretches.

Lev: That points toward future work needing to investigate those stronger black-box models mentioned in the paper, because that seems to be where the actual construction for longer states resides.

Kai: So, this paper provides a concrete oracle separation showing that linear stretching isn't possible under these constraints, and it sets up the direction for future research into achieving longer quantum pseudorandom states.

Conclusion: Kai: That title is quite specific; it suggests there’s a hard ceiling on how much we can extract from these states under these specific conditions.

Mira: It really highlights the constraint imposed by the oracle structure, showing that the mathematical possibility of stretching doesn't translate into a physical reality without changing those underlying assumptions.

Lev: From an error-correction standpoint, that implies any protocol relying on this kind of stretching needs to be fundamentally rethought if we want to scale it up for real hardware.

Kai: Exactly; it’s not just about finding a better algorithm, it’s about recognizing where the construction itself runs into a wall when we keep the access black-box.

Mira: The authors are showing that the structural properties of those quantum states, specifically how they interact with the chosen oracle, dictate this limit on length scaling.

Lev: If we have to use quadratic scaling just to get slightly longer stretches, that puts a serious burden on our qubit counts for any useful application.

Kai: That’s what I’m trying to get at; it means the resource cost for achieving even modest increases in output size jumps much faster than expected.

Mira: The authors are pointing out a fundamental difference between classical and quantum randomness resource bounds when viewed through the lens of black-box access models.

Lev: It really delineates where our current understanding of these primitives hits a limit when we don't have access to more powerful tools like querying the inverse generation algorithm.

Kai: So, this paper sets up a clear boundary on what’s achievable with limited access, which leads us to think about what kind of stronger access models might actually allow for those longer constructions.

Boyang Chen, Andrea Coladangelo, Yao-Ting Lin, Nikos Skoumios, Justin Tysdal, Yiming Wang

Department of Computer Science and Technology, Tsinghua University · Paul G. Allen School of Computer Science & Engineering, University of Washington

quant-ph, cs.CR

Submitted: 2026-06-23

Updated: 2026-10-05

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 92/100

The gist: Pseudorandom states are fundamental quantum primitives, and this work establishes a black-box separation between single-copy secure pseudorandom states (1PRS) with different output lengths.

Key concepts

Single-Copy Secure Pseudorandom States (1PRS): These are fundamental quantum primitives that generate states indistinguishable from truly random states, but only using a single copy of the generator. The paper investigates whether these secure states can be extended to much longer output lengths than initially suggested.
Black-Box Separation: This refers to proving that two classes of objects (in this case, 1PRS with different output lengths) are fundamentally different when only limited access is allowed. It means you cannot transform a short secure state into a very long one using only the defined black-box operations.
Common Haar Random State (CHRS) Oracle: This is a specific quantum oracle that allows an adversary to sample states from various Haar measures. It provides access to a family of i-qubit states, which is crucial for constructing the oracle separation used to show the impossibility of long stretching.
Effective Number of CHRS States: This concept bounds how many copies of the basic CHRS states are effectively needed by any algorithm trying to generate a pseudorandom state. The paper shows that any generator for a state of length $m$ can be implemented using only polynomially many copies, which limits its ability to achieve super-polynomial stretching.

Terminology

Trace — 12× in this paper · explained in 2 episodes
Common Haar Random State — 10× in this paper
Trace Distance — 5× in this paper · explained in 3 episodes
Adam — 3× in this paper · explained in 2 episodes
Ancilla Qubits — 3× in this paper · explained in 1 episode
Fidelity — 3× in this paper · explained in 2 episodes
Accuracy — 2× in this paper · explained in 1 episode
Core — 2× in this paper · explained in 2 episodes
Generalization — 2× in this paper · explained in 13 episodes
Hilbert Space — 2× in this paper · explained in 2 episodes
One-Way Functions — 2× in this paper
Quantum Circuits — 2× in this paper · explained in 2 episodes
Resource Constraints — 2× in this paper · explained in 3 episodes
Anti-correlation — 1× in this paper · explained in 3 episodes
Entanglement — 1× in this paper · explained in 3 episodes
Fingerprinting — 1× in this paper · explained in 2 episodes
Verification — 1× in this paper · explained in 2 episodes

Summary

Pseudorandom states are fundamental quantum primitives, and this work establishes a black-box separation between single-copy secure pseudorandom states (1PRS) with different output lengths. This finding demonstrates that stretching the output length of a 1PRS from a short stretch, such as length 1.1n, to an arbitrarily long stretch, like length omega(n 2+ε), is impossible in a black-box setting relative to certain oracles.

The Core Problem and Goal

The central question addressed is whether quantum pseudorandomness can be stretched to arbitrary polynomial length in a black-box way, contrasting the classical paradigm where PRGs can be iteratively applied. The paper proves that there exists a quantum oracle relative to which 1PRS with output length m(n) = 1.1n exist, but 1PRS with output length m(n) = omega(n 2+ε) do not exist for any ε > 0. This separation is achieved by constructing an oracle inspired by the Common Haar Random State (CHRS) model, which allows access to a family of states sampled from respective Haar measures.

The Oracle Separation Construction

The separation is defined relative to a quantum channel oracle O = (O1, O2).

O1 is the standard CHRS oracle, providing access to the family of states S = ψi⟩, where ψi⟩ is an i-qubit state.
O2 allows an adversary to run a quantum circuit C on a large number of copies of these states: A number T expressed in unary as 1/T, and the circuit C operates on ϕ⟩ ⊗ O T(i=1 ψ i⟩ ⊗ 2(2i/5)! ⊗ 0⟩ ⊗ T to output a bit.

Bounding the Effective Number of CHRS States

A key structural property is established in Lemma 4.4, which shows that any QPT generation algorithm (GenO) for a state with length m must have an equivalent implementation that uses only polynomially many copies of the CHRS states. This is due to the constraint that GenO must output a pure state on the first m qubits for all families of CHRS states. Specifically, Corollary 4.6 shows that there exists a measure 1 set of oracles O such that if GenO is a 1PRS, there exist unitaries Uk acting on an expanded space where the required number of copies is bounded by s(n) < p(n) and the effective length function l(k, i) < p(k).

The Attack Mechanism

The attack against any 1PRS with output length m = omega(n 2+ε) leverages this structural property. The adversary AO queries O2 to compute the succinct implementations of GenO (the unitaries Uk). Based on whether the resulting parameters fall into Case A or Case B—determined by conditions involving state lengths and copy numbers—AO executes a tailored attack:

In Case A, an OR test based on Permutation tests is used to distinguish the output from Haar random states with advantage at least 1/8n squared.
In Case B, a projective measurement is used to distinguish the distribution of states generated by GenO from the maximally mixed state, achieving a non-negligible advantage when m = omega(n 2+ε).

Implications for Black-Box Constructions

The oracle separation implies that one cannot stretch the output length of a 1PRS in a black-box way (when the construction is given coherent isometry access to the shorter 1PRS). This rules out constructions where a longer-stretch 1PRS can be built from a shorter one using only isometry access to the generator. The result suggests that any construction of long-stretching 1PRS from short-stretching 1PRS must either be non-black-box or utilize stronger black-box access models, such as querying the inverse of the generation algorithm or using ancilla qubits.

Complexity and Implementation Details

The time complexity of computing the required isometry V in Lemma 4.4 is exponential in the number of qubits G acts on, though this can be computed within O2 using a doubleexponential time Turing machine. The implementation of the Permutation test projection Πk involves classical steps such as comparing numbers and performing Schur basis transformations, which are efficient given access to the oracle O2. These details allow for a concrete description of how the attack is carried out efficiently relative to the defined oracles.

Final Conclusion on Stretching

Theorem 4.7 concludes that with probability 1 over the choice of O, 1PRS with output length m(n) = omega(n 2+ε) do not exist relative to O.

Improvements for AI systems

As a fastidious and diligent researcher, I have analyzed this paper, On the Limits of Stretching Quantum Pseudorandomness, which establishes a black-box separation between single-copy secure pseudorandom states (1PRS) with output lengths that are polynomially different (specifically, stretching from 1.1n to at least n squared + ε).

This result fundamentally limits the ability to construct long-stretch quantum pseudorandom generators in a fully black-box setting, even when leveraging powerful oracles like the Common Haar Random State (CHRS) model.

Here are the specific improvements an AI system can undergo based on this scientific finding, categorized by capability:

Stronger Quantum Cryptographic Security Bounds

The paper proves that a 1PRS with output length at least n2 + ε cannot be constructed from a 1PRS with length 1.1n using only isometry access to the generator and channel access to the adversary (Theorem 5.2).

Instead of assuming the existence of long-stretch quantum primitives, AI systems can be designed to operate securely within known bounds:
The system can reliably generate quantum states whose output length is strictly bounded by a linear factor relative to its key size (i.e., output length ≤ 1.1n). This provides a provable security guarantee against adversaries attempting to exploit non-linear stretching techniques.
This allows for the design of protocols in Microcrypt environments where the complexity of the quantum state is tightly controlled, ensuring that cryptographic primitives adhere to known minimal assumptions (like EFI pairs) rather than relying on potentially non-existent long-stretch constructions.

Enhanced Quantum State Generation and Verification

The paper details a constructive attack (Theorem 4.7) against any 1PRS with length n2 + ε, showing that the state can be distinguished from Haar random using an OR test based on specific CHRS oracles. This implies that any attempt to build such a generator is vulnerable to this specific type of quantum attack.

AI systems can incorporate oracle-aware generation mechanisms. If the system needs to generate a state longer than 1.1n, it must explicitly account for the structure of the CHRS family and its associated oracle access (as detailed in Corollary 4.6).
The system can be optimized to use only the succinct unitary implementations (the polynomial number of required CHRS copies) rather than attempting a naive exponential simulation, significantly reducing computational overhead while maintaining security against known black-box stretching attacks.

Robustness Against Black-Box Attacks in Quantum Primitives

The core implication is that the construction of long-stretch quantum primitives from short ones requires stronger access models: either non-black-box methods (requiring the full generation code) or more powerful access to the generator (inverse unitary/ancilla queries).

AI security modules can be designed with a fail-safe mechanism that detects when an adversary attempts to leverage the channel oracle in a way that mimics the attack described in Section 4.2.2.
If the system is operating under an isometry access model (e.g., generating states based on a common reference state), it can be designed to query the necessary purification or ancilla registers required by Lemma 5.4, thereby forcing the adversary into a more complex security reduction that they cannot afford within the black-box constraint.

Algorithmic Efficiency in Oracle-Based Constructions

The paper provides a concrete time complexity analysis for computing the necessary isometries (Lemma 4.3) and implementing the required projective measurements (Section 4.1).

AI systems can utilize this complexity analysis to determine whether an attack is computationally feasible given available resources. For instance, if the system has limited access to the oracle, it can calculate if it possesses enough computational power to run the required polynomial-time GCD algorithms needed in Lemma 4.3 (which takes time related to Dpoly(T)poly(N, D, T)).
This allows for resource-aware quantum circuit design. The AI can choose a construction path that minimizes the number of required oracle queries or ancilla qubits, balancing security requirements against computational cost derived from the complexity bounds in Section 4.3 and 4.5.