⚛️ quantum physics

Function-like pseudorandom unitaries generate pseudorandom quantum processes

This paper introduces pseudorandom function-like unitaries (PRFUs), a cryptographic primitive that efficiently generates families of reusable, random-looking quantum operations indexed by public labels from a single short key, thereby extending quantum pseudorandomness from individual unitaries to complex, multi-time quantum processes secure against adaptive queries.

Original authors: Zitai Xu, Rahul Arvind, Kishor Bharti, Tobias Haug, Dax Enshan Koh, Wai-Keong Mok, Andrew Tanggara, Alexey V. Gorshkov

Published 2026-10-02

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Zitai Xu, Rahul Arvind, Kishor Bharti, Tobias Haug, Dax Enshan Koh, Wai-Keong Mok, Andrew Tanggara, Alexey V. Gorshkov

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the quantum world, randomness is not just a lack of pattern; it is a fundamental resource. When physicists need to model how a complex quantum system behaves, they often imagine a "perfectly random" evolution, a process so chaotic and unpredictable that it mimics the behavior of a truly random coin flip repeated billions of times. This ideal state of randomness, known as a Haar-random unitary, serves as a gold standard for understanding everything from how information scrambles inside black holes to how quantum computers might eventually break encryption. However, there is a catch: describing or building such a perfectly random process requires an amount of information that grows exponentially with the size of the system. For even a modest number of particles, the instructions needed to create this randomness become so vast that no computer could ever store them, let alone run them.

To solve this, scientists have long relied on "pseudorandom" alternatives. These are processes that look random to any observer who does not have the secret recipe, even though they are generated by a simple, short set of instructions. Until now, these pseudorandom tools were limited. They could generate a single random-looking event, but if a scientist needed a whole family of different random events—perhaps one for every second of an experiment, or one for every different memory address in a computer—they had to generate a new, massive secret key for each one. Managing a library of thousands of these giant keys is impractical. The question remained: could a single, tiny secret key generate an entire universe of distinct, random-looking quantum processes, each accessible by a simple public label, without ever revealing the secret?

A team of researchers has now answered this question by introducing a new mathematical object called a pseudorandom function-like unitary. Think of this as a master key that, when combined with a public label like a name or a number, instantly produces a unique quantum operation that looks completely random. If you use the same label twice, you get the exact same operation, ensuring consistency. If you use a different label, you get a completely different operation that appears just as random as the first. The researchers proved that this system is secure against even the most powerful quantum computers, meaning no observer can tell the difference between these generated operations and the ideal, perfectly random ones, provided they do not have the master key.

The team developed two distinct versions of this tool to handle different ways of interacting with the system. In the first version, the label is a standard piece of classical information, like a number typed into a computer. Here, the researchers showed that by combining a secure pseudorandom function with a pseudorandom unitary, they could create a system where the master key derives a unique seed for every label. This construction is robust enough to withstand an adversary who can ask for the result of any label, in any order, and even keep a quantum memory of previous answers to help them guess the next one.

The second version is more sophisticated and handles "coherent" labels. In this scenario, the label itself can exist in a quantum superposition, meaning the system can be asked to apply a random operation to a label that is simultaneously "A" and "B" at the same time. This is a much harder challenge because the quantum interference between these different labels could potentially reveal the secret. To solve this, the researchers used a technique called indexed path recording. This method allows them to track the history of every query across all possible labels simultaneously, proving that even with these complex quantum queries, the system remains indistinguishable from true randomness.

The implications of this work extend far beyond just generating random numbers. The researchers demonstrated that these new tools can be used to build pseudorandom quantum channels and "quantum combs." A quantum comb is a way to describe a sequence of events where a system interacts with its environment over time, retaining a private memory between steps. By using their new tool, the team showed that a single key could generate a whole family of these time-evolving processes. This means a quantum system could simulate a complex, multi-step experiment where the rules change at every step, all driven by one short secret.

This capability opens the door to several practical applications. For instance, it enables a form of quantum authentication where a message is protected by a unique code that changes based on a public "nonce" or number. If an attacker tries to reuse an old number, the system can detect it and reject the message, ensuring that every communication is fresh and secure. It also allows for a new type of quantum memory access, where data can be retrieved from a database in a superposition of addresses, but the retrieved information is masked by a random operation that depends on the address. This hides the contents of the database from anyone who does not hold the master key, even while they are querying it in a quantum state.

