Depth-Optimal Quantum Compilation

Two foundational robustness results underlie the standard model of quantum computation. The Solovay–Kitaev theorem established that arbitrary quantum gates can be efficiently approximated using a fixed finite universal gate set, while results of Bernstein-Vazirani, Shi, and Aharonov showed that universal quantum computation can be realized using only real gates. However, these results do not necessarily preserve circuit depth, leaving open whether the same robustness extends to shallow quantum computation. In this work, I establish depth-preserving analogues of both robustness principles, leading to depth-optimal gate synthesis procedures and substantial simplifications of the shallow quantum circuit hierarchy.

In this talk, I will focus primarily on the main technical ingredient underlying the gate synthesis results: a simple, fully unitary construction based on block-encoding and oblivious amplitude amplification. This construction achieves depth O(log log(1/ε)) for ε-approximate synthesis of arbitrary single-qubit gates with only Hadamard, T, and CNOT gates. I show that this depth is optimal for any fixed finite bounded-width gate set, but that allowing logarithmic-width generalized Toffoli and Fan-Out gates reduces the depth to constant. Leveraging techniques from shallow quantum circuit complexity, I further show how Fan-Out can be eliminated altogether, yielding constant-depth synthesis with only Hadamard, T, and generalized Toffoli gates. I will conclude by discussing the broader implications for shallow quantum circuit complexity, including how arbitrary single-qubit rotations and complex amplitudes can be eliminated from bounded-error decision computation, yielding a substantially simplified circuit hierarchy and revealing a connection to restricted forms of Forrelation.

The full paper can be found at: https://arxiv.org/abs/2609.34659.