Need for Coherent Access in Constructing Quantum Cryptography

arXiv:2609.40301 · quant-ph, cs.CR · Submitted 2026-09-30 · 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: "Need for Coherent Access in Constructing Quantum Cryptography".

Mira: We construct quantum oracles relative to which quantum-secure one-way functions (OWFs) exist but pseudorandom states (PRS) with superlogarithmic output length do not,

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

Paper summary: Kai: Moving into what the authors actually claim in this paper, they establish an oracle model O where quantum-secure one-way functions exist alongside pseudorandom states that fail to reach superlogarithmic output lengths. The central thesis is that this impossibility arises because of the specific access model they are using, which allows classical oracles to be accessed only classically even by quantum algorithms.

Mira: What this means conceptually is that the distinction hinges on whether we consider a truly black-box construction or one where some form of coherent access—meaning interaction between parts—is permitted, and they show that the former fails for long output lengths without it. They further explore the separation by showing that logarithmic output length pseudorandom function-like states exist relative to these oracles, which creates a separation between classically accessible logarithmic length PRFSs and superlogarithmic length PRSs.

Lev: For us in error correction, this oracle separation is interesting because it means we're not dealing with a single monolithic construction; instead, we have different complexity classes of states depending on the access assumptions. This could inform how we analyze the resilience of quantum states against certain types of attacks that exploit weaker access models.

Kai: The paper lays out a very specific structure for this separation, relying on a dichotomy for general mixed states: either the state has noticeably low purity, or it's nearly pure and has large overlap with some component whose weight is at least one-half N. This split is what drives their subsequent analysis of the constructions.

Mira: That dichotomy is key because it dictates how they proceed with their distinction between PRS and OWFs. They then build a two-stage distinguisher, using repeated SWAP tests for the low-purity case and an OR test involving preparation circuits for every possible branch in the nearly pure case to detect overlap.

Lev: From my side, I wonder how robust these tests are when applied to actual noisy hardware; if the state is only slightly impure or has a small overlap, those detection mechanisms need to be extremely sensitive to avoid false positives or missed opportunities in a real measurement setting.

Kai: The paper concludes its analysis by showing that for any uniform QPT generator, there's a family of oracle-free unitaries that can reproduce each branch's probability and output state upon postselection, which is a major step in their argument against the existence of those long-output states.

Mira: Ultimately, the paper demonstrates that if you restrict yourself to classically accessible oracles without coherent access, you cannot construct pseudorandom states with output lengths exceeding logarithmic bounds, which is a significant result regarding the limits of what can be achieved without that specific quantum interaction structure.

Lev: So, if we want to build something truly complex using these primitives, we have to engineer the system to support that coherent access; it’s not just about having the right mathematical function in place.

Conclusion: Kai: Looking at this paper, "Need for Coherent Access in Constructing Quantum Cryptography," the authors are essentially proving that constructing pseudorandom states with superlogarithmic output lengths is impossible under their specific oracle model unless coherent access is present. They are showing that this limitation stems directly from the access model they've defined.

Mira: The implication here for cryptography is substantial; it suggests that if we want to build certain advanced quantum primitives, we have to account for the interaction between components during construction, moving beyond purely black-box assumptions about those foundational functions. This points toward a need for a more nuanced understanding of how these tools are actually built in practice.

Lev: From an error correction perspective, this tells us that achieving high complexity in quantum states requires not just encoding errors correctly but also ensuring the underlying construction allows for the necessary coherent interactions to manifest in the final state's properties.

Kai: The authors are defining a clear separation between logarithmic and superlogarithmic output lengths of pseudorandom function-like states relative to these oracles, which helps map out exactly where these constructs live within this theoretical framework. This mapping is vital for anyone trying to understand the limits of quantum cryptography primitives.

Mira: It really emphasizes that the nature of the primitives—whether they are short-length or superlogarithmic—is not just a function of the input size, but also depends on the access assumptions baked into how we build them, which is a deep structural point for theorists to consider.

Lev: So, for practical applications, this means when we look at schemes like commitments or encryption based on these states, we can't just assume they work if they are built from components that don't allow for that necessary coherent access.

Kai: And the authors have shown that fully black-box pseudorandom states from one-way functions are impossible without coherent access, which is a concrete limitation they’ve established for building these cryptographic tools.

