Optimal Multi-Bit Toffoli Gate Synthesis

Young Min Jun, In Chan Choi

Research output: Contribution to journalArticlepeer-review


Multi-bit Toffoli gates form an essential quantum gate class for quantum algorithms. They should be efficiently decomposed into elementary single- or multi-qubit quantum gates, such as CNOT, T, and Hadarmard, for a scalable implementation of a quantum algorithm. We propose an engineering method for the practical synthesis of a multi-bit Toffoli gate. Two optimization models and their closed-form solutions are presented for optimal decomposition of the multi-bit Toffoli gate. These models are based on linearized multi-objective integer programming with parameters such as the number of target ancillae, ancillae states, and basis gates. The proposed method supports the systematic handling of quantum circuit constraints, including the total number of available qubits and maximum circuit depth, which depend on various quantum hardware specifications. Our approach exhibits promise in the noisy intermediate-scale quantum environment by providing a rapid and optimal method for synthesizing multi-bit Toffoli gates in diverse and unpredictable quantum hardware specifications.

Original languageEnglish
Pages (from-to)27342-27351
Number of pages10
JournalIEEE Access
Publication statusPublished - 2023

Bibliographical note

Publisher Copyright:
© 2013 IEEE.


  • Combinatorial optimization
  • NISQ
  • quantum algorithm
  • Toffoli gate synthesis

ASJC Scopus subject areas

  • General Computer Science
  • General Materials Science
  • General Engineering
  • Electrical and Electronic Engineering


Dive into the research topics of 'Optimal Multi-Bit Toffoli Gate Synthesis'. Together they form a unique fingerprint.

Cite this