Quantum Fourier addition simplified to Toffoli addition

Alexandru Paler*

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

33 Downloads (Pure)


Quantum addition circuits are considered being of two types: (1) Toffoli-adder circuits which use only classical reversible gates (controlled-not and Toffoli), and (2) QFT-adder circuits based on the quantum Fourier transformation. We present a systematic translation of the QFT addition circuit into a Toffoli-based adder. This result shows that QFT addition has fundamentally the same fault-tolerance cost (e.g., T count) as the most cost-efficient Toffoli adder: instead of using approximate decompositions of the gates from the QFT circuit, it is more efficient to merge gates. In order to achieve this, we formulated circuit identities for multicontrolled gates and apply the identities algorithmically. The employed techniques can be used to automate quantum circuit optimization heuristics.

Original languageEnglish
Article number042444
Pages (from-to)1-6
Number of pages6
JournalPhysical Review A
Issue number4
Publication statusPublished - 27 Oct 2022
MoE publication typeA1 Journal article-refereed


Dive into the research topics of 'Quantum Fourier addition simplified to Toffoli addition'. Together they form a unique fingerprint.

Cite this