Constraints

Optimizing multiple-control Toffoli quantum circuit design with constraint programming

Jeenah Jung, Kevin Dalmeijer, Pascal Van Hentenryck

Published Jul 18, 2026• 0 citations

Abstract

Abstract As quantum technology advances, the efficient design of quantum circuits has become an important area of research. This paper provides an introduction to the MCT quantum circuit design problem for reversible Boolean functions with the necessary background in quantum computing to comprehend the problem. While this is a well-studied problem, optimization models that minimize the true objective have only been explored recently. This paper introduces a new optimization model and symmetry-breaking constraints that improve solving time by up to two orders of magnitude compared to earlier work when a Constraint Programming solver is used. Experiments with up to seven qubits and using up to 15 quantum gates result in several new best-known circuits, obtained by any method, for well-known benchmarks. Several in-depth analyses are presented to validate the effectiveness of the symmetry-breaking constraints from multiple perspectives. Finally, an extensive comparison with other approaches shows that optimization models may require more time but can provide superior circuits with optimality guarantees.

DOI: 10.1007/s10601-026-09399-0

Related papers

A New Optimization Model for Multiple-Control Toffoli Quantum Circuit Design

Jihye Jung, Kevin Dalmeijer, Pascal Van Hentenryck

As quantum technology advances, the efficient design of quantum circuits has become an important area of research. This paper provides an introduction to the MCT quantum circuit design problem for reversible Boolean functions with the necessary background in quantum computing to comprehend the problem. While this is a well-studied problem, optimization models that minimize the true objective have only been explored recently. This paper introduces a new optimization model and symmetry-breaking constraints that improve solving time by up to two orders of magnitude compared to earlier work when a Constraint Programming solver is used. Experiments with up to seven qubits and using up to 15 quantum gates result in several new best-known circuits, obtained by any method, for well-known benchmarks. Several in-depth analyses are presented to validate the effectiveness of the symmetry-breaking constraints from multiple perspectives. Finally, an extensive comparison with other approaches shows that optimization models may require more time but can provide superior circuits with optimality guarantees.

arXiv:2404.14384Leibniz international proceedings in informaticsJan 1, 20241 citation

Reversible Logic Circuit Synthesis for Quantum Computing via a Gate Pattern-based Optimization Model

Jihye Jung, In-Chan Choi

Quantum computing is the latest computing concept that can substantially reduce the computational burden of some difficult NP problems. Boolean reversible logic is frequently used as a key component in many quantum algorithms. This study proposes an approach based on a mixed integer programming model for reversible circuit synthesis. The proposed optimization model maps a given reversible function into a multiple-control Toffoli (MCT) circuit with minimum quantum costs. Our model exploits the relationship between MCT gate patterns and the operations on qubit states. We also report our experience in computational experiments on the circuit synthesis of reversible benchmark problems.

Journal of Korean Institute of Industrial EngineersAug 25, 20201 citation

Quantum Cost Reduction of Reversible Circuits Using New Toffoli Decomposition Techniques

Md. Belayet Ali, Takashi Hirayama, Katsuhisa Yamanaka +1 more

Quantum cost is the most important criteria to evaluate reversible and quantum circuits. Also the fundamental building blocks of reversible and quantum circuits are Multiple-Control Toffoli (MCT) gates. The synthesis of MCT based reversible circuits are usually conducted into two steps. First, MCT circuits are decomposed into quantum circuits and then they are optimized using various techniques such as template matching, moving rules to reduce the quantum cost of reversible circuits. In this paper, we propose new techniques to decompose the Toffoli gates, in which MCT based circuits are mapped into a corresponding quantum realization. The main improvement is that the resulting quantum realization of MCT based circuits makes significantly better realization than those achieved in the earlier approaches and further reduction is possible using some other optimization techniques. Experimental results show that our new techniques enable to get sub-optimal realization of the MCT based reversible circuits in decomposition stage and quantum cost reduction of the reversible circuits is achieved by using that sub-optimal realization.

International Conference on Computational Science and Computational Intelligence (CSCI)Dec 1, 201518 citations

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 SystemsJun 16, 20251 citation

Computational analysis and comparison of reversible gates for design and test of logic circuits

Hari Mohan Gaur, Ashutosh Kumar Singh, Anand Mohan +1 more

Quantum computing is one of the most significant anticipation towards the accomplishment of interminable consumer demands of small, high speed, and low-power operable electronics devices. As reversible logic circuits have direct applicability to quantum circuits, design and synthesis of these circuits are finding grounds for emerging nano-technologies of quantum computing. Multiple Controlled Toffoli (MCT) and Multiple Controlled Fredkin (MCF) are the fundamental reversible gates that playing key role in this phase of development. A number of special reversible gates have also been presented so far, which were claimed superior for providing certain purposes like logic development and testing. This paper critically analyses a range of these gates to procure an optimal solution for design, synthesis and testing of reversible circuits. The experimentation is facilitated at three subsequent levels, i.e. gates properties, quantum cost and design & testability. MCT and MCF gates are found up to 50% more cost-effective than special gates at design level and 34.4% at testability level. Maximum reversibility depth (MRD) is included as a new measurement parameter for comparison. Special gates exhibit MRD up to 7 which ideally should be 1 for a system to be physically reversible as that of MCT and MCF gates.

International Journal of ElectronicsApr 18, 201916 citations

A multi-commodity network model for optimal quantum reversible circuit synthesis

Jihye Jung, In-Chan Choi

Quantum computing is a newly emerging computing environment that has recently attracted intense research interest in improving the output fidelity, fully utilizing its high computing power from both hardware and software perspectives. In particular, several attempts have been made to reduce the errors in quantum computing algorithms through the efficient synthesis of quantum circuits. In this study, we present an application of an optimization model for synthesizing quantum circuits with minimum implementation costs to lower the error rates by forming a simpler circuit. Our model has a unique structure that combines the arc-subset selection problem with a conventional multi-commodity network flow model. The model targets the circuit synthesis with multiple control Toffoli gates to implement Boolean reversible functions that are often used as a key component in many quantum algorithms. Compared to previous studies, the proposed model has a unifying yet straightforward structure for exploiting the operational characteristics of quantum gates. Our computational experiment shows the potential of the proposed model, obtaining quantum circuits with significantly lower quantum costs compared to prior studies. The proposed model is also applicable to various other fields where reversible logic is utilized, such as low-power computing, fault-tolerant designs, and DNA computing. In addition, our model can be applied to network-based problems, such as logistics distribution and time-stage network problems.

PLoS ONEJun 22, 20213 citations