Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2404.03295 · Lecture notes in computer science

The Power of a Single Haar Random State: Constructing and Separating Quantum Pseudorandomness

Boyang Chen, Andrea Coladangelo, Or Sattath

Published Jan 1, 2025• 7 citations
arXivHTMLPDF
DOI
10.1007/978-3-031-91098-2_5

Related papers

Pseudorandom Function-Like States from Common Haar Unitary

Minki Hhan, Shogo Yamada

arXiv:2411.03201•Lecture notes in computer science•Dec 2, 2025•1 citation

Pseudorandom Quantum States

Zhengfeng Ji, Yi-Kai Liu, Fang Song

Lecture notes in computer science•Jan 1, 2018•123 citations

On Limits on the Provable Consequences of Quantum Pseudorandomness

Samuel Bouaziz--Ermann, Minki Hhan, Garazi Muguruza +1 more

There are various notions of quantum pseudorandomness, such as pseudorandom unitaries (PRUs), pseudorandom state generators (PRSGs), pseudorandom function-like state generators (PRFSGs) and quantum-computable PRGs. Unlike the different notions of classical pseudorandomness, which are known to be existentially equivalent to each other, the relations among quantum pseudorandomness have yet to be fully established. We present evidence suggesting that some forms of quantum pseudorandomness are unlikely to be constructed from the others. This indicates that quantum pseudorandomness behaves quite differently from classical pseudorandomness. Our main result is a unitary oracle separation where log-length output PRFSGs exist but quantum-computable pseudorandom generators (QPRGs) with negligible correctness error do not. This result suggests that the inverse-polynomial error in the state-of-the-art construction of QPRGs from log-length PRSGs is inherent. To achieve this, we prove a novel differential geometric barrier theorem for the product Haar measure on quantum states which replaces the usual concentration inequalities by certifying a non-negligible ``gap'' between two large trace-separated sets. Our separation is based on an oracle that outputs Haar random quantum states for each bit string, which can be viewed as a quantum version of the random oracle model, where output strings are replaced by quantum states. Variations of this oracle can be used to study other relationships between quantum cryptographic primitives, and we use it to achieve partial separations, that highlight technical difficulties when dealing with ancillary registers, measurements, and adaptivity in the quantum setting.

arXiv:2510.05393•Oct 6, 2025•0 citations

Pseudorandom Density Matrices

Nikhil Bansal, Wai‐Keong Mok, Kishor Bharti +2 more

Pseudorandom states (PRSs) are state ensembles that cannot be efficiently distinguished from Haar-random states. However, the definition of PRSs has been limited to pure states and lacks robustness against noise. In this work, we introduce pseudorandom density matrices (PRDMs), ensembles of n -qubit states that are computationally indistinguishable from the generalized Hilbert-Schmidt ensemble (GHSE), which is constructed from ( n + m ) -qubit Haar random states with m qubits traced out. For m = 0 , PRDMs are equivalent to PRSs, whereas for m = ω ( log  n ) , PRDMs are computationally indistinguishable from the maximally mixed state. PRDMs with m = ω ( log  n ) are robust to unital noise channels and separated in terms of security from PRS. PRDMs can disguise valuable quantum resources as trivial states. In particular, we construct pseudoresource state ensembles, which possess near-maximal entanglement, magic and coherence, but are computationally indistinguishable from resource-free states. PRDMs exhibit a pseudoresource gap of Θ ( n ) vs 0, surpassing previously found gaps. We also render EFI pairs, a fundamental cryptographic primitive, robust to strong mixed unitary noise. Our work has major implications on quantum resource theory. We show that entanglement, magic, and coherence cannot be efficiently tested, and that black-box resource distillation requires a superpolynomial number of copies. We also establish lower bounds on the purity needed for efficient testing and black-box distillation. Finally, we introduce memoryless PRSs, a noise-robust notion of PRS, which are indistinguishable to Haar random states for efficient algorithms without quantum memory, as well as noise-robust quantum money. Our work provides a comprehensive framework of pseudorandomness for mixed states, which yields powerful quantum cryptographic primitives and fundamental bounds on quantum resource theories.

arXiv:2407.11607•PRX Quantum•May 1, 2025•14 citations

Quantum Randomness: From Practice to Theory and Back

Cristian S. Calude

Theory and applications of computability•Jan 1, 2017•15 citations

Quantum Pseudorandom Scramblers

Chuhan Lu, Minglong Qin, Fang Song +2 more

