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:2609.03065

Distinctness threshold for pseudorandom unitaries

Asad Raza, Jens Eisert, Bill Fefferman

quant-phcs.CCcs.CRSubmitted Sep 2, 2026• Announced Sep 4, 2026• 0 citations
arXivHTMLPDF

Abstract

Pseudorandomness is increasingly recognized as a key property of ensembles in quantum information theory, statistical mechanics, and quantum many-body physics. Yet it appears in two conceptually different forms: statistical pseudorandomness, embodied by unitary designs, and computational pseudorandomness captured by pseudorandom unitaries (PRUs). The relationship between these two forms of pseudorandomness remains surprisingly poorly understood. Existing PRU constructions reveal this interplay where a statistically randomizing ingredient, a unitary design, is combined with classical cryptographic primitives to produce computational pseudorandomness. We show that statistical pseudorandomness is not necessary for computationally pseudorandom unitaries. We do this by replacing the unitary $2$-design layer in the existing constructions with ensembles that are not even state $1$-designs, yet are sufficiently {\em distinct}, a property we identify to be necessary for any PRU. This yields new non-adaptively secure PRU ensembles whose computational pseudorandomness is obtained without an underlying statistically pseudorandom quantum ensemble, such as a $2$-design. We characterize distinctness via an entangled analogue of anticoncentration and use it to show that distinctness already captures constraints on coherence and imaginarity of PRUs, while identifying broad classes of inputs for which the latter obstruction disappears, enabling real-valued PRUs even for certain (maximally) entangled states. As an application, we use lack of distinctness to constrain the conjectured pseudorandomness of the random phase-Hadamard ensemble to form a PRU.

Related papers

Pseudorandom unitaries with non-adaptive security

Tony Metger, Alexander Poremba, Makrand Sinha +1 more

Pseudorandom unitaries (PRUs) are ensembles of efficiently implementable unitary operators that cannot be distinguished from Haar random unitaries by any quantum polynomial-time algorithm with query access to the unitary. We present a simple PRU construction that is a concatenation of a random Clifford unitary, a pseudorandom binary phase operator, and a pseudorandom permutation operator. We prove that this PRU construction is secure against non-adaptive distinguishers assuming the existence of quantum-secure one-way functions. This means that no efficient quantum query algorithm that is allowed a single application of $U^{\otimes \mathrm{poly}(n)}$ can distinguish whether an $n$-qubit unitary $U$ was drawn from the Haar measure or our PRU ensemble. We conjecture that our PRU construction remains secure against adaptive distinguishers, i.e. secure against distinguishers that can query the unitary polynomially many times in sequence, not just in parallel.

arXiv:2402.14803•Feb 22, 2024•2 citations

Derivatives of Quantum Randomness: Separating Pseudorandom Unitaries from Pseudorandom (Function-like) States

Minki Hhan

Quantum computation gives rise to new pseudorandom primitives for states and unitaries, including pseudorandom state generators (PRSGs), pseudorandom function-like state generators (PRFSGs), and pseudorandom unitaries (PRUs). In this paper, we show a full unitary oracle separation between PRFSGs and PRUs. The separation holds between the strongest state notion and the weakest unitary notion: even adaptively secure, quantum-accessible PRFSGs do not imply non-adaptively secure, forward-only PRUs, even when their implementations are allowed to be non-unitary and use an arbitrary number of ancillary qubits. This reveals a fundamental distinction between pseudorandomness for quantum states and for quantum unitaries. Our main technical idea is to view a candidate PRU construction with access to state generation oracles as a map from the underlying oracle states to implemented unitaries, and to study the derivatives of this map. These derivatives are inherently low rank, and we exploit this low-rank structure to distinguish the resulting unitaries from truly random ones. We believe this differential perspective may be useful for studying other structural questions about quantum states and unitaries.

quant-pharXiv:2609.14626•Sep 15, 2026•0 citations

Pseudorandom unitaries are neither real nor sparse nor noise-robust

