Random unitaries are a central object of study in quantum information, with applications to quantum computation, quantum many-body physics, and quantum cryptography. Recent work has constructed unitary designs and pseudorandom unitaries (PRUs) using
Θ(loglogn)-depth unitary circuits with two-qubit gates. In this work, we show that unitary designs and PRUs can be efficiently constructed in several well-studied models of
constant-time quantum computation (i.e., the time complexity on the quantum computer is independent of the system size). These models are constant-depth circuits augmented with certain nonlocal operations, such as (a) many-qubit TOFFOLI gates, (b) many-qubit FANOUT gates, or (c) mid-circuit measurements with classical feedforward control. Recent advances in quantum computing hardware suggest experimental feasibility of these models in the near future. Our results demonstrate that unitary designs and PRUs can be constructed in much weaker circuit models than previously thought. Furthermore, our construction of PRUs in constant-depth with many-qubit TOFFOLI gates shows that, under cryptographic assumptions, there is no polynomial-time learning algorithm for the circuit class
QAC0. Finally, our results suggest a new approach towards proving that PARITY is not computable in
QAC0, a long-standing question in quantum complexity theory.
Unitary designs provide efficient substitutes for Haar-random unitaries in quantum information processing, randomized measurements, and many-body quantum dynamics. We propose a protocol based on time evolutions of a single chaotic Hamiltonian interleaved with unitary perturbations to generate unitary designs. We derive the frame potential of the resulting ensemble in terms of those of the intermediate ensemble. The intermediate ensemble need not itself be Haar random or exhibit Haar-level frame potentials, provided that its trace moments and frame-potential growth are sufficiently suppressed. The nontrivial Pauli set and the Clifford ensemble are simple examples, whereas ensembles whose cardinality does not grow with the Hilbert-space dimension generally fail. We further establish a frame-potential correspondence between multi-Hamiltonian temporal protocols and one-Hamiltonian protocols interleaved with repeated fixed trace-suppressed perturbations, showing that two perturbations suffice to recover Haar-level frame potentials. For local Hamiltonians, we derive a lower bound on the space--depth control resource, while more generally we establish a universal finite-window bound that constrains the required temporal sampling range. Together, these results identify complementary spatial and temporal resource requirements for perturbation-assisted randomness generation.
The existence of pseudorandom unitaries (PRUs) -- efficient quantum circuits that are computationally indistinguishable from Haar-random unitaries -- has been a central open question, with significant implications for cryptography, complexity theory, and fundamental physics. In this work, we close this question by proving that PRUs exist, assuming that any quantum-secure one-way function exists. We establish this result for both (1) the standard notion of PRUs, which are secure against any efficient adversary that makes queries to the unitary
U, and (2) a stronger notion of PRUs, which are secure even against adversaries that can query both the unitary
U and its inverse
U†. In the process, we prove that any algorithm that makes queries to a Haar-random unitary can be efficiently simulated on a quantum computer, up to inverse-exponential trace distance.
Can simple processes appear highly complex? Gowers (Comb. Prob. Comp. '96) conjectured that repeatedly composing local random reversible operations can yield global permutations that are indistinguishable from random. In this work, we study the unitary quantum analog of this question, in an attempt to make new progress on this longstanding conjecture.
Our first result shows that statistical moment matching in the form of unitary designs does not generically lead to pseudorandomness---even for the simplest quantum processes: for every fixed
t, we give an efficiently samplable family
{νn}n of distributions on one- and two-qubit gates such that, after
T=Ot(n2log2n) independent steps, the resulting
n-qubit ensemble is an approximate unitary
t-design with negligible error
exp(−Ω(log2n)), yet an efficient quantum algorithm distinguishes it from random using only
Ot(log2n) queries. This refutes the unitary analog of the Hoory--Magen--Myers--Rackoff conjecture (ICALP '04) for permutations.
Our second result is a stronger separation between unitary designs and pseudorandom unitaries at polynomially bounded moments; our counterexample, however, requires highly structured ensembles, in contrast with the simple local walks from before. This suggests caution when using unitary designs to model information scrambling in black-hole physics, as even maximally scrambled systems can exhibit structure which is accessible to efficient experiments. Motivated by these findings, we then propose new conjectures for how pseudorandomness can plausibly emerge within simple quantum processes, such as random quantum circuits.
The unitary design formation in random circuits has attracted considerable attention due to its wide range of practical applications and relevance to fundamental physics. While the formation rates in Haar random circuits have been extensively studied in previous works, it remains an open question how these rates are affected by the choice of local randomizers. In this Letter, we prove that the circuit depths required for general non-Haar random circuits to form unitary designs are upper bounded by those for the corresponding Haar random circuits, up to a constant factor independent of the system size. This result is derived in a broad range of circuit structures, including one- and higher-dimensional lattices, geometrically nonlocal configurations, and even extremely shallow circuits with patchwork architectures. We provide specific applications of these results in randomized benchmarking and random circuit sampling, and also discuss their implications for quantum many-body physics. Our results lays the foundation for flexible and robust randomness generation in real-world experiments, and offers new insights into chaotic dynamics in complex quantum systems.
Uniformly random unitaries, i.e. unitaries drawn from the Haar measure, have many useful properties, but cannot be implemented efficiently. This has motivated a long line of research into random unitaries that “look” sufficiently Haar random while also being efficient to implement. Two different notions of derandomisation have emerged:
t-designs are random unitaries that information-theoretically reproduce the first
tmoments of the Haar measure, and pseudorandom unitaries (PRUs) are random unitaries that are computationally indistinguishable from Haar random. In this work, we take a unified approach to constructing
t-designs and PRUs. For this, we introduce and analyse the “
PFCensemble”, the product of a random computational basis permutation
P, a random binary phase operator
F, and a random Clifford unitary
C. We show that this ensemble reproduces exponentially high moments of the Haar measure. We can then derandomise the
PFCensemble to show the following: •Linear-depth
t-designs. We give the first construction of a (diamond-error) approximate
t-design with circuit depth linear in
t. This follows from the
PFCensemble by replacing the random phase and permutation operators with their
2t-wise independent counterparts. •Non-adaptive PRUs. We give the first construction of PRUs with non-adaptive security, i.e. we construct unitaries that are indistinguishable from Haar random to polynomial-time distinguishers that query the unitary in parallel on an arbitary state. This follows from the
PFCensemble by replacing the random phase and permutation operators with their pseudorandom counterparts. •Adaptive pseudorandom isometries. We show that if one considers isometries (rather than unitaries) from
nto
n+ω(logn)qubits, a small modification of our PRU construction achieves adaptive security, i.e. even a distinguisher that can query the isometry adaptively in sequence cannot distinguish it from Haar random isometries. This gives the first construction of adaptive pseudorandom isometries. Under an additional conjecture, this proof also extends to adaptive PRUs.