We construct a constant-degree and constant-gap quantum expander on $n$ qubits where each unitary can be implemented by a depth-$1$ and 1D circuit of Pauli or CNOT gates. We provide two applications of this expander. First, we use it to construct a family of frustration-free 1D Hamiltonians whose ground states obey the entanglement-gap relation $S = Θ(Δ^{-1/2})$; this is believed to be optimal, but achieving it had been open. Second, we use it to provide a streaming protocol that tests for closeness to a class of 1D volume-law entangled states.
Moreover, we extend our quantum expander to a constant-degree and constant-gap expander on the unitary group where each unitary is a single $T$ gate, a single $T^{\dagger}$ gate, or a depth-$1$ Clifford circuit. This implies that a random sequence of unitaries from the expander yields a gapped walk on a dense subgroup of the unitary group. This improves upon previous work by Bourgain and Gamburd which did not control the dependence of the gap on the dimension.
We construct a constant-degree and constant-gap quantum expander on n qubits where each unitary can be implemented by a depth-1 and 1D circuit of Pauli or CNOT gates. We provide two applications of this expander. First, we use it to construct a family of frustration-free 1D Hamiltonians whose ground states obey the entanglement-gap relation S=Θ(Δ−1/2); this is believed to be optimal, but achieving it had been open. Second, we use it to provide a streaming protocol that tests for closeness to a class of 1D volume-law entangled states.
Moreover, we extend our quantum expander to a constant-degree and constant-gap expander on the unitary group where each unitary is a single T gate, a single T† gate, or a depth-1 Clifford circuit. This implies that a random sequence of unitaries from the expander yields a gapped walk on a dense subgroup of the unitary group. This improves upon previous work by Bourgain and Gamburd which did not control the dependence of the gap on the dimension.
We construct n-qubit approximate unitary k-designs in 1D systems, achieving circuit depth O(log(n/ε)+klogk) with relative error ε and requiring O(nklogk) magic gates. This matches existing lower bounds Ω(log(n/ε)+k) for circuit depth, and Ω(nk) for the required number of T gates, up to a logk factor, achieving simultaneous near-optimality in all parameters. Our construction is based on a combination and refinement of two existing results. We reduce the required magic block size for breaking Clifford symmetries in the magic-augmented circuit construction of Zhang et al. from O(klogk) to O(logk). We also improve the breakthrough construction of Chen et al. to construct a generating set of 1D local constant-depth circuits for the unitary group with a constant spectral gap, making O(logk)-local random unitaries realizable in depth O(klogk). As a by-product, we provide a constant-size 1D-local generating set for the Clifford group, which we expect to be of independent interest. Combining the two results with the gluing lemma, we prove the final result.
Classical circuits with unbounded fan-in can compute any Boolean function in constant depth when their size is unrestricted. We ask whether removing the restrictions on circuit size and ancillary qubits also allows quantum circuits built from arbitrary single-qubit gates and generalised Toffoli gates to implement every unitary in constant depth.
We give exact constant-depth constructions for arbitrary permutations of computational basis states, diagonal unitaries and the preparation of arbitrary pure states. These connect quantum state preparation to reversible classical computation and the preparation of probability distributions. With fanout in the gate set, they use exponentially many gates and ancillary qubits and return all ancillary qubits to zero. Replacing fanout by an exact circuit over the original gate set preserves constant depth, although the size bounds can become doubly exponential.
The implementation of arbitrary unitaries in constant depth remains open. We give equivalent formulations in terms of copying the vectors of a specified orthonormal basis, extracting their labels and implementing restricted families of unitaries. We also reduce arbitrary unitary implementation to that of traceless unitary involutions using one additional clean qubit. With adaptive measurements, gate teleportation gives depth proportional to the level of a gate in the Clifford hierarchy.
Towards arbitrary unitary implementation in constant depth, we use port-based teleportation: for input dimension d and M≥d2−1 ports, we construct a unitary circuit of depth O(d), independent of M and including resource preparation and port selection, with entanglement fidelity at least (1−(d2−1)/(2M))2. Thus, at fixed d, the approximation can be made arbitrarily accurate without increasing depth. Whether the dependence on d can also be removed remains open.
We prove constant lower bounds for the spectral gap of the following random walks on unitary groups SU(2n) on n qubits. (i) Random Pauli Rotation: choose an n-qubit Pauli operator P and an angle θ∈[0,2π), both uniformly at random, and apply eiθP. (ii) Brickwork Random Unitary Circuit: choose n−1 unitaries Ui uniformly at random from SU(4) independently, and apply U2j−1 on two qubits 2j−1,2j and then U2j on two qubits 2j,2j+1. Importantly, the spectral gap lower bounds are independent of n and apply for all finite dimensional unitary representations of SU(2n) uniformly, including those that appear in unitary t-designs. We also prove analogous constant-gap results for orthogonal and Clifford groups; the latter is indispensable for our result on the Brickwork Random Unitary Circuit.
Constructing ensembles of circuits which efficiently approximate the Haar measure over various groups is a long-standing and fundamental problem in quantum information theory. Recently it was shown that one can obtain approximate designs over the unitary group with depths scaling logarithmically in the number of qubits, but that no sublinear-depth approximate designs exist over the orthogonal group. Here we derive, for any group G possessing an invariant state G⊗k∣Ψ⟩=∣Ψ⟩, a lower bound on the diamond distance between the k\textsuperscript{th} moment operator of any ensemble of elements of G, and that of the Haar measure over G. We then use this bound to prove that for many groups of interest, no subset of G consisting of sublinear-depth one-dimensional circuits with local gates can form an approximate k-design over G. More generally, on a D-dimensional lattice, our results imply that such group designs require depths scaling at least as n1/D. Moreover, for most of the groups we consider we find that such ensembles can, with high probability, be distinguished from k-designs by a single shot of a constant-depth measurement. Among other examples, we show that there is a constant separation between (a) the maximum depth and gate count for which no circuit can approximate even the second moment of random matchgate circuits, and (b) the depth and gate count required to implement the matchgate Haar distribution exactly. We furthermore rule out the existence of sublinear-depth 8-designs over the Clifford group. Finally, we relax the assumption of working with local gates, and prove the impossibility of obtaining approximate designs over G using any circuit comprised of a sublinear number of gates generated by Pauli strings.
It is well-known that every n-qubit unitary can be implemented by a 2O(n)-depth quantum circuit using single- and two-qubit gates. It has been open whether exponential depth is *necessary* for general unitaries, even when allowing an unlimited number of ancilla qubits. Here we show, perhaps surprisingly, that all unitaries can be implemented exactly by a circuit of one- and two-qubit gates of depth poly(n) with 2O(n) ancilla qubits. In other words, every n-qubit unitary can be parallelized to polynomial depth. In fact, our depth bound is *linear* in n, which is the best possible, and an exponential improvement on the previous best bound of 2n/2 due to Rosenthal [TQC 2022, Quantum 2026]. Moreover, if we allow unbounded fan-out gates, these circuits can be further reduced to *constant* depth. Our construction takes advantage of a novel relationship connecting the unitary synthesis problem of Aaronson and Kuperberg to locally-decodable codes and private information retrieval from complexity theory and cryptography, and has a natural interpretation in bosonic quantum computation.
We seek to develop better upper bound guarantees on the depth of quantum CZ gate, CNOT gate, and Clifford circuits than those reported previously. We focus on the number of qubits$n\,{\leq }\,1,345,000[1],whichrepresentsthemostpracticalusecase.Ourupperboundonthedepthof\textsc {CZ}circuitsis\lfloor n/2 + 0.4993{\cdot }\log ^{2}(n) + 3.0191{\cdot }\log (n) - 10.9139\rfloor,improvingbestknowndepthbyafactorofroughly2.Weextendtheconstructionsusedtoprovethisupperboundtoobtaindepthupperboundof\lfloor n + 1.9496{\cdot }\log ^{2}(n) + 3.5075{\cdot }\log (n) - 23.4269 \rfloor$for CNOT gate circuits, offering an improvement by a factor of roughly4/3over state of the art, and depth upper bound of⌊2n+2.9487⋅log2(n)+8.4909⋅log(n)−44.4798⌋for Clifford circuits, offering an improvement by a factor of roughly5/3.