Scalable and (quantum-accessible) adaptive pseudorandom quantum states and pseudorandom function-like quantum state generators
Rishabh Batra, Zhili Chen, Rahul Jain, YaoNan Zhang · 2025
Read Scalable and (quantum-accessible) adaptive pseudorandom quantum states and pseudorandom function-like quantum state generators by Rishabh Batra, Zhili Chen, Rahul Jain, YaoNan Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-22535.txt.
Introduction
Rishabh Batra, Zhili Chen, Rahul Jain, and YaoNan Zhang construct pseudorandom quantum states and function-like state generators with strong guarantees, in a research paper from 2025. Such generators must fool any quantum adversary, even one that feeds quantum inputs and adapts queries over time. Past constructions lacked one or more of scale, quantum access, or adaptivity.
Their isometric method prepares states that sit arbitrarily close to truly random ones. That yields the first generator with all three traits, from a standard assumption on one-way functions. Their quantum access notion is stronger than prior ones, since adversary inputs may be entangled with side registers. Many variants, from long input to classically accessed forms, follow.
Catalog record
| CREATOR | Rishabh Batra, Zhili Chen, Rahul Jain, YaoNan Zhang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 136 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-22535
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Scalable and (quantum-accessible) adaptive pseudorandom quantum states and pseudorandom function-like quantum state generators Rishabh Batra, Zhili Chen, Rahul Jain, YaoNan Zhang Abstract Pseudorandom quantum states (PRS) and pseudorandom function-like quantum state (PRFS) generators are quantum analogues of pseudorandom generators and pseudorandom functions. It is known that PRS (and PRFS) can exist even if BQP = QMA (relative to a quantum oracle) [ Kre21 ] or if P = NP (relative to a classical oracle) [ KQST23 ] , which does not allow for the existence of one-way functions (relative to these oracles). Hence, these are potentially weaker objects than quantum-secure one-way functions, which can be used to do quantum cryptography. A desirable property of PRS and PRFS constructions is scalability, which ensures that the security parameter λ \lambda (which determines indistinguishability from their Haar-random counterparts) is much larger than n n (the number of qubits of the output states). This may be important in some applications where PRS and PRFS primitives are used. We present an isometric procedure to prepare quantum states that can be arbitrarily random (i.e., the trace distance from the Haar-random state can be arbitrarily small for the true random case, or the distinguishing advantage can be arbitrarily small for the pseudorandom case). Our procedure provides a new method for scalable PRS that introduces no entanglement or correlations with the environment. This naturally gives the first construction for scalable and (quantum-accessible) adaptive PRFS assuming quantum-secure one-way functions. Our PRFS construction implies various primitives, including long-input PRFS, short-input PRFS, short-output PRFS, non-adaptive PRFS, and classical-accessible adaptive PRFS [ AQY22 , AGQY22 ] . This new construction may be helpful in some simplification of the microcrypt zoo 1 1 1 https://sattath.github.io/microcrypt-zoo/ . . 1 Introduction Randomness has played an indispensable role in various fields of computer science, such as cryptography, algorithms, complexity theory, and so on. For practical applications, however, using true randomness may be very expensive and difficult to produce. Storing the complete description of a truly random object may be very inefficient. For example, to merely specify a binary truly random function on n -bit inputs, we require an exponentially large description. An object is called pseudorandom if we can generate it efficiently, but an efficient distinguisher cannot distinguish it from a truly random object. Using pseudorandomness enables us to design efficient protocols that require only short random seeds. In classical cryptography, pseudorandomness has been fundamental for the construction of efficient protocols that are secure against attacks by efficient adversaries. Let U_{n} represent the uniform distribution on n bits. A pseudorandom generator (PRG) is an efficiently computable function, \mathrm{PRG}:\{0,1\}^{n}\rightarrow\{0,1\}^{l(n)} such that l(n)>n and \mathrm{PRG}(U_{n}) is computationally indistinguishable from U_{l(n)} . A one-way function (OWF) is a function that is efficiently computable and hard to invert. The existence of one-way functions is a widely used computational assumption in classical cryptography. A pseudorandom function family (PRF) is a collection of efficiently computable functions that are computationally indistinguishable from a truly random function. It is known that in the classical world, one-way functions, PRG, and PRF are equivalent to each other [ Gol01 ] . In the quantum world, however, the story is not as straightforward. Ji, Liu, and Song [ JLS18 ] first introduced the notion of pseudorandom quantum states (PRS), which are efficiently generatable pure quantum states that are computationally indistinguishable from truly random (Haar-random) quantum states — even when an adversary has access to multiple copies of the state. PRS can be thought of as a generalization of PRGs with quantum outputs. Similarly, pseudorandom function-like quantum state (PRFS) generators, first introduced by Ananth, Qian, and Yuen [ AQY22 ] , are the quantum analogue of PRF. [ JLS18 ] showed that we can construct PRS from any quantum-secure one-way function by applying a random phase to each computational basis element (here \{f_{k}(\cdot)\}_{k} is a quantum-secure PRF). \ket{\phi_{k}}=\frac{1}{\sqrt{N}}\sum_{z=0}^{N-1}\left(e^{2\pi i/N}\right)^{f_{k}(z)}\ket{z}. Brakerski and Shmueli [ BS19 ] proved that the binary phase state is also pseudorandom. \ket{\phi_{k}}=\frac{1}{\sqrt{N}}\sum_{z=0}^{N-1}(-1)^{f_{k}(z)}\ket{z}. These elegant constructions guarantee that t -copies of such a state are close to t -copies of the Haar-random state when the number of qubits is sufficiently large. However, since these constructions are actually very different from the true Haar-random state, they are not scalable . Scalability is a desirable property in the quantum setting. Classically, once we generate an n -bit (pseudo)random string, we can freely use the first k bits as a k -bit (pseudo)random string. However, for the quantum case, even if we already have an n -qubit Haar-random state, if we take the first k qubits and trace out the rest, the result is typically very different from a k -qubit Haar-random state. Therefore, just considering the first k -qubits of an n -qubit pseudorandom state may not give a pseudorandom state. In fact, Bouaziz-Ermann and Muguruza [ BEM24 ] show that quantum pseudorandomness cannot be shrunk in a black-box way. In [ JLS18 ] and [ BS19 ] , the security parameter \lambda is (essentially) the same as the qubit number n . When n is much smaller than \lambda , the distinguishing advantage is not negligible in \lambda for the above constructions. Brakerski and Shmueli [ BS20 ] gave the first scalable PRS generator construction in which the security parameter \lambda can be chosen independent of the length n of the output quantum state. In [ JLS18 ] and [ BS19 ] , randomizing the phase was enough. But for achieving scalable pseudorandom states, randomizing the amplitudes of the quantum state is also needed. Their idea is to prepare a quantum state whose coefficients follow the normalized standard Gaussian random vector (see Definition 3.22 ). With infinite precision and perfect sampling algorithms, such is state exactly behaves like a true Haar-random state. They first use a pseudorandom function to do (complex) Gaussian sampling and then do quantum rejection sampling to generate the state corresponding to the sampled Gaussian random variables. Our contribution In this work, we present an isometric procedure to prepare quantum states that can be arbitrarily random (i.e. the trace distance from the Haar-random state can be arbitrarily small for the true random case, or the distinguishing advantage can be arbitrarily small for the pseudorandom case). This procedure provides a new method for scalable pseudorandom quantum state (PRS) generators, and yields the first construction for scalable and (quantum-accessible) adaptive pseudorandom function-like quantum state (PRFS) generators, assuming quantum-secure one-way functions [ Zha21 ] . Our main result is informally stated as follows: Theorem 1.1 (Informal) . Assuming scalable quantum-secure pseudorandom function generators ( Definition 3.27 ), there exists scalable and adaptive pseudorandom function-like quantum state generators ( Definition 3.33 ). Combining 3.29 that quantum-secure one-way functions ( Definition 3.25 ) imply scalable quantum-secure pseudorandom function generators ( Definition 3.27 ), our work shows that quantum-secure one-way functions imply scalable and adaptive pseudorandom function-like quantum state generators ( Definition 3.33 ). 1.1 Comparison with prior works In Table 1 and Table 2 , we compare our work with prior PRS and PRFS constructions. Work by PRS Construction Scalable Isometry [ JLS18 ] Random phase No Yes [ BS19 ] Binary phase No Yes [ BS20 ] Quantum rejection sampling Yes No This work Qubit-by-qubit rotation Yes Yes