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

Quantum Reports

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

GEORGE PAPAKONSTANTINOU

Published Aug 14, 2026• 0 citations
Publisher

Abstract

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.

DOI
10.3390/quantum8030079

Related papers

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

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•1 citation

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

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•8 citations

SAT-based Exact Synthesis of Ternary Reversible Circuits using a Functionally Complete Gate Library

Abhoy Kole, Kamalika Datta, Indranil Sengupta +1 more

The problem of synthesis and optimization of reversible and quantum circuits have drawn the attention of researchers for the last two decades due to increasing interest in quantum computing. Although lot of works have been done on the synthesis of binary reversible circuits, very less works have been reported on the synthesis of ternary reversible circuits. Ternary circuits have lower cost of implementation as compared to their binary counterparts. However, the synthesis approaches that exist for ternary reversible circuits either use too many circuit lines (qutrits) or too many gates. Only one prior work has discussed the problem of generating cost-optimal ternary reversible circuits, but for a very restrictive gate library, which limits the approach to a specific subset of ternary reversible functions and often the solution becomes sub-optimal due to the imposed restrictions. The present paper overcomes that restriction, and uses multiple control ternary Toffoli gates with all possible ternary target operations as the gate library. This gate library is functionally complete and can be used to synthesize any arbitrary function. The proposed SAT-based synthesis approach provides low cost solutions in terms of the number of gates for any arbitrary ternary reversible function. Experimental results on various randomly generated permutations as well as standard ternary benchmarks establish this claim. The results can be used as template for other synthesis approaches by observing how far they deviate from the optimal solutions.

Euromicro Conference on Digital System Design (DSD)•Aug 1, 2022•1 citation

Greedy Algorithm for Optimizing NCT-Based Reversible Circuits Using Optimization Rules

Khaled El-Wazan, Mohamed Hosny Abdo Osman, Ahmed Younes

Reversible circuit synthesis is critical for quantum computing, but existing methods suffer from high gate counts that increase error susceptibility. This paper introduces a permutation group-driven greedy algorithm that reduces primitive quantum gates systematically in reversible circuits built from NOT, Feyn-man, and Toffoli (NCT) gates. By exploiting the algebraic structure of reversible functions, the proposed method applies iterative gate cancellation and substitution rules to minimize circuit depth. Experiments on NCT-based reversible circuits using IBM's Qiskit demonstrate substantial reductions in primitive quantum gates.

International Conference on Machine Intelligence and Smart Innovation (ICMISI)•May 10, 2025•1 citation
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 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 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 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 problem of synthesis and optimization of reversible and quantum circuits have drawn the attention of researchers for the last two decades due to increasing interest in quantum computing. Although lot of works have been done on the synthesis of binary reversible circuits, very less works have been reported on the synthesis of ternary reversible circuits. Ternary circuits have lower cost of implementation as compared to their binary counterparts. However, the synthesis approaches that exist for ternary reversible circuits either use too many circuit lines (qutrits) or too many gates. Only one prior work has discussed the problem of generating cost-optimal ternary reversible circuits, but for a very restrictive gate library, which limits the approach to a specific subset of ternary reversible functions and often the solution becomes sub-optimal due to the imposed restrictions. The present paper overcomes that restriction, and uses multiple control ternary Toffoli gates with all possible ternary target operations as the gate library. This gate library is functionally complete and can be used to synthesize any arbitrary function. The proposed SAT-based synthesis approach provides low cost solutions in terms of the number of gates for any arbitrary ternary reversible function. Experimental results on various randomly generated permutations as well as standard ternary benchmarks establish this claim. The results can be used as template for other synthesis approaches by observing how far they deviate from the optimal solutions.
Reversible circuit synthesis is critical for quantum computing, but existing methods suffer from high gate counts that increase error susceptibility. This paper introduces a permutation group-driven greedy algorithm that reduces primitive quantum gates systematically in reversible circuits built from NOT, Feyn-man, and Toffoli (NCT) gates. By exploiting the algebraic structure of reversible functions, the proposed method applies iterative gate cancellation and substitution rules to minimize circuit depth. Experiments on NCT-based reversible circuits using IBM's Qiskit demonstrate substantial reductions in primitive quantum gates.