Decomposing Quantum Generalized Toffoli with an Arbitrary Number of Ancilla

2019/04/02 by Jonathan M. Baker, Casey Duckering, Baker, Jonathan M. +5 · 1 citation
Computer Science · Engineering · #Emerging Technologies (cs.ET) #FOS: Computer and information sciences #FOS: Physical sciences #Low-power high-performance VLSI design #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Quantum-Dot Cellular Automata

paper · pdf · doi:10.48550/arxiv.1904.01671

openalex publication_date 2019/04/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present a general decomposition of the Generalized Toffoli, and for completeness, the multi-target gate using an arbitrary number of clean or dirty ancilla. While prior work has shown how to decompose the Generalized Toffoli using 0, 1, or O(n) many clean ancilla and 0, 1, and n-2 dirty ancilla, we provide a generalized algorithm to bridge the gap, i.e. this work gives an algorithm to generate a decomposition for any number of clean or dirty ancilla. While it is hard to guarantee optimality, our decompositions guarantee a decrease in circuit depth as the number of ancilla increases.

Citations

• Elementary gates for quantum computation
• Decompositions of n-qubit Toffoli Gates with Linear Circuit Complexity

Cited by

• Primitive Quantum Gates for an SU(3) Discrete Subgroup: Σ(72×3)

Related

• Modifying n-qubit controlled-ZX gate to be n-qubit Toffoli gate
• Stesso: A reconfigurable decomposition of n-bit Toffoli gates using symmetrical logical structures and adjustable support qubits
• On Exact Space-Depth Trade-Offs in Multi-Controlled Toffoli Decomposition
• Graphical Stabilizer Decompositions for Multi-Control Toffoli Gate Dense Quantum Circuits
• The simplified Toffoli gate implementation by Margolus is optimal