Rise of conditionally clean ancillae for efficient quantum circuit constructions

Tanuj Khattar; Craig Gidney

doi:10.22331/q-2025-05-21-1752

Rise of conditionally clean ancillae for efficient quantum circuit constructions

Tanuj Khattar and Craig Gidney

Google Quantum AI, Santa Barbara, California 93117, USA

Published:	2025-05-21, volume 9, page 1752
Editor:	John van de Wetering
Eprint:	arXiv:2407.17966v2
Doi:	https://doi.org/10.22331/q-2025-05-21-1752
Citation:	Quantum 9, 1752 (2025).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

We introduce conditionally clean ancilla qubits, a new quantum resource, recently explored by [17], that bridges the gap between traditional clean and dirty ancillae. Like dirty ancillae, they begin and end in an unknown state and can be borrowed from existing system qubits, avoiding the space overhead of explicit qubit allocation. Like clean ancillae, they can be treated as initialized in a known state within specific computations, thus avoiding the overhead of toggle detection required for dirty ancillae. We present new circuit constructions leveraging conditionally clean ancillae to achieve lower gate counts and depths, particularly with limited ancilla availability. Specifically, we provide constructions for:

(a) $n$-controlled NOT using $2n$ Toffolis and $O(\log{n})$ depth given 2 clean ancillae.
(b) $n$-qubit incrementer using $3n$ Toffolis given $\log_2^*{n}$ clean ancillae.
(c) $n$-qubit quantum-classical comparator using $3n$ Toffolis given $\log_2^*{n}$ clean ancillae.
(d) unary iteration over $[0,N)$ using $2.5N$ Toffolis given $\log_2^*{n}$ clean ancillae.
(e) unary iteration via skew tree over $[0, N)$ using $1.25N$ Toffolis given $n$ dirty ancillae.

We also introduce $\textit{laddered toggle detection}$, a technique to replace clean ancillae with dirty ancillae in all our constructions, incurring a 2x Toffoli gate overhead. Our results demonstrate that conditionally clean ancillae are a valuable tool for quantum circuit design, especially in the resource-constrained early fault-tolerant era.

► BibTeX data

@article{Khattar2025riseofconditionally,
  doi = {10.22331/q-2025-05-21-1752},
  url = {https://doi.org/10.22331/q-2025-05-21-1752},
  title = {Rise of conditionally clean ancillae for efficient quantum circuit constructions},
  author = {Khattar, Tanuj and Gidney, Craig},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1752},
  month = may,
  year = {2025}
}

► References

[1] Anjali A. Agrawal, Joshua Job, Tyler L. Wilson, S. N. Saadatmand, Mark J. Hodson, Josh Y. Mutus, Athena Caesura, Peter D. Johnson, Justin E. Elenewski, Kaitlyn J. Morrell, and Alexander F. Kemper, ``Quantifying fault tolerant simulation of strongly correlated systems using the Fermi-Hubbard model'' (2024).
https://doi.org/10.48550/ARXIV.2406.06511
https://arxiv.org/abs/2406.06511

[2] Ryan Babbush, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, and Hartmut Neven, ``Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity'' Physical Review X 8 (2018).
https://doi.org/10.1103/physrevx.8.041015

[3] Clémence Chevignard, Pierre-Alain Fouque, and André Schrottenloher, ``Reducing the Number of Qubits in Quantum Factoring'' Cryptology ePrint Archive, Paper 2024/222 (2024) https://eprint.iacr.org/2024/222.
https://eprint.iacr.org/2024/222

[4] Andrew M. Childs, Dmitri Maslov, Yunseong Nam, Neil J. Ross, and Yuan Su, ``Toward the first quantum simulation with quantum speedup'' Proceedings of the National Academy of Sciences 115, 9456–9461 (2018).
https://doi.org/10.1073/pnas.1801723115

[5] Baptiste Claudon, Julien Zylberman, César Feniou, Fabrice Debbasch, Alberto Peruzzo, and Jean-Philip Piquemal, ``Polylogarithmic-depth controlled-NOT gates without ancilla qubits'' Nature Communications 15 (2024).
https://doi.org/10.1038/s41467-024-50065-x

