This paper presents the application of the improved Self-Organizing Migrating Algorithm (iSOMA) to the synthesis and optimization of quantum circuits. We develop a comprehensive method to evolve candidate quantum circuits with minimal cost by integrating iSOMA with circuit evaluators in Qiskit. Experimental evaluation across 100 independent runs demonstrates a 90% success rate in synthesizing Toffoli gates, with an 80% circuit uniqueness rate indicating diverse solution exploration. The algorithm achieves a median cost of 0.000 and determinism = 8/8 for successful runs, confirming its effectiveness for quantum circuit synthesis. This research is important for future 6G networks and beyond, as quantum computing has the potential to be more efficient, especially in the physical layer of the Radio Access Network (RAN), where quantum-supported optimization mechanisms are able to process a large number of tasks faster. The proposed synthesis of Toffoli gates controlled by iSOMA technology contributes to quantum computing by supporting the efficient design of quantum circuits, which is a prerequisite for the deployment of quantum-native functions, such as the Quantum Fourier Transform, in future communications and wireless infrastructures.
This paper presents the application of the improved Self-Organizing Migrating Algorithm (iSOMA) to the synthesis and optimization of quantum circuits. We develop a comprehensive method to evolve candidate quantum circuits with minimal cost by integrating iSOMA with circuit evaluators in Qiskit. Experimental evaluation across 100 independent runs demonstrates a 90% success rate in synthesizing Toffoli gates, with an 80% circuit uniqueness rate indicating diverse solution exploration. The algorithm achieves a median cost of 0.000 and determinism = 8/8 for successful runs, confirming its effectiveness for quantum circuit synthesis. This research is important for future 6G networks and beyond, as quantum computing has the potential to be more efficient, especially in the physical layer of the Radio Access Network (RAN), where quantum-supported optimization mechanisms are able to process a large number of tasks faster. The proposed synthesis of Toffoli gates controlled by iSOMA technology contributes to quantum computing by supporting the efficient design of quantum circuits, which is a prerequisite for the deployment of quantum-native functions, such as the Quantum Fourier Transform, in future communications and wireless infrastructures.
In the present paper, we demonstrate the possibilities of designing quantum computing circuits using a specific swarm intelligence algorithm — iSOMA in the form of three experiments. All simulations are based on a simple sample of a quantum computing circuit from the Qiskit environment, which was used as a comparison circuit with the results of the three experiments already mentioned. In the first experiment, we try to find an arbitrary functional solution using iSOMA with minimal constraints on this circuit’s design. It can be said that in this experiment, iSOMA showed the highest degree of “creativity”. In the second experiment, we focused on whether iSOMA can be used to find a circuit identical to the one designed by a human or equivalent with the positions of the measurement gates fixed. In the last experiment, we highlight iSOMA’s ability to avoid unnecessary qubit usage by adding redundant qubits to a possible circuit and fixing the measurement gates to the last two qubits in the scheme. In all three experiments, we see that iSOMA can find efficient functional and often astonishing solutions — the proposed method applied to a classical circuit founded a new one preserving required properties while saving one ancilla (redundant, useless, non-used)1 qubit. All computations are implemented in the IBM Qiskit2 environment. Although these are relatively simple experiments, the results show that evolutionary algorithms can successfully design more complex quantum circuits.
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.
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.
Quantum algorithms will likely play a key role in future high-performance-computing (HPC) environments. These algorithms are typically expressed as quantum circuits composed of arbitrary gates or as unitary matrices. Executing these on physical devices, however, requires translation to device-compatible circuits, in a process called quantum compilation or circuit synthesis, since these devices support a limited number of native gates. Moreover, these devices typically have specific qubit topologies, which constrain how and where gates can be applied. Consequently, logical qubits in input circuits and unitaries may need to be mapped to and routed between physical qubits. Furthermore, current Noisy Intermediate-Scale Quantum (NISQ) devices present additional constraints. They are vulnerable to errors during gate application and their short decoherence times lead to qubits rapidly succumbing to accumulated noise and possibly corrupting computations. Therefore, circuits synthesized for NISQ devices need to minimize gates and execution times. The problem of synthesizing device-compatible circuits, while optimizing for low gate count and short execution times, can be shown to be computationally intractable using analytical methods. Therefore, interest has grown towards heuristics-based synthesis techniques, which are able to produce approximations of the desired algorithm, while optimizing depth and gate-count. In this work, we investigate using genetic algorithms (GA)—a proven gradient-free optimization technique based on natural selection—for circuit synthesis. In particular, we formulate the quantum synthesis problem as a multi-objective optimization (MOO) problem, with the objectives of minimizing the approximation error, number of multi-qubit gates, and circuit depth. We also employ fuzzy logic for runtime parameter adaptation of GA to enhance search efficiency and solution quality in our proposed method.
In quantum computing, the synthesis of reversible circuits is an important topic. Reversible circuit synthesis is particularly challenging because the complexity grows as the number of bits increases. To date, many reversible circuit synthesis algorithms have been proposed, but most are unable to find the optima within an acceptable time. Because traditional methods only consider partial interests, the resulting cost would be more gates. This paper proposes a novel method, called Bound Oriented Algorithm, which has the ability to find the optimal solution with a high hit rate, one greater than 75% on average. Moreover, with the prediction of the optima by bound, it can reduce excess calculation to further improve efficiency. In addition, a special library containing only Toffoli gates is used, which simplifies algorithm design and is more easily converted to a common library. The experiment result shows that the proposed method performs better than other methods in terms of solution quality and time cost.
This study introduces a new optimization model and a branch-and-cut approach for synthesizing optimal quantum circuits for reversible Boolean functions, which are pivotal components in quantum algorithms. Although heuristic algorithms have been extensively explored for quantum circuit synthesis, research on exact counterparts remains relatively limited. However, the need to design quantum circuits with guaranteed optimality is increasing, especially for improving computational fidelity on noisy intermediate-scale quantum devices. This study presents mathematical optimization as a viable option for optimal synthesis, with the potential to accommodate practical considerations arising in fast-evolving quantum technologies. We set a demonstrative problem to implement reversible Boolean functions using high-level gates known as multiple control Toffoli gates while minimizing a technology-based proxy called quantum cost—the number of low-level gates used to realize each high-level gate. To address this problem, we propose a discrete optimization model based on a multicommodity network and discuss potential future variations at an abstract level to incorporate technical considerations. A customized branch and cut is then developed upon different aspects of our model, including polyhedron integrality, surrogate constraints, and variable prioritization. Our experiments demonstrate the robustness of the proposed approach in finding cost-optimal circuits for all benchmark instances within a two-hour time frame. Furthermore, we present interesting intuitions from these experiments and compare our computational results with relevant studies, highlighting newly discovered circuits with the lowest quantum costs reported in this paper. History: Accepted by Giacomo Nannicini, Area Editor for Quantum Computing. This paper has been accepted for the INFORMS Journal on Computing Special Issue on Quantum Computing. Funding: This research was supported by the Ministry of Science and Information and Communication Technology, South Korea [Grants 2017R1E1A1A0307098814 and 2020R1A4A307986411]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0562 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0562 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .