Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Access

Optimal Multi-Bit Toffoli Gate Synthesis

Young-Min Jun, In-Chan Choi

Published Jan 1, 2023• 3 citations
Publisher

Abstract

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.

DOI
10.1109/access.2023.3243798

Related papers

Layout Synthesis for Quantum Circuits Considering Toffoli Gate Decomposition

Po-Wei Chen, Sheng-Tan Huang, Shao‐Yun Fang

State-of-the-art studies on quantum layout synthesis have proposed various approaches based on the assumption that the input circuit is only composed of single-qubit and two-qubit gates. This assumption greatly simplifies the layout synthesis problem, and thus they only require ensuring that all controlled-NOT (CNOT) gates satisfy the hardware constraints imposed by a given coupling graph. However, during the design of quantum circuits, multi-controlled Toffoli (MCT) gates are usually used to better characterize the function of the circuits. Directly decomposing them into single and two-qubit gates with a fixed routine ignores the flexibility and optimization opportunity provided by various decomposition (i.e., logic synthesis) possibilities and thus suffers from sub-optimal results. This article proposes a co-optimization approach for quantum logic and layout synthesis. The MCT gates are first decomposed into Toffoli gates, and an efficient qubit mapping checking process is proposed to optimally solve the SWAP-free layout synthesis problem by automatically determining the decomposition result of each Toffoli gate. If a SWAP-free result cannot be found, the proposed algorithm flow is then used to obtain a solution that minimizes the total cost that simultaneously counts the cost caused by the different decomposition methods for Toffoli gates and the cost induced by SWAP gates. Compared with a state-of-the-art method, the proposed approach reduces the number of additional CNOT gates by 16% with around 25X runtime speedup for the cases with SWAP-free solutions, which cannot be obtained without the co-optimization approach.

ACM Transactions on Design Automation of Electronic Systems•Jun 16, 2025•1 citation

Hardware-Conscious Optimization of the Quantum Toffoli Gate

Max Aksel Bowman, Pranav Gokhale, Jeffrey M. Larson +2 more

While quantum computing holds great potential in combinatorial optimization, electronic structure calculation, and number theory, the current era of quantum computing is limited by noisy hardware. Many quantum compilation approaches can mitigate the effects of imperfect hardware by optimizing quantum circuits for objectives such as critical path length. Few approaches consider quantum circuits in terms of the set of vendor-calibrated operations (i.e., native gates) available on target hardware. This manuscript expands the analytical and numerical approaches for optimizing quantum circuits at this abstraction level. We present a procedure for combining the strengths of analytical native gate-level optimization with numerical optimization. Although we focus on optimizing Toffoli gates on the IBMQ native gate set, the methods presented are generalizable to any gate and superconducting qubit architecture. Our optimized Toffoli gate implementation demonstrates an 18% reduction in infidelity compared with the canonical implementation as benchmarked on IBM Jakarta with quantum process tomography. Assuming the inclusion of multi-qubit cross-resonance (MCR) gates in the IBMQ native gate set, we produce Toffoli implementations with only six multi-qubit gates, a 25% reduction from the canonical eight multi-qubit implementations for linearly connected qubits.

arXiv:2209.02669•ACM Transactions on Quantum Computing•Jul 20, 2023•17 citations

A study of optimal 4-bit reversible circuit synthesis from mixed-polarity Toffoli gates

Marek Szyprowski, Paweł Kerntopf

Optimal synthesis of reversible circuits is a very hard task. In 2010, a method and a tool of practical usage for finding optimal circuits built from multi-control Toffoli gates for any 4-bit reversible specification were finally developed. In 2011 we published an extension to the algorithm, which allows to reduce the quantum cost of the resulting circuits. In this paper we present another extension to this approach. Namely, we have extended the reversible gate library to mixed-polarity multi-control Toffoli gates (i.e. with both positive and negative controls). Our experimental results for the known reversible benchmarks show that using mixed-polarity Toffoli gates gives significant savings in gate count. The paper presents standard computational experiments for circuit synthesis. These results have implications in testing synthesis algorithms for reversible mixed-polarity circuits and quantum circuits.

IEEE International Conference on Nanotechnology (IEEE-NANO)•Aug 1, 2012•9 citations