Tobias Haug, Kishor Bharti, Dax Enshan Koh

Pseudorandom quantum states (PRSs) and pseudorandom unitaries (PRUs) possess the dual nature of being efficiently constructible while appearing completely random to any efficient quantum algorithm. In this study, we establish fundamental bounds on pseudorandomness. We show that PRSs and PRUs exist only when the probability that an error occurs is negligible, ruling out their generation on noisy intermediate-scale and early fault-tolerant quantum computers. Further, we show that PRUs need imaginarity while PRS do not have this restriction. This implies that quantum randomness requires in general a complex-valued formalism of quantum mechanics, while for random quantum states real numbers suffice. Additionally, we derive lower bounds on the coherence of PRSs and PRUs, ruling out the existence of sparse PRUs and PRSs. We also show that the notions of PRS, PRUs and pseudorandom scramblers (PRSSs) are distinct in terms of resource requirements. We introduce the concept of pseudoresources, where states which contain a low amount of a given resource masquerade as high-resource states. We define pseudocoherence, pseudopurity and pseudoimaginarity, and identify three distinct types of pseudoresources in terms of their masquerading capabilities. Our work also establishes rigorous bounds on the efficiency of property testing, demonstrating the exponential complexity in distinguishing real quantum states from imaginary ones, in contrast to the efficient measurability of unitary imaginarity. Further, we show an exponential advantage in imaginarity testing when having access to the complex conjugate of the state. Lastly, we show that the transformation from a complex to a real model of quantum computation is inefficient, in contrast to the reverse process, which is efficient. Our results establish fundamental limits on property testing and provide valuable insights into quantum pseudorandomness.

arXiv:2306.11677•Quantum•Jun 4, 2025•20 citations

How to Build Pseudorandom Unitaries in Microcrypt

Aditya Gulati, Dakshita Khurana, Kabir Tomer

We provide the first evidence relative to a classical oracle that pseudorandom unitaries (PRUs) can exist without quantum-computable one-way functions. To obtain this result, we first prove that five independent random diagonal phase layers interleaved with Hadamard transforms \[ U=F_5HF_4HF_3HF_2HF_1 \] form a strong PRU with security under adaptive, controlled access to the unitary, its inverse, transpose, and complex conjugate. Our main result is that, when the phase layers are implemented using a classical random oracle O, the construction remains secure against uniform BQP adversaries with coherent access to suitable Boolean completions of classical-input $QMA^{PH}^{O}}$ decision problems. Such an adversary can invert (even quantum-computable) one-way functions and solve efficiently verifiable one-way puzzles defined relative to O. Our result therefore provides classical-oracle evidence that PRUs do not imply quantum-computable one-way functions, in the form of a black-box separation. We substantially strengthen the classical-oracle result of Kretschmer, Qian, and Tal (STOC 2025) by obtaining PRUs secure against these QMA-aided adversaries. Our construction also consists of a simple, efficient circuit that queries a random function, suggesting a route to concrete implementation via the random-oracle heuristic.

quant-pharXiv:2610.03711•Oct 5, 2026•0 citations

Quantum Pseudorandom Primitives Beyond Pseudorandom States

Chuhan Lu

