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

Systematic Optimization of Quantum Circuits via Toffoli Permutation and Local Search

GEORGE PAPAKONSTANTINOU

Published Apr 19, 2026• 1 citation
Publisher

Abstract

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.

DOI
10.31224/6865

Related papers

Systematic Synthesis and Optimization of Reversible Quantum Circuits via MINLP, Toffoli Permutation, and Local Search

GEORGE PAPAKONSTANTINOU

The synthesis of efficient reversible logic circuits is critical for fault-tolerant quantum computing (FTQC). The primary motivation of this work is to overcome the inherent disadvantages of existing synthesis techniques: approximate heuristic methods often miss optimal solutions, while pure exact computational methods suffer from combinatorial explosion on deep circuits. While the strict NCT library (NOT, CNOT, Toffoli) is often preferred due to the high cost of distilling non-Clifford states required for arbitrary gates, standard physical implementations frequently utilize the broader NCV library (NOT, CNOT, V, V-dagger), requiring the decomposition of Toffoli gates into five elementary operations. To bridge this gap, this paper presents a unified, highly scalable methodology for the optimal design of reversible circuits across both libraries. First, a Mixed-Integer Non-Linear Programming (MINLP) formulation, linearized for the high-performance IBM ILOG CPLEX solver, is introduced to automate the exact generation of globally optimal strict NCT topologies. Second, a systematic four-phase optimization framework is proposed to reduce NCV costs. By replacing Toffoli gates with specific NCV decompositions, permuting control lines to match subsequent linear gates, and applying exact local searches via an extended MINLP solver on bounded sliding windows, significant gate cancellations are achieved. Applying this methodology to prominent primitives (MIG, SAYEM, URG, TSG, and MKG), we match global NCT optimality constraints and achieve highly optimized NCV Quantum Costs of 7, 14, and 12 for the MIG, TSG, and MKG gates, respectively, establishing best-known upper bounds that significantly outperform heuristic literature benchmarks.

Quantum Reports•Aug 14, 2026•0 citations

Optimal Design of Reversible Circuits in the Strict NCT Library

GEORGE PAPAKONSTANTINOU

The synthesis of reversible logic circuits is a fundamental step in the design of fault-tolerant quantum arithmetic. Existing literature frequently minimizes Quantum Cost (QC) by utilizing the NCV library, which permits controlled-V and Vdagger gates. However, in the context of Fault-Tolerant Quantum Computing (FTQC), the strict NCT library (NOT, CNOT, Toffoli) is often preferred due to the high cost of distilling non-Clifford states required for arbitrary V-gates. Moreover, in the classical design of reversible circuits, only the NCT library can be used as V-gates are not available. In this paper, a new design method for reversible circuits is proposed, based on Mixed-Integer Non-Linear Programming (MINLP) within the Strict NCT Library. By formulating the problem as an MINLP model in GAMS, we successfully automated the optimization of five prominent reversible primitives (TSG, MKG, MIG, SAYEM, and URG) within the strict NCT library. Comparative analysis with the NCV costs found in the literature shows that the costs within the NCT library are comparable or better.

•Feb 16, 2026•3 citations

Optimization of Reversible Circuits Using Toffoli Decompositions with Negative Controls

Mariam Gado, Ahmed Younes

The synthesis and optimization of quantum circuits are essential for the construction of quantum computers. This paper proposes two methods to reduce the quantum cost of 3-bit reversible circuits. The first method utilizes basic building blocks of gate pairs using different Toffoli decompositions. These gate pairs are used to reconstruct the quantum circuits where further optimization rules will be applied to synthesize the optimized circuit. The second method suggests using a new universal library, which provides better quantum cost when compared with previous work in both cost015 and cost115 metrics; this proposed new universal library “Negative NCT” uses gates that operate on the target qubit only when the control qubit’s state is zero. A combination of the proposed basic building blocks of pairs of gates and the proposed Negative NCT library is used in this work for synthesis and optimization, where the Negative NCT library showed better quantum cost after optimization compared with the NCT library despite having the same circuit size. The reversible circuits over three bits form a permutation group of size 40,320 (23!), which is a subset of the symmetric group, where the NCT library is considered as the generators of the permutation group.

