Function-like pseudorandom unitaries generate pseudorandom quantum processes

AI summary

Overview

Research area: Quantum cryptography and quantum pseudorandomness — specifically, the theory of pseudorandom unitaries (PRUs), pseudorandom states, and pseudorandom quantum processes.

Technical level: Advanced. The paper is written for researchers comfortable with quantum oracle security games, hybrid arguments, unitary designs, quantum combs, and standard cryptographic primitives (PRFs, PRPs, qPRFs).

Scope (one sentence): The paper introduces pseudorandom function-like unitaries (PRFUs) — a single short key that generates an entire family of independently Haar-looking unitaries indexed by public labels — and proves security under both classical-label and coherent-label access, then lifts these to pseudorandom channels, quantum combs, and one-key variable-width PRUs.

What This Paper Is About

A single pseudorandom unitary (PRU) emulates one persistent Haar-random unitary, but many quantum tasks need a whole collection of independent random-looking evolutions — one per context, nonce, register width, memory address, or time step — and managing a separate secret key for each is impractical. This paper asks whether one short master key can generate an adaptively addressable family of pseudorandom unitaries, so that querying with the same public label always returns the same unitary, and the whole family is indistinguishable from assigning an independently sampled Haar-random unitary to every label. The authors answer yes, give explicit constructions for two different label-access models, and then show that such families can be used to build pseudorandom quantum processes (channels and combs) rather than just individual operations.

Key Contributions

1. Definition and construction of PRFUs (pseudorandom function-like unitaries). The paper formalizes the ideal object — a function-like Haar random family in which each label (x) indexes an independent Haar-random unitary (H_x) — and defines a PRFU as an efficient keyed family ({G_k(x)}) indistinguishable from it under adaptive quantum queries. Two access models are separated: classical-label access (only the label wire is classical; data, reference, and adversary memory stay quantum) and coherent-label access (the label is a quantum register that may be in superposition or entangled, with a query applying the controlled unitary (W_k = \sum_x |x\rangle\langle x|_L \otimes G_k(x))).

2. Classical-label construction from a post-quantum PRF plus a PRU. The construction is (G_k(x) := V_{F_k(x)}), where (F_k) is a post-quantum pseudorandom function deriving the seed and ({V_a}) is an inner adaptive forward PRU family. The reduction handles adaptively chosen labels in order of first occurrence, requiring at most (q) hybrid transitions for (q) queries, independently of the label-domain size. A key technical ingredient is an efficiently implementable Haar proxy obtained unconditionally from amplified relative-error permutation-function-Clifford (PFC) designs; the proxy is a resource of the proof, not a component of the construction. This yields classical-label forward security whenever the PRU acts on (n(\lambda) = \omega(\log \lambda)) qubits, and extends to strong security (inverse-oracle access) when the inner PRU is strong.

3. Coherent-label construction and proof via indexed path recording. The coherent-label family incorporates the label directly into the permutation and phase primitives, forming an indexed PFC ensemble, built from a quantum-secure pseudorandom function (qPRF) and assuming a tweakable in-place pseudorandom permutation. Because a single coherent query can have support on every label, the first-occurrence hybrid argument of the classical case does not apply; the authors use indexed path recording to account for interference between query histories involving different labels. An access hierarchy (Proposition 1) is established: coherent-label forward security implies classical-label forward security, and strong security implies forward security, with the converse implications not claimed.

4. Lifting from unitaries to quantum processes and flexible key reuse. PRFUs are used to construct pseudorandom quantum combs (sequences of operations connected by inaccessible internal memory), with a public process label giving a whole family of combs secure under interleaved interactions. Combining PRFUs with unitary gluing yields a one-key family of variable-width PRUs whose supported polynomially bounded register widths can be chosen after key generation. The paper also lists applications: nonce-resolved quantum authentication, coherently masked QRAM queries, and efficient emulation of random multi-time dynamics.

Main Findings

• Classical-label lifting bound (Theorem 1): For any nonuniform QPT adversary making at most (q = q(\lambda)) classical-label forward calls, the distinguishing advantage is bounded by (\mathrm{Adv}_F^{\mathsf{prf}}(\mathcal{B}F;\lambda) + \sum{j=1}^{q}\mathrm{Adv}_V^{\mathsf{pru},\rightarrow}(\mathcal{B}_j;\lambda) + 2q\eta), where (\eta) is the Haar-proxy error. Each (\mathcal{B}_j) makes at most (q) forward calls to its single-unitary challenge.

