This paper considers the optimization of reversible circuits composed of multiple-control Toffoli gates to quantum circuits using the well-known NCV-1 (NCV) library and the recently introduced NCV-v1 library which both use a four-valued model for the quantum gates. The techniques introduced handle positive and negative controls which are central to many reversible circuit synthesis procedures. Experimental results confirm the methods are applicable to circuits obtained by diverse synthesis methods. The results also show the significant advantage of the NCV-v1 library.
This paper considers the optimization of reversible circuits composed of multiple-control Toffoli gates to quantum circuits using the well-known NCV-1 (NCV) library and the recently introduced NCV-v1 library which both use a four-valued model for the quantum gates. The techniques introduced handle positive and negative controls which are central to many reversible circuit synthesis procedures. Experimental results confirm the methods are applicable to circuits obtained by diverse synthesis methods. The results also show the significant advantage of the NCV-v1 library.
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.
Owing to the exponential nature of the memory or run-time complexity,many existing methods can only synthesize 3-qubit logic circuits using quantum logic gate library,however,a few can optimally synthesize 3-qubit logic circuits for quantum NOT,CNOT,Controlled-V and Controlled-V+(NCV)gates,the key approach reduces the NCV quantum circuit synthesis problem to four-valued logic synthesis.This paper proposes using NCV gates to create a new quantum logic gate library,which is exactly the same as NCV gate library in the synthesis of all optimal 3-qubit circuits,thus it also reduces the four-valued logic synthesis to easily solved two-valued logic synthesis.We present a 3-qubit efficient synthesis algorithms based on perfect hash function,which can quickly construct all optimal 3-qubit circuits——the average speed that synthesizes circuits with minimum cost is nearly 127 times faster than that of the best result of Maslov 2007.
This paper reviews recent developments on mapping reversible circuits to libraries of elementary quantum gates. The emphasis is on optimization of both the initial reversible circuit and the resulting quantum circuit. At the quantum level, improved realizations of single mixed-polarity multiple-control Toffoli gates are presented as well as techniques for performing quantum gate optimizations across Toffoli gate boundaries. Experimental results show the effectiveness of the methods presented using circuits from the REVLIB benchmark suite.
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.
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.
Multiple Control Toffoli (MCT) gates are the main constituent of reversible circuits. For quantum circuits, MCT gates are realized using quantum gate libraries such as NCV or NCVW which are composed of universal quantum gates like NOT, CNOT, V/V+, and W/W+. In order to improve the design of quantum circuits, the mapping of MCT gates to a cascade of these quantum gates has to be improved as well. In this work, we propose reconfigured structures of quantum gates realizing MCT gates. To this end, we rely on the established mapping structure, but append redundant gates which can be used afterwards for simplifications. Eventually, the proposed design is mapped to an NCVW quantum circuit. We have successfully tested our mapping technique. The obtained results have experimentally been compared to related work.