Spin-Based Simulation and Optimization of Multi-Qubit Quantum Gates

Dolananda Sri Naga Phani Sarma Mokkapati, V Ramesh Kumar, D. De +1 more

Spin-based quantum architectures offer a promising route toward scalable and practical quantum computing owing to their long coherence times, high-fidelity gate operations, and compatibility with established semiconductor fabrication processes. This work focuses on the design, decomposition, and simulation of fundamental multi-qubit logic gates on spin-based architectures. An optimized CNOT gate decomposition is presented, achieving a $36.36 \%$ reduction in elementary operations, verified through quantum circuit simulation. Furthermore, a resource-efficient Toffoli (CCNOT) gate is developed, yielding a $38 \%$ reduction in elementary gates and demonstrating improved T-depth efficiency. Finally, a four-qubit circuit example is presented, illustrating the scalability of the pseudocode and validating the correctness of the proposed approach.

International Conference on Research in Computational Intelligence and Communication Networks (ICRCICN)•Dec 20, 2025•0 citations

Systematic Optimization of Quantum Circuits via Toffoli Permutation and Local Search

GEORGE PAPAKONSTANTINOU

The synthesis of efficient reversible logic circuits is critical for fault-tolerant quantum computing. While standard libraries often treat the Toffoli gate as an atomic unit, its realization in the NCV library requires decomposition into 5 elementary gates. In this work, we propose a novel, systematic four-phase optimization methodology. First, we generate an optimal circuit in the strict NCT library (NOT, CNOT, Toffoli) using automated synthesis. Second, we replace each Toffoli gate with a specific NCV decomposition, permuting the control lines such that the final internal CNOT gate matches the subsequent linear gate in the circuit, allowing us to apply a cancellation rule (X ·X = I). Finally, post-synthesis local searches are applied using Mixed- Integer Non-Linear Programming (MINLP) techniques to further reduce the total gate count. Applying this method to the MIG, TSG, and MKG gates, we achieve Quantum Costs of 7, 14, and 12 respectively, matching or beating the best-known literature benchmarks.

•Apr 19, 2026•1 citation

A Study of Optimal 4-bit Reversible Circuit Synthesis from Mixed-Polarity

Toffoli Gates, Marek Szyprowski, Pawel Kerntopfi

Optimal synthesis of reversible circuits is a very hard task. In 2010, a method and a tool of practical usage for finding optimal circuits built from multi-control Toffoli gates for any 4-bit reversible specification were finally developed. In 2011 we published an extension to the algorithm, which allows to reduce the quantum cost of the resulting circuits. In this paper we present another extension to this approach. Namely, we have extended the reversible gate library to mixed-polarity multi-control Toffoli gates (Le. with both positive and negative controls). Our experimental results for the known reversible benchmarks show that using mixed-polarity Toffoli gates gives significant savings in gate count. The paper presents standard computational experiments for circuit synthesis. These results have implications in testing synthesis algorithms for reversible mixed-polarity circuits and quantum circuits.