[6] Austin G. Fowler, Matteo Mariantoni, John M. Martinis, and Andrew N. Cleland, ``Surface codes: Towards practical large-scale quantum computation'' Physical Review A 86 (2012).
https://doi.org/10.1103/physreva.86.032324

[7] Craig Gidney ``Constructing Large Controlled Nots'' https://algassert.com (2015).
https://algassert.com/circuits/2015/06/05/Constructing-Large-Controlled-Nots.html

[8] Craig Gidney ``Constructing Large Increment Gates'' https://algassert.com (2015).
https://algassert.com/circuits/2015/06/12/Constructing-Large-Increment-Gates.html

[9] Craig Gidney ``Factoring with n+2 clean qubits and n-1 dirty qubits'' (2017).
https://doi.org/10.48550/ARXIV.1706.07884
https://arxiv.org/abs/1706.07884

[10] Craig Gidney ``Halving the cost of quantum addition'' Quantum 2, 74 (2018).
https://doi.org/10.22331/q-2018-06-18-74

[11] Matthew P. Harrigan, Tanuj Khattar, Charles Yuan, Anurudh Peduri, Noureldin Yosri, Fionn D. Malone, Ryan Babbush, and Nicholas C. Rubin, ``Expressing and Analyzing Quantum Algorithms with Qualtran'' (2024).
https://doi.org/10.48550/ARXIV.2409.04643
https://arxiv.org/abs/2409.04643

[12] Cody Jones ``Low-overhead constructions for the fault-tolerant Toffoli gate'' Physical Review A 87 (2013).
https://doi.org/10.1103/physreva.87.022328

[13] Isaac H. Kim, Ye-Hua Liu, Sam Pallister, William Pol, Sam Roberts, and Eunseok Lee, ``Fault-tolerant resource estimate for quantum chemical simulations: Case study on Li-ion battery electrolyte molecules'' Physical Review Research 4 (2022).
https://doi.org/10.1103/physrevresearch.4.023019

[14] Joonho Lee, Dominic W. Berry, Craig Gidney, William J. Huggins, Jarrod R. McClean, Nathan Wiebe, and Ryan Babbush, ``Even More Efficient Quantum Computations of Chemistry Through Tensor Hypercontraction'' PRX Quantum 2 (2021).
https://doi.org/10.1103/prxquantum.2.030305

[15] Daniel Litinski ``A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery'' Quantum 3, 128 (2019).
https://doi.org/10.22331/q-2019-03-05-128

[16] Daniel Litinski ``How to compute a 256-bit elliptic curve private key with only 50 million Toffoli gates'' (2023).
https://doi.org/10.48550/ARXIV.2306.08585
https://arxiv.org/abs/2306.08585

[17] Junhong Nie, Wei Zi, and Xiaoming Sun, ``Quantum circuit for multi-qubit Toffoli gate with optimal resource'' (2024).
https://doi.org/10.48550/ARXIV.2402.05053
https://arxiv.org/abs/2402.05053

[18] Nicholas C. Rubin, Dominic W. Berry, Fionn D. Malone, Alec F. White, Tanuj Khattar, A. Eugene DePrince, Sabrina Sicolo, Michael Küehn, Michael Kaicher, Joonho Lee, and Ryan Babbush, ``Fault-Tolerant Quantum Simulation of Materials Using Bloch Orbitals'' PRX Quantum 4 (2023).
https://doi.org/10.1103/prxquantum.4.040303

[19] Nicholas C. Rubin, Dominic W. Berry, Alina Kononov, Fionn D. Malone, Tanuj Khattar, Alec White, Joonho Lee, Hartmut Neven, Ryan Babbush, and Andrew D. Baczewski, ``Quantum computation of stopping power for inertial fusion target design'' Proceedings of the National Academy of Sciences 121 (2024).
https://doi.org/10.1073/pnas.2317772121

[20] Yuval R. Sanders, Dominic W. Berry, Pedro C.S. Costa, Louis W. Tessler, Nathan Wiebe, Craig Gidney, Hartmut Neven, and Ryan Babbush, ``Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization'' PRX Quantum 1 (2020).
https://doi.org/10.1103/prxquantum.1.020312