Furthermore, the researchers showed that this single-key approach can generate random unitaries for registers of variable sizes. In many quantum algorithms, the size of the data being processed might change, but previously, a new key would be needed for each new size. With this new method, the same master key can generate random operations for a small register, a medium one, or a large one, simply by changing the public label. This flexibility is crucial for building scalable quantum systems that need to adapt to different tasks without the overhead of managing a massive library of keys.

The work also clarifies the relationship between different types of quantum randomness. While it was known how to create a single random unitary, and how to create a family of random quantum states, creating a family of random unitaries was a missing piece. The researchers filled this gap, showing that the transition from a single random operation to a family of them is possible, but it requires specific cryptographic assumptions that differ depending on whether the labels are classical or quantum. They did not just propose a theoretical idea; they provided concrete mathematical constructions and rigorous proofs that these systems work under the most demanding conditions, including adaptive attacks where an adversary learns from every interaction.

Ultimately, this research shifts the paradigm of how we think about generating randomness in quantum systems. Instead of treating each random event as a separate, expensive resource, it treats randomness as a function that can be called upon repeatedly with different inputs. This efficiency is vital for the future of quantum cryptography and simulation, where the ability to generate vast amounts of reproducible, random-looking dynamics from a single secret is a prerequisite for secure communication and complex modeling. The researchers have effectively built a machine that turns a single key into an infinite supply of unique, random quantum behaviors, secure enough to fool even the most advanced quantum observers.

Technical Summary: Function-like Pseudorandom Unitaries Generate Pseudorandom Quantum Processes

Problem Statement

Haar-random unitaries serve as the canonical model for generic random quantum evolution, underpinning phenomena such as decoupling, information scrambling, and quantum cryptography. However, a typical Haar-random unitary possesses exponential description and circuit complexity, rendering them infeasible for practical implementation. While pseudorandom unitaries (PRUs) offer an efficient surrogate for a single random-looking evolution, many cryptographic and physical tasks require a family of independently random-looking operations indexed by public context (e.g., nonces, register widths, or time steps).

Existing approaches to generating such families, such as sampling independent PRU keys for each context, are impractical due to the management overhead of a large, dynamically growing set of secret keys. Furthermore, standard PRUs do not inherently provide security against adaptive quantum queries where an adversary interacts with multiple instances of the family. The paper addresses the need for a primitive that generates an entire adaptively addressable family of pseudorandom unitaries from a single short master key, while maintaining security against adversaries who may query the family adaptively and coherently.

Methodology

The authors introduce Pseudorandom Function-like Unitaries (PRFUs), a keyed family $\{G_k(x)\}_{x \in \mathcal{X}_\lambda}$ where a single key $k$ and a public label $x$ determine an efficiently implementable unitary. The security goal is computational indistinguishability from a function-like Haar random family, where each label $x$ maps to an independently sampled Haar-random unitary $H_x$ .

The paper distinguishes two access models for the label $x$ :

Classical-label access: The label is supplied as a classical bit string. The data and reference registers remain quantum.
Coherent-label access: The label is supplied in a quantum register $L$ , potentially in superposition or entangled with other registers. The oracle applies a controlled unitary $W_k = \sum_x |x\rangle\langle x|_L \otimes G_k(x)$ .

Constructions

1. Classical-Label Construction:
The authors propose a generic construction combining a post-quantum pseudorandom function (PRF) $F_k$ and an adaptive forward PRU family $\{V_a\}$ . The construction is defined as:
$G_k(x) := V_{F_k(x)}$
Here, the PRF derives the seed $a = F_k(x)$ for the inner PRU. The security proof utilizes a "deferred table" hybrid argument, processing labels in the order of their first appearance. A critical component is the use of an efficiently implementable Haar proxy (derived from amplified relative-error Permutation-Function-Clifford (PFC) designs) to simulate intermediate hybrids. This allows the reduction to bound the distinguishing advantage without requiring the inner PRU to be a full Haar proxy for all possible queries, only for the bounded number of queries made by the adversary.