Mira: That result really frames the conversation around what kind of computational resources—in terms of access structure—are actually required to realize those long-output states we're discussing in quantum cryptography.

Lev: I think this work suggests that the focus needs to shift toward developing constructions that explicitly guarantee this coherent access, rather than just hoping it emerges naturally in a standard black-box setting.

Minki Hhan Changhun Oh Vaughn Sohn

KAIST

quant-ph, cs.CR

Submitted: 2026-09-30

Updated: 2026-09-30

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

Importance score: 92/100

The gist: We construct quantum oracles relative to which quantum-secure one-way functions (OWFs) exist but pseudorandom states (PRS) with superlogarithmic output length do not, demonstrating that coherent

Key concepts

Oracle Model O: This is a mathematical framework defining the computational environment. It consists of a classical random oracle (R) providing one-way functions and a QPSPACE oracle supporting polynomial-width unitary computations. This model sets the stage for analyzing what can be computed in this specific quantum setting.
Coherent Access: This refers to a specific way an algorithm interacts with the oracle, where access is not just random but structured. The paper argues that this coherent access is necessary to build pseudorandom states of superlogarithmic length from shorter ones, distinguishing it from simpler black-box access.
Pseudorandom States (PRS): These are quantum states that are hard to distinguish from truly random quantum states. The paper focuses on proving that these states cannot have output lengths growing faster than logarithmic in the oracle's complexity ($\omega(\log \lambda)$) without coherent access.
Quantum-Secure OWFs: These are one-way functions that are secure against quantum adversaries. The paper establishes their existence within the defined oracle model, showing that these secure functions can be used to build other cryptographic primitives.

Terminology

Adam — 2× in this paper · explained in 2 episodes
Ancilla Qubits — 2× in this paper · explained in 1 episode
Entanglement — 2× in this paper · explained in 3 episodes
Accuracy — 1× in this paper · explained in 1 episode
Adaptivity — 1× in this paper · explained in 1 episode
Annual Symposium on Foundations of Computer Science — 1× in this paper

Summary

We construct quantum oracles relative to which quantum-secure one-way functions (OWFs) exist but pseudorandom states (PRS) with superlogarithmic output length do not, demonstrating that coherent access is necessary for constructing these primitives from classical ones.

The gist

There exists a quantum channel oracle world in which classically computable, quantum-secure OWFs exist, but PRS with output length m(λ) = ω(log λ) do not exist.

Oracle Model and Separation Basis

The work defines an oracle model O = (R, QPSPACE), where R is a classical-accessible random oracle providing OWFs, and QPSPACE is a QPSPACE oracle supporting polynomial-width unitary computations. The separation relies on the distinction between access models: coherent access increases the power of both honest algorithms and adversaries [AK22]. This model shows that fully black-box PRS length extension from logarithmic to superlogarithmic output length must use coherent access to the underlying short PRS.

Construction of OWFs and Classical Primitives

Theorem 4.1 establishes the existence of quantum-secure OWFs relative to O. The classical function family is defined as fλ(x):= Rλ(x). Corollary 4.2 shows that this oracle world supports several classical primitives, including:

quantum-secure PRGs with any polynomial output length,
quantum-secure PRFs with classical queries,
IND-CPA-secure SKE and EUF-CMA-secure MAC, and
statistically binding, computationally hiding interactive bit commitments.

Oracle Separation of PRS from OWFs

The main result proves the impossibility of constructing PRS with output length m(λ) = ω(log λ) relative to O. The proof utilizes a dichotomy for general mixed states: one of the following holds: (Case 1) The state ρ has noticeably low purity. (Case 2) The state ρ is nearly pure and has large overlap with some component ψi⟩ whose weight satisfies pi ≥ 1/2N.

Construction of Oracle-Free Branches

The proof proceeds by constructing a two-stage distinguisher. In the low-purity case, repeated SWAP tests detect an antisymmetric outcome with constant probability. In the nearly pure case (Case 2), we construct preparation circuits for all possible branches and use an OR test to detect whether any candidate has sufficiently large overlap with the output state. Lemma 5.3 guarantees that for any uniform QPT generator GO, there exist a family of oracle-free unitaries that can reproduce each actual branch's probability and output state upon postselection.

