BROWSE
Detail
Journal Article
Logarithmic-depth MCT gate implementation method on a given arbitrary number of clean ancillae
- Authors
- Jongheon Lee, Yousung Kang
- Issue Date
- 2026-01
- Citation
- Quantum Information Processing, v.25, pp.1-37
- ISSN
- 1570-0755
- Publisher
- Springer Nature
- Language
- English
- Type
- Journal Article
- Abstract
- One of the key operations in various quantum algorithms, including Grover’s algorithm, is the multi-controlled Toffoli (MCT) gate. This work proposes optimal design techniques for the MCT gate using the conditionally clean ancillae strategy, assuming that an arbitrary number of clean ancillae are available. We consider two primary cases: first, when only a single clean ancilla is available; and second, when the number of clean ancillae is O(n), where n is the number of controls in the MCT gate. For the case of a single clean ancilla, we propose a novel design method that achieves better efficiency compared to a previous approach. While prior work yields a Toffoli-depth of O(n), our proposed method reduces the Toffoli-depth to O(n). Moreover, by employing this new technique as a subroutine within previously proposed methods for the cases of two or three clean ancillae, we demonstrate both logically and empirically an improvement in time complexity. Additionally, prior work addressed optimal designs only when the number of clean ancillae was up to approximately logn, without providing efficient strategies beyond this regime. In this study, we also present efficient MCT gate constructions when a sufficiently large number of clean ancillae are available. We confirm, both theoretically and empirically, that the Toffoli-depth decreases as the number of clean ancillae increases. In conclusion, this work highlights that the optimal MCT design strategy depends on the availability of clean ancillae. It also indirectly suggests a threshold point at which the optimal design strategy transitions, depending on the number of ancillae provided.
- Keyword
- Clean ancillae, Dirty ancillae, MCT gate, Toffoli-count, Toffoli-depth
- KSP Keywords
- Design method, Design techniques, Implementation method, Optimal design strategy, Time Complexity, novel design, quantum algorithm
This work is distributed under the term of Creative Commons License (CCL)
(CC BY)
(CC BY)