Abstract. Quantum pseudorandom state generators ( PRSG s) have stimulated exciting developments in recent years. A PRSG , on a fixed initial (e.g., all-zero) state, produces an output state that is computationally indistinguishable from a Haar random state. However, pseudorandomness of the output state is not guaranteed on other initial states. In fact, known PRSG constructions provably fail on some initial states. In this work, we propose and construct quantum pseudorandom state scramblers ( PRSS s), which can produce a pseudorandom state on an arbitrary initial state. In the information-theoretical setting, we obtain a scrambler which maps an arbitrary initial state to a distribution of quantum states that is close to Haar random in total variation distance. As a result, our scrambler exhibits a dispersing property. Loosely, it can span an [Formula: see text]-net of the state space. This significantly strengthens what standard PRSG s can induce, as they may only concentrate on a small region of the state space provided that the average output state approximates a Haar random state. Our PRSS construction develops a parallel extension of the famous Kac’s walk, and we show that it mixes exponentially faster than the standard Kac’s walk. This constitutes the core of our proof. We also describe a few applications of PRSS s. While our PRSS construction assumes a postquantum one-way function, PRSS s are potentially a weaker primitive and can be separated from one-way functions in a relativized world similar to standard PRSG s.

arXiv:2309.08941•SIAM Journal on Computing•Aug 21, 2026•1 citation
There are various notions of quantum pseudorandomness, such as pseudorandom unitaries (PRUs), pseudorandom state generators (PRSGs), pseudorandom function-like state generators (PRFSGs) and quantum-computable PRGs. Unlike the different notions of classical pseudorandomness, which are known to be existentially equivalent to each other, the relations among quantum pseudorandomness have yet to be fully established. We present evidence suggesting that some forms of quantum pseudorandomness are unlikely to be constructed from the others. This indicates that quantum pseudorandomness behaves quite differently from classical pseudorandomness. Our main result is a unitary oracle separation where log-length output PRFSGs exist but quantum-computable pseudorandom generators (QPRGs) with negligible correctness error do not. This result suggests that the inverse-polynomial error in the state-of-the-art construction of QPRGs from log-length PRSGs is inherent. To achieve this, we prove a novel differential geometric barrier theorem for the product Haar measure on quantum states which replaces the usual concentration inequalities by certifying a non-negligible ``gap'' between two large trace-separated sets. Our separation is based on an oracle that outputs Haar random quantum states for each bit string, which can be viewed as a quantum version of the random oracle model, where output strings are replaced by quantum states. Variations of this oracle can be used to study other relationships between quantum cryptographic primitives, and we use it to achieve partial separations, that highlight technical difficulties when dealing with ancillary registers, measurements, and adaptivity in the quantum setting.
Pseudorandom states (PRSs) are state ensembles that cannot be efficiently distinguished from Haar-random states. However, the definition of PRSs has been limited to pure states and lacks robustness against noise. In this work, we introduce pseudorandom density matrices (PRDMs), ensembles of n -qubit states that are computationally indistinguishable from the generalized Hilbert-Schmidt ensemble (GHSE), which is constructed from ( n + m ) -qubit Haar random states with m qubits traced out. For m = 0 , PRDMs are equivalent to PRSs, whereas for m = ω ( log  n ) , PRDMs are computationally indistinguishable from the maximally mixed state. PRDMs with m = ω ( log  n ) are robust to unital noise channels and separated in terms of security from PRS. PRDMs can disguise valuable quantum resources as trivial states. In particular, we construct pseudoresource state ensembles, which possess near-maximal entanglement, magic and coherence, but are computationally indistinguishable from resource-free states. PRDMs exhibit a pseudoresource gap of Θ ( n ) vs 0, surpassing previously found gaps. We also render EFI pairs, a fundamental cryptographic primitive, robust to strong mixed unitary noise. Our work has major implications on quantum resource theory. We show that entanglement, magic, and coherence cannot be efficiently tested, and that black-box resource distillation requires a superpolynomial number of copies. We also establish lower bounds on the purity needed for efficient testing and black-box distillation. Finally, we introduce memoryless PRSs, a noise-robust notion of PRS, which are indistinguishable to Haar random states for efficient algorithms without quantum memory, as well as noise-robust quantum money. Our work provides a comprehensive framework of pseudorandomness for mixed states, which yields powerful quantum cryptographic primitives and fundamental bounds on quantum resource theories.
Abstract. Quantum pseudorandom state generators ( PRSG s) have stimulated exciting developments in recent years. A PRSG , on a fixed initial (e.g., all-zero) state, produces an output state that is computationally indistinguishable from a Haar random state. However, pseudorandomness of the output state is not guaranteed on other initial states. In fact, known PRSG constructions provably fail on some initial states. In this work, we propose and construct quantum pseudorandom state scramblers ( PRSS s), which can produce a pseudorandom state on an arbitrary initial state. In the information-theoretical setting, we obtain a scrambler which maps an arbitrary initial state to a distribution of quantum states that is close to Haar random in total variation distance. As a result, our scrambler exhibits a dispersing property. Loosely, it can span an [Formula: see text]-net of the state space. This significantly strengthens what standard PRSG s can induce, as they may only concentrate on a small region of the state space provided that the average output state approximates a Haar random state. Our PRSS construction develops a parallel extension of the famous Kac’s walk, and we show that it mixes exponentially faster than the standard Kac’s walk. This constitutes the core of our proof. We also describe a few applications of PRSS s. While our PRSS construction assumes a postquantum one-way function, PRSS s are potentially a weaker primitive and can be separated from one-way functions in a relativized world similar to standard PRSG s.