Quantum pseudorandomness is an emerging research area. Ji, Liu, and Song defined pseudorandom states (PRSs) and pseudorandom unitaries (PRUs) as quantum analogs of pseudorandom generators and pseudorandom functions. A unitary oracle separation result between one-way functions and PRSs/PRUs, established by Kretschmer, suggests that certain quantum primitives may remain secure even if classical cryptography is compromised. This insight has spurred extensive work on quantum pseudorandomness and its applications in quantum cryptography. Many constructions of PRSs have been established under standard assumptions, yet building a secure PRU was a long-standing open problem. This dissertation aims to narrow the gap between PRSs and PRUs and presents results that go beyond PRSs. We introduce Pseudorandom State Scramblers (PRSSs), a new primitive that lies between PRSs and PRUs. A PRSS maps any pure state to a pseudorandom state, a property shared with PRUs but not with PRSs. We present a construction of PRSSs inspired by the well-known Kac’s walk, and in particular, we develop a parallel variant that significantly accelerates the mixing time, enabling an efficient construction. PRSSs support cryptographic tasks not known to be achievable from PRSs alone, including a quantum encryption scheme and a succinct quantum state commitment. Additionally, when suitable classical randomness is provided, our construction exhibits a special dispersing property not known to be satisfied by any existing construction of quantum pseudorandom primitives. Our subsequent work shows that, without asymptotically increasing the number of steps, our construction based on the parallel Kac’s walk yields PRUs with standard or even strong security. The proof builds on a recently developed technique for establishing adaptive security, known as the path-recording method. This result provides an alternative construction of PRUs and further showcases the power of this proof technique. In addition, this dissertation includes two side projects. The first revisits the Hidden Subgroup Problem over ℤn, providing a simplified analysis of a known quantum algorithm using elementary lattice tools. The second establishes a quantum analogue of a classical impossibility result for statistical non-interactive zero-knowledge arguments, showing limitations of black-box reductions under classical-query quantum adversaries.

•Aug 26, 2025•0 citations

On Scalable Pseudorandom Unitaries and the Unitary Synthesis Problem

Zvika Brakerski, Henry Yuen

We consider the task of constructing pseudorandom unitaries (PRUs) with scalable security, i.e. families in which the security parameter may vary independently of the dimension (or input bit-length). It is not known whether scalable PRUs can be constructed. In this work we show that if scalable PRUs can be constructed via the prevailing paradigm for analyzing PRUs, then there would be a positive solution to the Aaronson-Kuperberg unitary synthesis problem, a longstanding question in quantum complexity theory about whether implementing arbitrary unitaries can be efficiently reduced to computing a Boolean function. Specifically, we formalize the notion of ROM-PRUs, which are statistically secure PRUs in the random oracle model (ROM). All prior known constructions of cryptographically secure PRUs are based on a ROM-PRU construction. We prove novel connections between ROM-PRUs, approximate unitary designs, epsilon-nets over the unitary group, and the unitary synthesis problem. In particular, we prove that any unitary synthesis algorithm (and thus any ROM-PRU) must use a classical oracle with input length (2 - o(1)) log d bits, where d is the dimension of the unitary to be implemented. This bound rules out all existing candidates for scalable PRUs in the literature. Together, these connections indicate that ROM-PRUs provide a fruitful idealized model for studying pseudorandom unitaries.

