No linear stretching of single-copy quantum pseudorandomness

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.