• Efficient, unconditional Haar proxies (Proposition 2): When (C_0 q \le 2^{n/4}) for a universal constant (C_0 \ge 1), an efficiently samplable and implementable (n)-qubit forward ((q,\eta)) Haar proxy exists with sampling time and circuit size in (\mathrm{poly}(n, q, \log(1/\eta))). The explicit ensemble is an (m)-fold product of independent, efficiently derandomized PFC layers with (m = O(q + \log(1/\eta)/n)), so this step introduces no extra cryptographic hardness assumption.

• Existence of classical-label PRFUs (Corollaries 1 and 2): Given a post-quantum secure PRF, an adaptive forward PRU, and (n(\lambda) = \omega(\log \lambda)), the family (G_k(x) = V_{F_k(x)}) is a classical-label adaptive forward PRFU; with a strong inner PRU it is a classical-label adaptive strong PRFU. The proxy may be chosen after fixing the adversary's query bound, for example with error (\eta = 2^{-\lambda}), while (G_k) itself remains fixed and independent of both choices.

• Explicit PFC instantiation (Corollary 3): Writing (N = 2^{n(\lambda)}), the ideal PFC ensemble is (P_\pi \Phi_h C) with (P_\pi = \sum_z |\pi(z)\rangle\langle z|), (\Phi_h = \sum_z (-1)^{h(z)}|z\rangle\langle z|), and (C) an independent unitary 2-design such as a uniformly random Clifford. Its distinguishing advantage from Haar is at most (4t(t-1)/(N+1)) for (t \le N). Splitting the outer PRF output into three components ((F_k^{(\mathsf{P})}, F_k^{(\mathsf{F})}, F_k^{(\mathsf{C})})) gives the explicit family (G_k^{\mathsf{PFC}}(x) = P_{\pi_{F_k^{(\mathsf{P})}(x)}} \Phi_{h_{F_k^{(\mathsf{F})}(x)}} C_{F_k^{(\mathsf{C})}(x)}), secure when (q,\varepsilon_{\mathsf{C}} = \mathrm{negl}(\lambda)) for the 2-design sampler's total-variation error and (n(\lambda) = \omega(\log \lambda)). The three primitives are known from quantum-secure one-way functions.

• Coherent-label security bound: The indexed path-recording analysis bounds the observer's advantage in distinguishing the ideal indexed PFC ensemble from independent Haar-random unitaries by (2q(q-1)/(2^n+1)) for query number (q < 2^n), yielding coherent-label forward security when the PRFUs act on (n(\lambda) = \omega(\log \lambda)) qubits.

• Access-model hierarchy (Proposition 1): Classical-label access is exactly coherent-label access with full dephasing of the label register in the computational basis before each query, so coherent-label forward security implies classical-label forward security; strong security implies forward security. The paper explicitly states that the inverse implications are not necessarily true.

• Process-level results: Retaining private memory and discarding part of the output turns label-indexed unitaries into labeled families of quantum channels; multi-time interventions with inaccessible internal memory are captured by quantum combs (quantum strategies), which are not described by the endpoint channel or its Choi state. The resulting pseudorandom combs remain indistinguishable from Haar-built combs even under adaptive interventions between operations, and function-like comb families remain secure under interleaved interactions with different family members.

• No empirical benchmarks are reported. The paper is a theory contribution; the excerpt contains no dataset sizes, simulation results, or numeric experiments beyond the cryptographic advantage bounds listed above.

Methodology in Plain English

The authors work entirely at the level of security proofs, using a chain of "hybrid" experiments — a standard cryptographic technique where the real construction is transformed step by step into the ideal Haar object, with each step shown to be undetectable.

For classical labels, each query reveals at most one new label, so the proof can walk through the labels in the order they first appear, maintaining a lazily filled table of at most (q) entries. For each label, the inner PRU is swapped for an efficiently implementable Haar proxy — a circuit ensemble that is statistically indistinguishable from Haar for a bounded number of queries, built from derandomized PFC designs. Because the proxy is efficient, an adversary distinguishing consecutive hybrids can be converted into a distinguisher against the PRU, and after all proxies are in place, the proxy-versus-Haar statistical gap gives the final additive term.

For coherent labels that trick fails: one query can touch every label at once while preserving interference, so there is no online ordering of "new labels." The authors instead attach the label to the permutation and phase of a PFC-style unitary, producing an indexed ensemble, and analyze it with indexed path recording — a technique that tracks the records of the permutation and function along each computational path, so that superpositions over labels and data can be reasoned about as a whole. Computational hybrids then replace the ideal indexed primitives with quantum-secure pseudorandom versions.

