Metraipolis › archive › dc_8550d2a15b8d

Depth-Optimal Quantum Compilation — arXiv:2609.34659

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.34659
License (as archived)
CC0-1.0
Archived
2026-10-08T00:43:24.104Z
SHA-256 of the archived text
0780bcbab7cd2b11179aaaa9b190a615bf4b8b4390b28d89d82177f3e5ecb798
Stable URL of this page
https://metraipolis.com/documento/dc_8550d2a15b8d

How to cite

Depth-Optimal Quantum Compilation — arXiv:2609.34659 — arXiv (en), https://arxiv.org/abs/2609.34659 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_8550d2a15b8d (Metraipolis archive dc_8550d2a15b8d, sha256 0780bcbab7cd2b11179aaaa9b190a615bf4b8b4390b28d89d82177f3e5ecb798)
BibTeX
@misc{dc8550d2a15b8d,
  title = {Depth-Optimal Quantum Compilation — arXiv:2609.34659},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.34659},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_8550d2a15b8d; sha256 0780bcbab7cd2b11179aaaa9b190a615bf4b8b4390b28d89d82177f3e5ecb798},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.34659. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We achieve the first constant-depth circuit for arbitrary single-qubit gate synthesis. Unlike prior approaches, the construction is fully unitary and requires no pre-supplied catalyst. For any constant $\delta>0$, it $\varepsilon$-approximates an arbitrary single-qubit gate using $O(\log^{1+\delta}(1/\varepsilon))$ clean ancillae, Hadamard and $T$ single-qubit gates, $O(\log(1/\varepsilon))$-width generalized Toffoli gates, and sublogarithmic-width Fan-Out gates. We further eliminate Fan-Out entirely, showing that Hadamard, $T$, and generalized Toffoli gates alone suffice for constant-depth synthesis. When restricted to the standard bounded-width gate model, our construction has depth $O(\log\log(1/\varepsilon))$, and we prove a matching $\Omega(\log\log(1/\varepsilon))$-depth lower bound. Overall, we establish that $\Theta(\log\log(1/\varepsilon))$-depth is unavoidable with only bounded-width gates, yet allowing even logarithmic-width multi-qubit gates suffices to achieve constant-depth synthesis. These results also reveal new structure in shallow quantum circuit complexity. We give a depth-preserving real simulation of bounded-error decision computation, showing that every depth-$d$ QAC circuit can be simulated in depth $O(d)$ using only Hadamard, $X$, and generalized Toffoli gates. Thus arbitrary single-qubit rotations and complex amplitudes do not increase the bounded-error decision power of QAC, even at constant depth. In particular, this reduces the long-standing conjecture Parity$\notin$QAC$^0$ to proving a Parity lower bound against circuits consisting only of Hadamard, $X$, and generalized Toffoli gates. More generally, this real normal form exposes a direct correspondence between the standard shallow-depth quantum circuit hierarchy and a hierarchy of Forrelation circuits with restricted oracle families.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-29 in cs.CC).
Categorie arXiv: Quantum Physics (quant-ph) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2609.34659 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T00:17:42.559Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).