quant-pharXiv:2605.09957•May 12, 2026•0 citations
Pseudorandomness is increasingly recognized as a key property of ensembles in quantum information theory, statistical mechanics, and quantum many-body physics. Yet it appears in two conceptually different forms: statistical pseudorandomness, embodied by unitary designs, and computational pseudorandomness captured by pseudorandom unitaries (PRUs). The relationship between these two forms of pseudorandomness remains surprisingly poorly understood. Existing PRU constructions reveal this interplay where a statistically randomizing ingredient, a unitary design, is combined with classical cryptographic primitives to produce computational pseudorandomness. We show that statistical pseudorandomness is not necessary for computationally pseudorandom unitaries. We do this by replacing the unitary 222-design layer in the existing constructions with ensembles that are not even state 111-designs, yet are sufficiently {\em distinct}, a property we identify to be necessary for any PRU. This yields new non-adaptively secure PRU ensembles whose computational pseudorandomness is obtained without an underlying statistically pseudorandom quantum ensemble, such as a 222-design. We characterize distinctness via an entangled analogue of anticoncentration and use it to show that distinctness already captures constraints on coherence and imaginarity of PRUs, while identifying broad classes of inputs for which the latter obstruction disappears, enabling real-valued PRUs even for certain (maximally) entangled states. As an application, we use lack of distinctness to constrain the conjectured pseudorandomness of the random phase-Hadamard ensemble to form a PRU.
Pseudorandom unitaries (PRUs) are ensembles of efficiently implementable unitary operators that cannot be distinguished from Haar random unitaries by any quantum polynomial-time algorithm with query access to the unitary. We present a simple PRU construction that is a concatenation of a random Clifford unitary, a pseudorandom binary phase operator, and a pseudorandom permutation operator. We prove that this PRU construction is secure against non-adaptive distinguishers assuming the existence of quantum-secure one-way functions. This means that no efficient quantum query algorithm that is allowed a single application of U⊗poly(n)U^{\otimes \mathrm{poly}(n)}U⊗poly(n) can distinguish whether an nnn-qubit unitary UUU was drawn from the Haar measure or our PRU ensemble. We conjecture that our PRU construction remains secure against adaptive distinguishers, i.e. secure against distinguishers that can query the unitary polynomially many times in sequence, not just in parallel.
Quantum computation gives rise to new pseudorandom primitives for states and unitaries, including pseudorandom state generators (PRSGs), pseudorandom function-like state generators (PRFSGs), and pseudorandom unitaries (PRUs). In this paper, we show a full unitary oracle separation between PRFSGs and PRUs. The separation holds between the strongest state notion and the weakest unitary notion: even adaptively secure, quantum-accessible PRFSGs do not imply non-adaptively secure, forward-only PRUs, even when their implementations are allowed to be non-unitary and use an arbitrary number of ancillary qubits. This reveals a fundamental distinction between pseudorandomness for quantum states and for quantum unitaries. Our main technical idea is to view a candidate PRU construction with access to state generation oracles as a map from the underlying oracle states to implemented unitaries, and to study the derivatives of this map. These derivatives are inherently low rank, and we exploit this low-rank structure to distinguish the resulting unitaries from truly random ones. We believe this differential perspective may be useful for studying other structural questions about quantum states and unitaries.
Pseudorandom quantum states (PRSs) and pseudorandom unitaries (PRUs) possess the dual nature of being efficiently constructible while appearing completely random to any efficient quantum algorithm. In this study, we establish fundamental bounds on pseudorandomness. We show that PRSs and PRUs exist only when the probability that an error occurs is negligible, ruling out their generation on noisy intermediate-scale and early fault-tolerant quantum computers. Further, we show that PRUs need imaginarity while PRS do not have this restriction. This implies that quantum randomness requires in general a complex-valued formalism of quantum mechanics, while for random quantum states real numbers suffice. Additionally, we derive lower bounds on the coherence of PRSs and PRUs, ruling out the existence of sparse PRUs and PRSs. We also show that the notions of PRS, PRUs and pseudorandom scramblers (PRSSs) are distinct in terms of resource requirements. We introduce the concept of pseudoresources, where states which contain a low amount of a given resource masquerade as high-resource states. We define pseudocoherence, pseudopurity and pseudoimaginarity, and identify three distinct types of pseudoresources in terms of their masquerading capabilities. Our work also establishes rigorous bounds on the efficiency of property testing, demonstrating the exponential complexity in distinguishing real quantum states from imaginary ones, in contrast to the efficient measurability of unitary imaginarity. Further, we show an exponential advantage in imaginarity testing when having access to the complex conjugate of the state. Lastly, we show that the transformation from a complex to a real model of quantum computation is inefficient, in contrast to the reverse process, which is efficient. Our results establish fundamental limits on property testing and provide valuable insights into quantum pseudorandomness.
We provide the first evidence relative to a classical oracle that pseudorandom unitaries (PRUs) can exist without quantum-computable one-way functions. To obtain this result, we first prove that five independent random diagonal phase layers interleaved with Hadamard transforms U=F5HF4HF3HF2HF1 U=F_5HF_4HF_3HF_2HF_1 U=F5​HF4​HF3​HF2​HF1​ form a strong PRU with security under adaptive, controlled access to the unitary, its inverse, transpose, and complex conjugate. Our main result is that, when the phase layers are implemented using a classical random oracle O, the construction remains secure against uniform BQP adversaries with coherent access to suitable Boolean completions of classical-input $QMA^{PH}^{O}}$ decision problems. Such an adversary can invert (even quantum-computable) one-way functions and solve efficiently verifiable one-way puzzles defined relative to O. Our result therefore provides classical-oracle evidence that PRUs do not imply quantum-computable one-way functions, in the form of a black-box separation. We substantially strengthen the classical-oracle result of Kretschmer, Qian, and Tal (STOC 2025) by obtaining PRUs secure against these QMA-aided adversaries. Our construction also consists of a simple, efficient circuit that queries a random function, suggesting a route to concrete implementation via the random-oracle heuristic.
Quantum pseudorandomness is an emerging research area. Ji, Liu, and Song defined pseudorandom states (PRSs) and pseudorandom unitaries (PRUs) as quantum analogs of pseudorandom generators and pseudorandom functions. A unitary oracle separation result between one-way functions and PRSs/PRUs, established by Kretschmer, suggests that certain quantum primitives may remain secure even if classical cryptography is compromised. This insight has spurred extensive work on quantum pseudorandomness and its applications in quantum cryptography. Many constructions of PRSs have been established under standard assumptions, yet building a secure PRU was a long-standing open problem. This dissertation aims to narrow the gap between PRSs and PRUs and presents results that go beyond PRSs. We introduce Pseudorandom State Scramblers (PRSSs), a new primitive that lies between PRSs and PRUs. A PRSS maps any pure state to a pseudorandom state, a property shared with PRUs but not with PRSs. We present a construction of PRSSs inspired by the well-known Kac’s walk, and in particular, we develop a parallel variant that significantly accelerates the mixing time, enabling an efficient construction. PRSSs support cryptographic tasks not known to be achievable from PRSs alone, including a quantum encryption scheme and a succinct quantum state commitment. Additionally, when suitable classical randomness is provided, our construction exhibits a special dispersing property not known to be satisfied by any existing construction of quantum pseudorandom primitives. Our subsequent work shows that, without asymptotically increasing the number of steps, our construction based on the parallel Kac’s walk yields PRUs with standard or even strong security. The proof builds on a recently developed technique for establishing adaptive security, known as the path-recording method. This result provides an alternative construction of PRUs and further showcases the power of this proof technique. In addition, this dissertation includes two side projects. The first revisits the Hidden Subgroup Problem over ℤn, providing a simplified analysis of a known quantum algorithm using elementary lattice tools. The second establishes a quantum analogue of a classical impossibility result for statistical non-interactive zero-knowledge arguments, showing limitations of black-box reductions under classical-query quantum adversaries.
We consider the task of constructing pseudorandom unitaries (PRUs) with scalable security, i.e. families in which the security parameter may vary independently of the dimension (or input bit-length). It is not known whether scalable PRUs can be constructed. In this work we show that if scalable PRUs can be constructed via the prevailing paradigm for analyzing PRUs, then there would be a positive solution to the Aaronson-Kuperberg unitary synthesis problem, a longstanding question in quantum complexity theory about whether implementing arbitrary unitaries can be efficiently reduced to computing a Boolean function. Specifically, we formalize the notion of ROM-PRUs, which are statistically secure PRUs in the random oracle model (ROM). All prior known constructions of cryptographically secure PRUs are based on a ROM-PRU construction. We prove novel connections between ROM-PRUs, approximate unitary designs, epsilon-nets over the unitary group, and the unitary synthesis problem. In particular, we prove that any unitary synthesis algorithm (and thus any ROM-PRU) must use a classical oracle with input length (2 - o(1)) log d bits, where d is the dimension of the unitary to be implemented. This bound rules out all existing candidates for scalable PRUs in the literature. Together, these connections indicate that ROM-PRUs provide a fruitful idealized model for studying pseudorandom unitaries.