[21] Yewei Yuan, Chao Wang, Bei Wang, Zhao-Yun Chen, Meng-Han Dou, Yu-Chun Wu, and Guo-Ping Guo, ``An improved QFT-based quantum comparator and extended modular arithmetic using one ancilla qubit'' New Journal of Physics 25, 103011 (2023).
https://doi.org/10.1088/1367-2630/acfd52

[22] Ben Zindorfand Sougato Bose ``Efficient Implementation of Multi-Controlled Quantum Gates'' (2024).
https://doi.org/10.48550/ARXIV.2404.02279
https://arxiv.org/abs/2404.02279

[23] Shuchen Zhu, Aarthi Sundaram, and Guang Hao Low, ``Unified Architecture for a Quantum Lookup Table'' (2024).
https://doi.org/10.48550/ARXIV.2406.18030
https://arxiv.org/abs/2406.18030

Cited by

[1] Marek Gluza, Jeongrak Son, Bi Hong Tiang, René Zander, Raphael Seidel, Yudai Suzuki, Zoë Holmes, and Nelly H. Y. Ng, "Double-Bracket Quantum Algorithms for Quantum Imaginary-Time Evolution", Physical Review Letters 136 2, 020601 (2026).

[2] A. Mammola, Q. Schaeverbeke, and G. Di Molfetta, "Noisy simulations of quantum walk and quantum walk search via quantum cellular automata on a semiconducting spin processor emulator", Physical Review Research 8 1, 013117 (2026).

[3] Christine Li and Lia Yeh, Lecture Notes in Computer Science 16626, 3 (2026) ISBN:978-3-032-30838-2.

[4] Mathieu Roget and Giuseppe Di Molfetta, "A quantum walk inspired model for distributed computing on arbitrary graphs", Natural Computing 25 2, 24 (2026).

[5] Andreas Juul Bay-Smidt, Frederik Ravn Klausen, Christoph Sünderhauf, Róbert Izsák, Gemma C. Solomon, and Nick S. Blunt, "Fault-Tolerant Quantum Simulation of Generalized Hubbard Models", PRX Quantum 6 3, 030348 (2025).

[6] Sean A. Adamson and Petros Wallden, "Benincasa-Dowker-Glaser causal set actions by quantum counting", Physical Review Research 8 2, 023188 (2026).

[7] Jeongrak Son, Ray Ganardi, Shintaro Minagawa, Francesco Buscemi, Seok Hyung Lie, and Nelly H. Y. Ng, "Catalytic Channels Are the Only Noise-Robust Catalytic Processes", Physical Review Letters 136 5, 050202 (2026).

[8] Chris Heunen, Louis Lemonnier, Christopher McNally, and Alex Rice, "Quantum Circuits Are Just a Phase", Proceedings of the ACM on Programming Languages 10 POPL, 2586 (2026).

[9] Martin Plesch, Martin Friák, and Ijaz Ahamed Mohammad, "Efficient implementation of single particle Hamiltonians in exponentially reduced qubit space", Quantum 10, 2099 (2026).

[10] Jongheon Lee and Yousung Kang, "Logarithmic-depth MCT gate implementation method on a given arbitrary number of clean ancillae", Quantum Information Processing 25 1, 33 (2026).

[11] Anik Basu Bhaumik, Suman Dutta, Kyungbae Jang, Anubhab Baksi, Siyi Wang, Amit Saha, Hwajeong Seo, and Anupam Chattopadhyay, Lecture Notes in Computer Science 16487, 295 (2026) ISBN:978-981-95-8033-0.

[12] Michal Szczepanik and Emil Zak, "Utilizing redundancies in qubit Hilbert space to reduce entangling gate counts in the unitary vibrational coupled-cluster method", The Journal of Chemical Physics 163 2, 024128 (2025).

[13] Oliver O'Brien and Christoph Sünderhauf, "Quantum state preparation via piecewise QSVT", Quantum 9, 1786 (2025).