Symmetry•Jun 7, 2021•9 citations

Optimal Design of Reversible Circuits in the Strict NCT Library

GEORGE PAPAKONSTANTINOU

The synthesis of reversible logic circuits is a fundamental step in the design of fault-tolerant quantum arithmetic. Existing literature frequently minimizes Quantum Cost (QC) by utilizing the NCV library, which permits controlled-V and Vdagger gates. However, in the context of Fault-Tolerant Quantum Computing (FTQC), the strict NCT library (NOT, CNOT, Toffoli) is often preferred due to the high cost of distilling non-Clifford states required for arbitrary V-gates. Moreover, in the classical design of reversible circuits, only the NCT library can be used as V-gates are not available. In this paper, a new design method for reversible circuits is proposed, based on Mixed-Integer Non-Linear Programming (MINLP) within the Strict NCT Library. By formulating the problem as an MINLP model in GAMS, we successfully automated the optimization of five prominent reversible primitives (TSG, MKG, MIG, SAYEM, and URG) within the strict NCT library. Comparative analysis with the NCV costs found in the literature shows that the costs within the NCT library are comparable or better.

•Jan 13, 2026•0 citations

Improved NCV Gate Realization of Arbitrary Size Toffoli Gates

Abhoy Kole, Kamalika Datta

The problem of synthesis and optimization of reversible and quantum circuits have drawn the attention of researchers in recent years. The typical design flow for such circuits first carries out the step of synthesis in terms of reversible gates, and then maps (decomposes) each reversible gate into equivalent set of quantum gates (e.g. from the NCV library). Since its initial proposal in realizing a Toffoli gate using quantum gates, several structural modifications have been proposed in the literature in order to reduce the cost of the generated netlist. The most recently introduced approach produces improved NCV cascade successively by partitioning the control lines of the given Toffoli gate in all possible ways, and replacing intermediate Toffoli gates with optimized equivalent NCV cascades form a catalog. In this approach the complexity of decomposing large Toffoli gates is high. In the present paper an efficient heuristic for partitioning the control lines of a given Toffoli gate is proposed. This heuristic is used for decomposition of the Toffoli gate without using any NCV catalog, after applying a template based optimization step. The cost of resultant circuit is similar to or sometimes better than the one reported by previous approaches.

