arXiv:2609.39092
Quantum circuit compilation with constant overhead
Chenyi Zhang, Xinyu Tan, Robin Kothari, David Gosset, Craig Gidney
Abstract
Compiling a continuous gate set to a discrete universal gate set generally incurs an overhead. A circuit composed of $G$ arbitrary one- and two-qubit gates can be $ε$-approximated by a sequence of gates from $\{H,T,\mathrm{CNOT}\}$ by replacing each original gate by a sequence of $O(\log(G/ε))$ elementary gates. We show that this overhead can be avoided using adaptivity for polynomial-sized circuits with inverse-polynomial target error, which is optimal.
AI Summary
Standard gate-by-gate compilation of a circuit with $G$ arbitrary one- and two-qubit gates into $\{H,T,\mathrm{CNOT}\}$ costs $O(G\log(G/\epsilon))$ gates. This paper asks whether compiling the circuit collectively can remove that multiplicative overhead. The main result is an adaptive implementation using $O(G)$ elementary gates in the worst case, with diamond-distance error $G^{-c}$ for any fixed $c$; the hidden constant depends on $c$. For circuits over the discrete set augmented by dyadic rotations $R(\pi/2^j)$, the bound improves to $O(G+\log(1/\epsilon))$ for arbitrary target error. A supporting result prepares an $n$-qubit phase-gradient state unitarily with error $2^{-n}$ using $O(n)$ gates. With Clifford gates free, a circuit containing $G$ arbitrary $Z$-rotations can achieve error $1/\sqrt G$ with at most $8G+o(G)$ $T$ gates. The compilation strategy combines state injection with catalytic phase-halving gadgets and an adaptive bank of rotation-resource states. Tail bounds allow a fixed runtime cutoff while controlling failure error. General rotations are discretized and decomposed using a large-base expansion; the simpler $1/\sqrt G$-error construction uses randomized rounding. Linear-cost phase-gradient preparation uses LCU, amplitude amplification, tailored encodings, and classical multiselection circuits. A counting argument rules out linear-cost compilation at superpolynomially small error for arbitrary gates. Full adaptivity remains necessary for the presented protocols; whether it can be avoided is open. The optimal phase-gradient construction requires complex coherent reversible circuits and is not presented as near-term practical.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.