Finally, the process-level results are obtained by lifting: adding an inaccessible environment register and tracing out part of the output produces channels; keeping the internal memory across successive labeled calls produces combs. Reusing a single key across different register widths is achieved by gluing local unitaries derived from public labels so that they jointly behave like independent Haar-random unitaries.

Why This Matters

Impact on research. Quantum pseudorandomness has so far been developed mostly for individual objects: one state, one unitary. This work extends the paradigm to efficiently generated families of random-looking quantum dynamics, in the same spirit that pseudorandom function-like states (PRFS) extended pseudorandom states. It also connects two previously separate threads — PRUs and random-channel/quantum-comb ensembles — and shows that a single key can serve an unbounded, adaptively chosen set of contexts, which is the operational requirement in most cryptographic settings.

Applications named in the paper:

• Nonce-resolved quantum authentication: public labels distinguish authentication contexts, avoiding a separate key per nonce.
• Coherently masked QRAM queries: memory addresses act as coherent labels that mask the data being queried.
• Efficient emulation of random multi-time dynamics: labeled unitaries at successive time steps reproduce random multi-time processes without sampling independent Haar unitaries.
• One-key variable-width PRUs: a single key supports polynomially bounded register widths chosen only after key generation, extending a fixed-register PRU without extra secret keys.

Industry relevance. The work targets the cryptographic layer of quantum computing rather than hardware. It is relevant to companies building quantum processors and quantum-safe security products (co-author Kishor Bharti is listed as currently at IonQ), to efforts involving QRAM architectures, and to anyone designing key-management schemes for quantum-era protocols where the number of required random operations grows dynamically and per-context key storage is a bottleneck.

Future Directions

• Closing the access hierarchy. The paper proves that coherent-label security implies classical-label security but explicitly states that the converse is not necessarily established. Whether classical-label PRFUs can be upgraded to coherent-label security, or whether a separation exists, remains open in the presented material.

• Reducing cryptographic assumptions for the coherent-label construction. The coherent-label family relies on a quantum-secure PRF plus a tweakable in-place pseudorandom permutation. Determining whether weaker or more standard primitives suffice — paralleling how the classical-label case needs only a post-quantum PRF plus a PRU — is a natural next step.

• Detailed limitations analysis. The paper states that Sections V–VII cover the process liftings, applications, and limitations, but the specific limitations are not contained in the excerpt analyzed here; they would need to be read from the full text to be assessed.

• Realizing the applications concretely. Nonce-resolved quantum authentication, coherently masked QRAM, and random multi-time dynamics emulation are identified as supported use cases; the paper presents them as consequences of the PRFU framework rather than as implemented protocols with resource estimates, leaving protocol-level design and cost analysis to future work.

Target Audience

Quantum cryptographers and theoretical computer scientists working on pseudorandomness, oracle separation, and quantum-secure primitives; researchers in quantum information theory interested in random channels, quantum combs, and unitary designs; and protocol designers who need a compact key-management scheme for many random-looking quantum operations. The paper assumes fluency with quantum oracle security games and reduction-based proofs, so it is best suited to readers with graduate-level background in quantum complexity or cryptography.

Authors’ abstract

Haar-random unitaries provide a canonical model of generic random quantum evolution, but they typically have exponential description and circuit complexity. Although pseudorandom unitaries efficiently emulate a single Haar-random unitary, many tasks require an entire reusable family of independently random-looking operations. We introduce pseudorandom function-like unitaries (PRFU), which generate such a family indexed by public labels using only a single short key. We distinguish classical- and coherent-label access and establish security under adaptive quantum queries. For classical labels, we provide a generic construction from a post-quantum pseudorandom function and a pseudorandom unitary. For coherent labels, we use an indexed path-recording framework to analyze interference across labels and prove security of a construction based on quantum-secure function and permutation primitives. We further show that PRFUs generate pseudorandom channels and quantum combs with private memory, which are secure against adaptive interventions and concurrent sessions. Combining PRFUs with unitary gluing yields a one-key family of pseudorandom unitaries whose supported register widths can be chosen after key generation. Further applications include nonce-resolved quantum authentication, coherently masked QRAM queries, and efficient emulation of random multi-time dynamics. Our results extend quantum pseudorandomness from individual operations to efficiently generated families of random-looking quantum dynamics.