Random Unitaries in Constant (Quantum) Time

Ben Foxman Natalie Parham Francisca Vasconcelos Henry Yuen · 2025

Read Random Unitaries in Constant (Quantum) Time by Ben Foxman Natalie Parham Francisca Vasconcelos Henry Yuen (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-2508-11487.txt.

Introduction

Ben Foxman, Natalie Parham, Francisca Vasconcelos, and Henry Yuen show that random unitaries can be built in constant quantum time in this 2025 paper. Random unitaries sit at the heart of quantum computing, many body physics, and cryptography. Recent constructions needed circuit depth that grows, slowly, with system size. These authors work in weaker models where the quantum run time does not grow at all. The models add special operations to shallow circuits, such as many qubit gates or mid circuit measurement with fast classical control.

In each model, they build both unitary designs and pseudorandom unitaries, two grades of randomness used in theory and security work. One result carries a complexity punch: with many qubit TOFFOLI gates, no fast classical learner can master this circuit class, under standard cryptographic assumptions. It also suggests a fresh route at a long open parity question.

Catalog record

CREATORBen Foxman Natalie Parham Francisca Vasconcelos Henry Yuen
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE93 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-11487

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Random Unitaries in Constant (Quantum) Time Ben Foxman Natalie Parham Francisca Vasconcelos Henry Yuen Abstract 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 Θ ⁡ ( log ⁡ log ⁡ n ) \Theta(\log\log n) -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 𝖰𝖠𝖢 0 {\mathsf{QAC}}^{0} . Finally, our results suggest a new approach towards proving that PARITY is not computable in 𝖰𝖠𝖢 0 {\mathsf{QAC}}^{0} , a long-standing question in quantum complexity theory. 1 Introduction Unitary designs and pseudorandom unitaries (PRUs) are efficiently implementable ensembles of unitaries that mimic Haar-random unitaries; t -designs are statistically indistinguishable from the Haar measure up to t ’th moments, and PRUs are computationally indistinguishable from Haar when queried by efficient quantum algorithms. Applications of unitary designs and pseudorandom unitaries are diverse, ranging from quantum compiling [ WE16 ] , benchmarking [ Kni+08 ] , quantum learning [ HCP23 ] , quantum supremacy experiments [ Aru+19 ] , and quantum cryptography [ Gun+23 ] . There is a long line of work focused on efficiently implementing unitary designs [ BHH16 , Haf22 , HM23 , Met+24 , LL24 , SHH25 ] and PRUs [ SHH25 , MH24 , Lu+25 ] . Particularly striking are the “gluing-type” results of LaRacuente and Leditzky [ LL24 ] and Schuster, Haferkamp, and Huang [ SHH25 ] . In these works, the authors show that several small, independent copies of t -designs or PRUs can be “glued” together, yielding random unitaries on larger numbers of qubits. This allows one to construct t -designs/PRUs in O(\log n) depth on nearest-neighbor circuit geometries, and O(\log\log n) depth in all-to-all circuits. Given that circuit depth corresponds to the time complexity of a computation, this results imply that (pseudo)random unitaries can be implemented in little time on a quantum computer. Schuster et al. [ SHH25 ] also show that the Gluing Lemma is optimal: unitary designs and PRUs provably require \Theta(\log\log n) depth in all-to-all architectures and \Theta(\log n) depth in nearest-neighbor architectures. Given this, it may appear that the story is closed on minimizing the time complexity of unitary designs and PRUs. However, this is only the limit when we consider unitary circuits composed of single- and two-qubit gates. In this paper we show that t -designs and PRUs can be implemented in constant time in several well-motivated models of quantum computation. We then describe several implications of our results, ranging from possible experimental implementations, quantum complexity theory, and limits on quantum learning. Models of constant-time computation. Constant-depth quantum circuits are a model of constant-time quantum computations (i.e., the time complexity on the quantum computer is independent of the system size). Constant-depth circuits with only local unitary gates are quite limited in power; they cannot prepare long-range entanglement (like in the GHZ state) or compute functions that depend on all input bits. However, there has been significant interest in understanding the power of constant-depth quantum circuits augmented with complex operations such as many-qubit gates or intermediate measurements with feedforward control. The addition of nonlocal operations appears to unlock significant computational advantages for constant-depth circuits. Some models include: 1. Short-time Hamiltonian evolutions. Such operations are natural in analog quantum simulators [ Per+21 ] , and are capable of entangling many qubits simultaneously [ Fen03 ] . 2. Constant-depth circuits with mid-circuit measurements (i.e., intermediate measurements, followed by classical postprocessing of measurement outcomes to control subsequent layers of gates). This model is important for quantum error-correction [ Sho95 ] , and has been shown to be capable of generating exotic quantum states with long-range entanglement [ TVV23 , Buh+24 ] . Here we treat classical computation as a free operation (i.e., costing no time), which is a reasonable assumption in many cases. 3. Constant-depth circuits with arbitrary single-qubit gates and many-qubit FANOUT gates (which maps \ket{s,x_{1},\dots,x_{k}} to \ket{s,s\oplus x_{1},\dots,s\oplus x_{k}} ). This gives rise to the so-called {\mathsf{QAC}}^{0}_{f} circuit class, which has been studied in quantum complexity theory as a quantum analogue of the classical circuit class {\mathsf{AC}}^{0} [ Moo99 ] . The addition of the FANOUT gate makes constant-depth circuits surprisingly powerful; for example, the PARITY function and even the quantum Fourier transform can be computed with {\mathsf{QAC}}^{0}_{f} circuits [ HS05 ] . 4. Circuits with constant T -depth , that is, arbitrary Clifford computation interleaved with a constant number of layers of T gates. Such circuits have been studied in the context of fault-tolerant quantum computation [ Fow12 ] , nonlocal quantum computation [ Spe16 ] , and quantum circuit lower bounds [ Par25 ] . This is a reasonable model of constant-time computation in the fault-tolerance setting, because the cost of performing logical T gates dominates that of Clifford operations. These models might appear very different from each other, but in fact some of them are closely related. For example, constant T -depth circuits, when given access to a catalytic resource state, can simulate {\mathsf{QAC}}^{0}_{f} [ Kim25 ] , which in turn is equivalent to constant-depth circuits with mid-circuit measurements where the classical processing consists of parity computations [ Buh+24 ] . The equivalence of these models greatly extends the flexibility of quantum algorithm design. For example, one could design an efficient quantum algorithm in the {\mathsf{QAC}}^{0}_{f} model (which may be conceptually easier to think about), and then immediately obtain an efficient implementation in the mid-circuit measurement model, which is experimentally realizable [ Cór+21 ] . We take this approach to show that unitary designs and pseudorandom unitaries can be implemented in constant (quantum 1 1 1 The parenthetical is meant to emphasize that the quantum part of the circuit has constant depth, and we treat the classical processing, which will be simple parity computations, as free. ) time. 1.1 Our Contributions First we show that unitary designs and PRUs can be implemented by polynomial-size {\mathsf{QAC}}^{0}_{f} circuits. Here, we consider two flavors of designs and PRUs, standard and strong . Standard means that the unitaries appear Haar-random to algorithms that can make (adaptive) queries to the forwards direction of the unitary, whereas strong means that the unitaries appear Haar-random even when the algorithm can make queries to the inverse unitary as well [ MH24 ] . This theorem circumvents the lower bounds of [ SHH25 ] which only apply to circuits with single- and two-qubit unitary gates. Theorem 1.1 (Random Unitaries in {\mathsf{QAC}}^{0}_{f} ) .

Read the complete text