The simplified Toffoli gate implementation by Margolus is optimal

Abstract

Unitary operations are expressed in the quantum circuit model as a finite sequence of elementary gates, such as controlled-not gates and single qubit gates. We prove that the simplified Toffoli gate by Margolus, which coincides with the Toffoli gate up to a single change of sign, cannot be realized with less than three controlled-not gates. If the circuit is implemented with three controlled-not gates, then at least four additional single qubit gates are necessary. This proves that the implementation suggested by Margolus is optimal.

15 pages, 44 figures, submitted to Quantum Information and Computation

References in corpus (1)

• Elementary gates for quantum computation

Cited by in corpus (5)

• Synthesis of Reversible Functions Beyond Gate Count and Quantum Cost
• High-Round QAOA for MAX $k$-SAT on Trapped Ion NISQ Devices
• Uncomputation in the Qrisp high-level Quantum Programming Framework
• Benchmarking 16-element quantum search algorithms on superconducting quantum processors
• Improved FRQI on superconducting processors and its restrictions in the NISQ era