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 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) (including central phases of the parent group) independently, and apply U2j−1 on two qubits 2j−1,2j and then U2j on two qubits 2j,2j+1. Importantly, the gap bounds are independent of n and apply for all finite dimensional unitary representations of SU(2n) uniformly.
Our results immediately imply that the Random Pauli Rotation and Brickwork Random Unitary Circuit converge to approximate unitary t-designs after O(nt) steps. As a consequence, we improve implications for the complexity growth of random unitary circuits as a function of the depth. The existing argument can be applied almost verbatim, but previously the depth had to be O(2cn) for some c<1. Our unconditional constant spectral gap removes this restriction.
We prove analogous constant-gap results for orthogonal and Clifford groups; the latter is indispensable for our result on the Brickwork Random Unitary Circuit. The former implies convergence to approximate orthogonal t-designs. In this case, the implied mixing time with respect to a constant additive and multiplicative error is optimal (up to an absolute constant factor) for t=2.
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 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.
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.
We consider the problem of subgroup testing for a quantum circuit C: given access to C, determine whether it implements a unitary that is a-close or b-far from a subgroup G of the unitary group. It encompasses the problem of exact testing, property testing and tolerant testing. In this work, we study these problems with the group G as the trivial subgroup (i.e. identity testing) or the Pauli or Clifford group and their q-ary extension, and a promise version of these problems where C is promised to be in some subgroup of the unitaries that contains G (e.g. identity testing for Clifford circuits). Our main result is an equivalence between Pauli testing, Clifford testing and Identity testing. We derive the equivalence between Clifford and Identity testing by showing a structural property of the Clifford unitaries. Namely, that their (normalized) trace lies in the discrete set {2−k/2:k∈N}∪{0}, regardless of the dimension. We also state and prove the analogous property for the q-ary Cliffords. This result allows us to analyze a very simple single-query identity test under the Clifford/Pauli promise. To prove the equivalence between Pauli and Identity testing, we analyze the conjugation action of a non-Pauli unitary on the Pauli group and show that its distance from the Pauli group affects the number of fixed points. We believe that these results are of interest, independent of their application to establish the equivalences. We use the equivalences to compare (and thus establish) computational hardness for the problems of Pauli and Clifford testing.