Decomposing Quantum Generalized Toffoli with an Arbitrary Number of Ancilla

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.

arXiv comment10 pages, 5 figures

References in corpus (1)

• Elementary gates for quantum computation

Cited by in corpus (6)

• Time-Sliced Quantum Circuit Partitioning for Modular Architectures
• Polylogarithmic-depth controlled-NOT gates without ancilla qubits
• Dancing the Quantum Waltz: Compiling Three-Qubit Gates on Four Level Architectures
• Communication Trade Offs in Intermediate Qudit Circuits
• QContext: Context-Aware Decomposition for Quantum Gates
• Solving lattice gauge theories using the quantum Krylov algorithm and qubitization