In quantum information theory, perfectly random states and operations—known as Haar-random objects—are the ultimate resource for scrambling information, encrypting data, and simulating complex physical systems. However, creating a truly Haar-random state or unitary matrix on $n$ qubits requires an exponential number of quantum gates. This physical impossibility creates a fundamental bottleneck for quantum protocols.
To bypass this limitation, researchers have developed the theory of quantum pseudorandomness. The core insight is that we do not need perfect mathematical randomness; we only need objects that are computationally indistinguishable from random ones to any observer with polynomial time and resources.
The Baseline: Pseudorandom Quantum States
To understand why quantum pseudorandomness works, we can look at how a classical computer generates random-looking numbers. A classical pseudorandom function (PRF) takes a secret key and an input, producing an output that looks like unpredictable noise.
In Pseudorandom Quantum States, Fang Song et al. extended this logic to the quantum domain by constructing Pseudorandom States (PRS). Imagine initializing a quantum register in a uniform superposition of all possible computational basis states:
$$\frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} |x\rangle$$
If we apply a classical quantum-secure PRF to compute a deterministic but random-looking phase shift for each basis state, the state becomes:
$$\frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} (-1)^{f_k(x)} |x\rangle$$
By following this phase-scrambling step with a Quantum Fourier Transform (QFT), the amplitudes are spread out globally. To a polynomial-time quantum observer, the resulting state is statistically indistinguishable from a state drawn uniformly at random from the entire Hilbert space, even though it was generated using minimal, polynomial-sized resources.
A remarkable extension of this idea is quantum pseudoentanglement, introduced by Scott Aaronson et al. in Quantum Pseudoentanglement. True Haar-random states are almost maximally entangled across any geometric split. The authors demonstrated that by carefully selecting a subset of basis states and applying pseudorandom phases, one can construct states that possess very low physical entanglement entropy (e.g., logarithmic in the number of qubits) but computationally appear to have maximal entanglement to any efficient quantum algorithm.
Scaling Up to Pseudorandom Unitaries
While a pseudorandom state hides its structure as a static vector, a Pseudorandom Unitary (PRU) must act as a black-box scrambler that mimics a Haar-random matrix for any arbitrary input state. This is a significantly harder problem because an adversary can choose the inputs adaptively to try and expose the underlying circuit structure.
The theoretical existence of PRUs was an open question until Fermi Ma resolved it in How to Construct Random Unitaries. The primary obstacle to proving that PRUs exist was a proof-theoretic one: in classical cryptography, we analyze security by imagining a "lazy evaluation" oracle that decides its random outputs on the fly. In the quantum world, an adversary can query an oracle in a superposition of inputs, meaning the oracle must evaluate all paths simultaneously.
To overcome this, Fermi Ma introduced the path-recording oracle. Instead of trying to materialize a massive, random unitary matrix, the path-recording oracle dynamically tracks the history of the computational paths taken by the quantum superposition. This mechanism allowed the author to prove that efficient quantum circuits driven by classical PRFs can successfully simulate Haar-random unitaries with an exponentially small trace distance error.
[Input State] ---> [ Ancilla Expansion ] ---> [ Phase Shift & Permutation ] ---> [Pseudorandom Output]
^ ^
| |
(Driven by Classical PRF) (Driven by Classical PRP)
As shown in Pseudorandom Isometries by Prabhanjan Vijendra Ananth et al., a practical way to build these operators is to expand the input state space with ancilla qubits, apply a sequence of phase shifts driven by classical PRFs, and execute permutations driven by pseudorandom permutations (PRPs). This architecture forces the quantum state to wander through an exponentially large space, mimicking the statistical properties of a Haar-random isometry.
Defending Against Inverse Queries
The definition of a PRU becomes even more demanding when the adversary is allowed to query both the unitary $U$ and its inverse $U^\dagger$. This is known as a strong PRU. Without careful design, an attacker can use backward queries to undo the entanglement or scrambling created by the forward process, exposing the non-random nature of the circuit.
In Pseudorandom Unitaries in the Haar Random Oracle Model, Prabhanjan Vijendra Ananth et al. proved a strict architectural threshold for achieving strong pseudorandomness. A single query to a random quantum oracle is fundamentally vulnerable to cancellation attacks. However, the authors proved that two sequential queries are sufficient to achieve strong pseudorandomness. By interleaving queries to a Haar-random oracle with secret-key-controlled bit-flip operations, the forward and backward computational paths become decoupled from the perspective of a polynomial-time adversary, preventing cancellation attacks.
Unconditional Pseudorandomness in Restricted Models
Most constructions of quantum pseudorandomness rely on unproven classical complexity assumptions, such as the existence of quantum-secure one-way functions. However, if we restrict the capabilities of the observer, we can achieve unconditional pseudorandomness without any underlying assumptions.
In Unconditional Pseudorandomness Against Shallow Quantum Circuits, Soumik Ghosh et al. shifted the focus from time-bounded adversaries to depth-bounded adversaries (shallow, geometrically local quantum circuits). Instead of relying on cryptographic PRFs, the authors utilized unitary $k-designs$—ensembles of operators that perfectly match the first $k$ statistical moments of a Haar-random distribution.
By leveraging unitary 2-designs, the authors proved that shallow circuits cannot gather enough global correlation data to distinguish the design from a truly Haar-random unitary. The local nature of the shallow circuit prevents it from reading the global algebraic structures embedded in the state, making the pseudorandomness unconditional.
Why It Matters: Complexity and Hardware
The ability to generate pseudorandom states and unitaries efficiently has deep implications across quantum computing:
- Circuit Lower Bounds: In Quantum State and Unitary Learning Implies Circuit Lower Bounds, Nai-Hui Chia et al. demonstrated a fundamental duality: if an algorithm can efficiently learn or de-anonymize a PRS or PRU, that algorithm can be used to prove that certain powerful quantum circuit classes cannot efficiently synthesize those states. This connects pseudorandomness directly to the quest for proving quantum circuit lower bounds.
- Quantum Hardware Security: In On the connection between quantum pseudorandomness and quantum hardware assumptions, Mina Doosti et al. showed that PRSs can replace expensive Haar-random states in constructing unforgeable Quantum Physical Unclonable Functions (qPUFs). This bridges the gap between abstract complexity theory and physical hardware validation.
Ultimately, quantum pseudorandomness works because quantum indistinguishability is a leverage game. By hiding simple classical keys inside global quantum superpositions and phases, efficient circuits can construct states and operators that look indistinguishable from the chaotic, infinitely complex randomness of nature.
Key Foundational Work
Chaos and complexity by design (2017) — contributed 1 concept elements to this direction.
On learning finite-state quantum sources (2012) — contributed 1 concept elements to this direction.