[14] Matthew P. Harrigan, Tanuj Khattar, Charles Yuan, Anurudh Peduri, Noureldin Yosri, Fionn D. Malone, Ryan Babbush, and Nicholas C. Rubin, "Expressing and Analyzing Quantum Algorithms with Qualtran", arXiv:2409.04643, (2024).

[15] Sam McArdle, Alexander M. Dalzell, Aleksander Kubica, and Fernando G. S. L. Brandão, "The Fast for the Curious: How to accelerate fault-tolerant quantum applications", arXiv:2510.26078, (2025).

[16] Jamie Heredge, Maxwell West, Lloyd Hollenberg, and Martin Sevior, "Nonunitary quantum machine learning", Physical Review Applied 23 4, 044046 (2025).

[17] David Jennings, Kamil Korzekwa, Matteo Lostaglio, Richard Ashworth, Emanuele Marsili, and Stephen Rolston, "An end-to-end quantum algorithm for nonlinear fluid dynamics with bounded quantum advantage", arXiv:2512.03758, (2025).

[18] Suman Dutta, Siyi Wang, Anubhab Baksi, Anupam Chattopadhyay, and Subhamoy Maitra, "Exact space-depth trade-offs in multicontrolled Toffoli decomposition", Physical Review A 111 5, 052611 (2025).

[19] Victor M. Bastidas, Nathan Fitzpatrick, K. J. Joven, Zane M. Rossi, Shariful Islam, Troy Van Voorhis, Isaac L. Chuang, and Yuan Liu, "Unification of finite symmetries in the simulation of many-body systems on quantum computers", Physical Review A 111 5, 052433 (2025).

[20] Maxime Remaud and Vivien Vandaele, "Ancilla-free Quantum Adder with Sublinear Depth", arXiv:2501.16802, (2025).

[21] Julien Zylberman, "Fast Laplace transforms on quantum computers", arXiv:2412.05173, (2024).

[22] Ben Zindorf and Sougato Bose, "Multi-Controlled Quantum Gates in Linear Nearest Neighbor", arXiv:2506.00695, (2025).

[23] Jędrzej Burkat and Nathan Fitzpatrick, "The Quantum Paldus Transform: Efficient Circuits with Applications", arXiv:2506.09151, (2025).

[24] Baptiste Claudon, "A simple algorithm to reflect through eigenspaces of unitaries", arXiv:2412.09320, (2024).

[25] Tom Ginsberg and Vyom Patel, "Quantum Error Detection For Early Term Fault-Tolerant Quantum Algorithms", arXiv:2503.10790, (2025).

[26] Élie Gouzien and Nicolas Sangouard, "Provably optimal exact gate synthesis from a discrete gate set", arXiv:2503.15452, (2025).

[27] Matic Petrič and René Zander, "Block-encodings as programming abstractions: The Eclipse Qrisp BlockEncoding Interface", arXiv:2604.18276, (2026).

[28] Océane Koska, Marc Baboulin, and Arnaud Gazda, "A mixed-precision quantum-classical algorithm for solving linear systems", arXiv:2502.02212, (2025).

[29] Maxime Remaud, "Quantum adders: on the structural link between the ripple-carry and carry-lookahead techniques", arXiv:2510.00840, (2025).

[30] Rakshit M. Gharat, Gopikrishnan Muraleedharan, Dominic W. Berry, and Gavin K. Brennen, "Quantum algorithm for solving differential equations using SLAC derivatives", arXiv:2605.04861, (2026).

[31] Christine Li and Lia Yeh, "Transversal AND in Quantum Codes", arXiv:2603.04548, (2026).

[32] Luisa Gerlach, Tobias Köppl, René Zander, Nicole Schweikardt, and Stefanie Scherzinger, "Quantum Computing for Query Containment of Conjunctive Queries", arXiv:2602.21803, (2026).

[33] Siyi Wang, Kyungbae Jang, Hyunji Kim, Anik Basu Bhaumik, Anubhab Baksi, Hwajeong Seo, and Anupam Chattopadhyay, "Quantum Arithmetic Circuits in Public-Key Cryptography", arXiv:2607.11713, (2026).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-13 19:37:31) and SAO/NASA ADS (last updated successfully 2026-08-13 19:37:44). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.