International Conference on VLSI Design•Jan 1, 2017•11 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
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.
The synthesis of efficient reversible logic circuits is critical for fault-tolerant quantum computing (FTQC). The primary motivation of this work is to overcome the inherent disadvantages of existing synthesis techniques: approximate heuristic methods often miss optimal solutions, while pure exact computational methods suffer from combinatorial explosion on deep circuits. While the strict NCT library (NOT, CNOT, Toffoli) is often preferred due to the high cost of distilling non-Clifford states required for arbitrary gates, standard physical implementations frequently utilize the broader NCV library (NOT, CNOT, V, V-dagger), requiring the decomposition of Toffoli gates into five elementary operations. To bridge this gap, this paper presents a unified, highly scalable methodology for the optimal design of reversible circuits across both libraries. First, a Mixed-Integer Non-Linear Programming (MINLP) formulation, linearized for the high-performance IBM ILOG CPLEX solver, is introduced to automate the exact generation of globally optimal strict NCT topologies. Second, a systematic four-phase optimization framework is proposed to reduce NCV costs. By replacing Toffoli gates with specific NCV decompositions, permuting control lines to match subsequent linear gates, and applying exact local searches via an extended MINLP solver on bounded sliding windows, significant gate cancellations are achieved. Applying this methodology to prominent primitives (MIG, SAYEM, URG, TSG, and MKG), we match global NCT optimality constraints and achieve highly optimized NCV Quantum Costs of 7, 14, and 12 for the MIG, TSG, and MKG gates, respectively, establishing best-known upper bounds that significantly outperform heuristic literature benchmarks.
The synthesis of reversible logic circuits is a fundamental step in the design of fault-tolerant quantum arithmetic. Existing literature frequently minimizes Quantum Cost (QC) by utilizing the NCV library, which permits controlled-V and Vdagger gates. However, in the context of Fault-Tolerant Quantum Computing (FTQC), the strict NCT library (NOT, CNOT, Toffoli) is often preferred due to the high cost of distilling non-Clifford states required for arbitrary V-gates. Moreover, in the classical design of reversible circuits, only the NCT library can be used as V-gates are not available. In this paper, a new design method for reversible circuits is proposed, based on Mixed-Integer Non-Linear Programming (MINLP) within the Strict NCT Library. By formulating the problem as an MINLP model in GAMS, we successfully automated the optimization of five prominent reversible primitives (TSG, MKG, MIG, SAYEM, and URG) within the strict NCT library. Comparative analysis with the NCV costs found in the literature shows that the costs within the NCT library are comparable or better.
The synthesis and optimization of quantum circuits are essential for the construction of quantum computers. This paper proposes two methods to reduce the quantum cost of 3-bit reversible circuits. The first method utilizes basic building blocks of gate pairs using different Toffoli decompositions. These gate pairs are used to reconstruct the quantum circuits where further optimization rules will be applied to synthesize the optimized circuit. The second method suggests using a new universal library, which provides better quantum cost when compared with previous work in both cost015 and cost115 metrics; this proposed new universal library “Negative NCT” uses gates that operate on the target qubit only when the control qubit’s state is zero. A combination of the proposed basic building blocks of pairs of gates and the proposed Negative NCT library is used in this work for synthesis and optimization, where the Negative NCT library showed better quantum cost after optimization compared with the NCT library despite having the same circuit size. The reversible circuits over three bits form a permutation group of size 40,320 (23!), which is a subset of the symmetric group, where the NCT library is considered as the generators of the permutation group.
The synthesis of reversible logic circuits is a fundamental step in the design of fault-tolerant quantum arithmetic. Existing literature frequently minimizes Quantum Cost (QC) by utilizing the NCV library, which permits controlled-V and Vdagger gates. However, in the context of Fault-Tolerant Quantum Computing (FTQC), the strict NCT library (NOT, CNOT, Toffoli) is often preferred due to the high cost of distilling non-Clifford states required for arbitrary V-gates. Moreover, in the classical design of reversible circuits, only the NCT library can be used as V-gates are not available. In this paper, a new design method for reversible circuits is proposed, based on Mixed-Integer Non-Linear Programming (MINLP) within the Strict NCT Library. By formulating the problem as an MINLP model in GAMS, we successfully automated the optimization of five prominent reversible primitives (TSG, MKG, MIG, SAYEM, and URG) within the strict NCT library. Comparative analysis with the NCV costs found in the literature shows that the costs within the NCT library are comparable or better.
The problem of synthesis and optimization of reversible and quantum circuits have drawn the attention of researchers in recent years. The typical design flow for such circuits first carries out the step of synthesis in terms of reversible gates, and then maps (decomposes) each reversible gate into equivalent set of quantum gates (e.g. from the NCV library). Since its initial proposal in realizing a Toffoli gate using quantum gates, several structural modifications have been proposed in the literature in order to reduce the cost of the generated netlist. The most recently introduced approach produces improved NCV cascade successively by partitioning the control lines of the given Toffoli gate in all possible ways, and replacing intermediate Toffoli gates with optimized equivalent NCV cascades form a catalog. In this approach the complexity of decomposing large Toffoli gates is high. In the present paper an efficient heuristic for partitioning the control lines of a given Toffoli gate is proposed. This heuristic is used for decomposition of the Toffoli gate without using any NCV catalog, after applying a template based optimization step. The cost of resultant circuit is similar to or sometimes better than the one reported by previous approaches.
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.