•Jan 1, 2012•0 citations
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.
State-of-the-art studies on quantum layout synthesis have proposed various approaches based on the assumption that the input circuit is only composed of single-qubit and two-qubit gates. This assumption greatly simplifies the layout synthesis problem, and thus they only require ensuring that all controlled-NOT (CNOT) gates satisfy the hardware constraints imposed by a given coupling graph. However, during the design of quantum circuits, multi-controlled Toffoli (MCT) gates are usually used to better characterize the function of the circuits. Directly decomposing them into single and two-qubit gates with a fixed routine ignores the flexibility and optimization opportunity provided by various decomposition (i.e., logic synthesis) possibilities and thus suffers from sub-optimal results. This article proposes a co-optimization approach for quantum logic and layout synthesis. The MCT gates are first decomposed into Toffoli gates, and an efficient qubit mapping checking process is proposed to optimally solve the SWAP-free layout synthesis problem by automatically determining the decomposition result of each Toffoli gate. If a SWAP-free result cannot be found, the proposed algorithm flow is then used to obtain a solution that minimizes the total cost that simultaneously counts the cost caused by the different decomposition methods for Toffoli gates and the cost induced by SWAP gates. Compared with a state-of-the-art method, the proposed approach reduces the number of additional CNOT gates by 16% with around 25X runtime speedup for the cases with SWAP-free solutions, which cannot be obtained without the co-optimization approach.
While quantum computing holds great potential in combinatorial optimization, electronic structure calculation, and number theory, the current era of quantum computing is limited by noisy hardware. Many quantum compilation approaches can mitigate the effects of imperfect hardware by optimizing quantum circuits for objectives such as critical path length. Few approaches consider quantum circuits in terms of the set of vendor-calibrated operations (i.e., native gates) available on target hardware. This manuscript expands the analytical and numerical approaches for optimizing quantum circuits at this abstraction level. We present a procedure for combining the strengths of analytical native gate-level optimization with numerical optimization. Although we focus on optimizing Toffoli gates on the IBMQ native gate set, the methods presented are generalizable to any gate and superconducting qubit architecture. Our optimized Toffoli gate implementation demonstrates an 18% reduction in infidelity compared with the canonical implementation as benchmarked on IBM Jakarta with quantum process tomography. Assuming the inclusion of multi-qubit cross-resonance (MCR) gates in the IBMQ native gate set, we produce Toffoli implementations with only six multi-qubit gates, a 25% reduction from the canonical eight multi-qubit implementations for linearly connected qubits.
Optimal synthesis of reversible circuits is a very hard task. In 2010, a method and a tool of practical usage for finding optimal circuits built from multi-control Toffoli gates for any 4-bit reversible specification were finally developed. In 2011 we published an extension to the algorithm, which allows to reduce the quantum cost of the resulting circuits. In this paper we present another extension to this approach. Namely, we have extended the reversible gate library to mixed-polarity multi-control Toffoli gates (i.e. with both positive and negative controls). Our experimental results for the known reversible benchmarks show that using mixed-polarity Toffoli gates gives significant savings in gate count. The paper presents standard computational experiments for circuit synthesis. These results have implications in testing synthesis algorithms for reversible mixed-polarity circuits and quantum circuits.
Spin-based quantum architectures offer a promising route toward scalable and practical quantum computing owing to their long coherence times, high-fidelity gate operations, and compatibility with established semiconductor fabrication processes. This work focuses on the design, decomposition, and simulation of fundamental multi-qubit logic gates on spin-based architectures. An optimized CNOT gate decomposition is presented, achieving a 36.36%36.36 \%36.36% reduction in elementary operations, verified through quantum circuit simulation. Furthermore, a resource-efficient Toffoli (CCNOT) gate is developed, yielding a 38%38 \%38% reduction in elementary gates and demonstrating improved T-depth efficiency. Finally, a four-qubit circuit example is presented, illustrating the scalability of the pseudocode and validating the correctness of the proposed approach.
The synthesis of efficient reversible logic circuits is critical for fault-tolerant quantum computing. While standard libraries often treat the Toffoli gate as an atomic unit, its realization in the NCV library requires decomposition into 5 elementary gates. In this work, we propose a novel, systematic four-phase optimization methodology. First, we generate an optimal circuit in the strict NCT library (NOT, CNOT, Toffoli) using automated synthesis. Second, we replace each Toffoli gate with a specific NCV decomposition, permuting the control lines such that the final internal CNOT gate matches the subsequent linear gate in the circuit, allowing us to apply a cancellation rule (X ·X = I). Finally, post-synthesis local searches are applied using Mixed- Integer Non-Linear Programming (MINLP) techniques to further reduce the total gate count. Applying this method to the MIG, TSG, and MKG gates, we achieve Quantum Costs of 7, 14, and 12 respectively, matching or beating the best-known literature benchmarks.
Optimal synthesis of reversible circuits is a very hard task. In 2010, a method and a tool of practical usage for finding optimal circuits built from multi-control Toffoli gates for any 4-bit reversible specification were finally developed. In 2011 we published an extension to the algorithm, which allows to reduce the quantum cost of the resulting circuits. In this paper we present another extension to this approach. Namely, we have extended the reversible gate library to mixed-polarity multi-control Toffoli gates (Le. with both positive and negative controls). Our experimental results for the known reversible benchmarks show that using mixed-polarity Toffoli gates gives significant savings in gate count. The paper presents standard computational experiments for circuit synthesis. These results have implications in testing synthesis algorithms for reversible mixed-polarity circuits and quantum circuits.