Amplified Candidate States for OR Test

The construction of the OR test involves enumerating all possible oracle-query records d. Lemma 5.3 allows the construction of a unitary Ud that, when postselected on the all-zero outcome, prepares the normalized output state ψi⟩ for each branch i. The adversary uses this to construct an oracle-free circuit containing, for every actual branch, a circuit that reproduces its output state and preparation probability upon postselection. The final attack involves using L copies of the challenge state for the OR test and showing that the acceptance probability on PRS outputs is at least 1/28, while on Haar-random states it is bounded by 2(-λ). This yields a non-negligible advantage for distinguishing PRS from Haar-random states.

Adversary and Final Conclusion

The adversary distinguishes PRS outputs from Haar-random states in polynomial time with a single query to QPSPACE. The acceptance probability on PRS is at least 1/28, while the acceptance probability on Haar-random states is at most 2(-λ). Since L is polynomial and m = ω(log λ), the advantage at least 1/28 − 2(-λ) remains non-negligible, proving that PRS with output length ω(log λ) do not exist relative to O. The conclusion emphasizes that coherent access plays a crucial role in constructing PRS or many quantum cryptographic primitives. This result suggests that the relative strength of minicrypt and microcrypt depends on the oracle access model. In this model without coherent access, minicrypt does not suffice for microcrypt! (Page 4). All honest algorithms are classical polynomial-time algorithms using only classical queries to R. Computational security holds against QPT adversaries with the full access to O prescribed by our oracle model. All candidate preparation circuits, amplified preparation circuits, and the OR test circuit used in this procedure have polynomial width and can be printed in exponential time by a classical Turing machine with a polynomial-length description that never queries R. (Page 17). The final result is that fully black-box PRS from OWFs are impossible without coherent access. (Page 3).

Improvements for AI systems

As a meticulous researcher, I have analyzed this paper, Need for Coherent Access in Constructing Quantum Cryptography, which establishes a fundamental oracle separation between quantum-secure One-Way Functions (OWFs) and Pseudorandom States (PRS) when restricted to classically accessible oracles.

Here are the specific improvements that can be made to AI systems based on these findings, along with the capabilities of such an improved system:

The core finding is that constructing complex quantum primitives like Pseudorandom States (PRS) from simpler classical primitives (OWFs) requires a highly constrained access model—specifically, it necessitates coherent access to the underlying oracles. When restricted to classically accessible oracles (where even quantum algorithms can only make classical queries), PRS with superlogarithmic output length are provably impossible.

This research provides a concrete mathematical barrier that dictates the necessary computational resources and structure for building secure cryptographic primitives.

The following improvements are tailored for AI systems designed to operate in, or model the limitations of, quantum-secure cryptographic environments:

Enhanced Security Analysis and Primitive Selection for Quantum Cryptography:
Design of Coherent Oracle Access Protocols for Quantum State Generation:
Development of Complexity Bounds for Quantum Randomness Verification (PRS vs. Haar Random States):

Specific Improvements and Capabilities:

The improved AI system can perform rigorous, provable complexity analysis to determine the minimum required access model (e.g., distinguishing between classically accessible and quantum-accessible) for constructing specific cryptographic primitives.
It can identify when a proposed quantum cryptographic scheme (like a PRS generator) is fundamentally impossible without implementing coherent access structures (e.g., requiring unitary evolution or preservation of quantum coherence).
The system can be used to design and test protocols that explicitly enforce the coherent access requirement, potentially leading to more robust and practically implementable quantum cryptographic constructions that are provably secure against adversaries with limited query capabilities (like those restricted by a QPSPACE oracle).
It can develop advanced methods for distinguishing between true quantum pseudorandom states (PRS) and Haar-random states using refined tests, specifically by leveraging the dichotomy derived in Lemma 5.2: checking for low purity versus high overlap with a dominant pure state component, even when only polynomial resources are available.
The system can model the performance limits of quantum algorithms (like those used in the OR test) against black-box constraints (like QPSPACE), allowing for tighter bounds on the distinguishing advantage an adversary can achieve against a PRS generator versus a truly random state.

In essence, this research allows an AI to transition from merely suggesting cryptographic constructions to mathematically proving the necessary structural requirements (coherence) for those constructions to exist securely under specific computational models.