Metraipolis › archive › dc_26549e89fad0
Ancilla-free randomized Toffoli gates and the T-count of Boolean oracles — arXiv:2610.38189
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.38189
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-01T02:48:01.793Z
- SHA-256 of the archived text
3e1262c6b3ba93153536157fddeb309fb3b6d3fce534c9c630f53dfb269f13e0- Stable URL of this page
https://metraipolis.com/documento/dc_26549e89fad0
How to cite
Ancilla-free randomized Toffoli gates and the T-count of Boolean oracles — arXiv:2610.38189 — arXiv (en), https://arxiv.org/abs/2610.38189 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_26549e89fad0 (Metraipolis archive dc_26549e89fad0, sha256 3e1262c6b3ba93153536157fddeb309fb3b6d3fce534c9c630f53dfb269f13e0)
BibTeX
@misc{dc26549e89fad0,
title = {Ancilla-free randomized Toffoli gates and the T-count of Boolean oracles — arXiv:2610.38189},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.38189},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_26549e89fad0; sha256 3e1262c6b3ba93153536157fddeb309fb3b6d3fce534c9c630f53dfb269f13e0},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.38189. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In fault-tolerant Clifford+T circuits, a Boolean oracle costs T gates and extra qubits, and on four or more qubits every exact Toffoli gate needs an extra qubit. Gosset, Kothari and Zhang showed that sampling a fresh random circuit for each call makes the T-count of the Toffoli gate independent of its size, but a direct implementation of their sampler uses about one extra qubit per bit of precision. We show that computing the sampled parities in place, on the gate's own controls, removes every extra qubit once the gate is large enough: each random circuit then uses about 8 T gates per bit of precision and borrows only the gate's own idle inputs. This is one T gate more per circuit than the best measurement-free variant that keeps one clean ancilla. The same holds for exclusive-ors of indicators of affine subspaces, such as equality tests and checks of linear equations. For randomized circuits that do not measure, this is within a factor of eight of optimal up to an additive constant, even with extra qubits, and when each random circuit computes a Boolean function exactly, closing the factor asymptotically is equivalent to determining the leading constant in the T-count of exact multi-controlled Toffoli gates. Finally, the oracle of the indicator of a random set of fixed density needs exponentially many T gates at constant error, while that of an affine subspace of the same density needs a constant number, and extra qubits reduce the exponential cost only quadratically. Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.CC, nuovi lavori del giorno). Categorie arXiv: Quantum Physics (quant-ph) ; Computational Complexity (cs.CC). Pagina del lavoro: https://arxiv.org/abs/2610.38189 — 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-11-01T02:18:28.505Z dalla pagina https://arxiv.org/list/cs.CC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).