2. Coherent-Label Construction:
For coherent access, the authors construct a PRFU directly using an indexed PFC ensemble. Instead of deriving keys via an outer PRF, the label $x$ is incorporated directly into the phase and permutation primitives. The construction uses:

A quantum-secure pseudorandom function (qPRF) $g_{k_\Phi}(x, z)$ for the phase layer.
A tweakable in-place pseudorandom permutation (qPRP) $\Pi_{k_P}(x, z)$ for the permutation layer.
A shared unitary 2-design $C$ .
The resulting unitary is $W_k^{coh} = \hat{P}_{\Pi} \hat{\Phi}_{g} (I_L \otimes C)$ .
Security is established using an indexed path-recording technique. This method tracks query histories involving superpositions of labels to analyze interference. The proof demonstrates that the ideal indexed PFC ensemble is statistically indistinguishable from independent Haar unitaries up to a bound of $2q(q-1)/(N+1)$ , where $q$ is the query count and $N=2^n$ . Computational security follows by replacing the random primitives with their quantum-secure counterparts.

Extensions to Quantum Processes

The paper extends PRFUs to generate pseudorandom quantum channels and quantum combs (processes with internal memory).

Channels: By applying a PRFU within a Stinespring dilation and discarding the environment, the authors generate pseudorandom function-like channels (PRFCs).
Combs: By assigning distinct PRFU labels to successive "teeth" (operations) of a quantum comb, the authors construct pseudorandom combs. This allows for the emulation of multi-time dynamics with inaccessible memory, secure against adaptive interventions and concurrent sessions.

Key Contributions

Definition of PRFUs: The formalization of pseudorandom function-like unitaries, which generate a family of random-looking unitaries indexed by public labels from a single key.
Classical-Label Construction & Security: A generic construction from post-quantum PRFs and PRUs, proven secure under adaptive classical-label queries using a hybrid argument and Haar proxies.
Coherent-Label Construction & Security: A specific construction based on indexed PFC ensembles using qPRFs and tweakable in-place qPRPs. Security is proven via indexed path-recording to handle label superpositions and interference.
Process Lifting: Demonstrations that PRFUs can be lifted to generate pseudorandom channels and quantum combs, securing processes with private memory against adaptive and concurrent interactions.
Variable-Width PRUs: A method combining PRFUs with unitary gluing to create a one-key family of PRUs where the register width can be chosen adaptively after key generation.
Applications: The paper outlines specific applications including:
- Nonce-resolved quantum authentication.
- Coherently masked QRAM queries (hiding database contents from forward-access observers).
- Efficient emulation of random multi-time dynamics.

Results

Security Bounds: For classical labels, the distinguishing advantage is bounded by the sum of the PRF advantage, the PRU advantage, and a term dependent on the Haar proxy error ( $2q\eta$ ). For coherent labels, the statistical distance to the ideal Haar family is bounded by $2q(q-1)/(N+1)$ , with computational security relying on the hardness of the underlying qPRF and qPRP.
Efficiency: The constructions are efficient, requiring only polynomial time and circuit size relative to the security parameter $\lambda$ and the number of queries.
Variable Widths: The gluing construction successfully generates pseudorandom unitaries for polynomially bounded register widths chosen post-generation, with security preserved across different widths.

Significance and Claims

The paper claims to extend the concept of quantum pseudorandomness from individual operations to efficiently generated families of random-looking quantum dynamics. By introducing PRFUs, the authors bridge the gap between single-instance PRUs and the need for reproducible, context-dependent random evolutions required in advanced quantum protocols.

The work highlights that:

One-Key Paradigm: It is possible to derive an entire adaptively addressable family of pseudorandom unitaries from a single short master key, avoiding the key management issues of independent PRU sampling.
Coherent Security: Security can be maintained even when labels are queried in superposition, a stronger requirement than classical-label security, achieved through specific indexed path-recording techniques.
Process Security: The framework naturally extends to complex quantum processes (channels and combs) with internal memory, providing security against adversaries who can intervene between steps or run concurrent sessions.

The authors note that while the relationship between PRUs and PRFUs is clear for classical labels (via PRF lifting), the relationship for coherent labels remains an open question, as their construction relies on specific primitives rather than a general transformation from a single-instance PRU. Additionally, the construction of the required tweakable in-place qPRP from standard assumptions remains a concrete open problem for future instantiation.