Quantum computing leverages the unique properties of qubits and quantum parallelism to solve problems intractable for classical systems, offering unparalleled computational potential. However, optimization of quantum circuits remains critical, especially for noisy intermediate-scale quantum (NISQ) devices with limited qubits and high error rates. Genetic algorithms (GAs) provide a promising approach for efficient quantum circuit synthesis by automating optimization tasks. This work examines the impact of various mutation strategies within a GA framework for quantum circuit synthesis. By analyzing how different mutations transform circuits, it identifies strategies that enhance efficiency and performance. Experiments utilized a fitness function emphasizing fidelity, while accounting for circuit depth and T-operations, to optimize circuits with four to six qubits. Our analysis revealed that, while the "swap, addition" strategy achieved the highest fidelity scores, it consistently increased circuit depth. In contrast, combining "swap, addition, delete" strategies offers a more balanced approach, delivering near-optimal results while also having the potential of reducing circuit depth.
Quantum computing leverages the unique properties of qubits and quantum parallelism to solve problems intractable for classical systems, offering unparalleled computational potential. However, optimization of quantum circuits remains critical, especially for noisy intermediate-scale quantum (NISQ) devices with limited qubits and high error rates. Genetic algorithms (GAs) provide a promising approach for efficient quantum circuit synthesis by automating optimization tasks. This work examines the impact of various mutation strategies within a GA framework for quantum circuit synthesis. By analyzing how different mutations transform circuits, it identifies strategies that enhance efficiency and performance. Experiments utilized a fitness function emphasizing fidelity, while accounting for circuit depth and T-operations, to optimize circuits with four to six qubits. Our analysis revealed that, while the "swap, addition" strategy achieved the highest fidelity scores, it consistently increased circuit depth. In contrast, combining "swap, addition, delete" strategies offers a more balanced approach, delivering near-optimal results while also having the potential of reducing circuit depth.
Quantum computing emerges as a promising direction for high-performance computing in the post-Moore era. Leveraging quantum mechanical properties, quantum devices can theoretically provide significant speedup over classical computers in certain problem domains. Quantum algorithms are typically expressed as quantum circuits composed of quantum gates, or as unitary matrices. Execution of quantum algorithms on physical devices requires translation to machine-compatible circuits -- a process referred to as quantum compilation or synthesis. Quantum synthesis is a challenging problem. Physical quantum devices support a limited number of native basis gates, requiring synthesized circuits to be composed of only these gates. Moreover, quantum 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 on the device. Current Noisy Intermediate-Scale Quantum (NISQ) devices present additional constraints, through their gate errors and high susceptibility to noise. NISQ devices are vulnerable to errors during gate application and their short decoherence times leads to qubits rapidly succumbing to accumulated noise and possibly corrupting computations. Therefore, circuits synthesized for NISQ devices need to have a low number of gates to reduce gate errors, and short execution times to avoid qubit decoherence. The problem of synthesizing device-compatible quantum 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 compilation techniques, which are able to produce approximations of the desired algorithm to a required degree of precision. In this work, we investigate using Genetic Algorithms (GAs) -- 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 of our proposed quantum synthesis method.
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.
Abstract Designing compact and efficient quantum circuits that are compatible with Noisy Intermediate-Scale Quantum (NISQ) hardware remains a central challenge in quantum computing. Most existing optimization approaches rely on fidelity-based fitness functions that require computing the full unitary matrix of the circuit. However, this quickly becomes computationally intractable beyond 10–12 qubits due to the exponential memory and time complexity O(22n) . In this work, we propose a scalable multi-objective genetic algorithm for quantum circuit optimization tailored to NISQ devices. Although evolutionary algorithms have demonstrated strong potential for circuit synthesis, current methods generally depend on full-unitary fidelity evaluation, which severely limits scalability. To address this bottleneck, we introduce two complementary strategies: (1) an independent block-based evaluation using graph partitioning, and (2) an overlapping sliding-window decomposition approach. Both strategies reduce computational complexity from O(22n) to O(22k) , where k≪n , making it possible to optimize circuits with more than 20 qubits in practice. Our methods are integrated into the NSGA-II multi-objective framework, enabling simultaneous optimization of fidelity, circuit depth, and gate cost, while maintaining structural compatibility with NISQ hardware–without requiring full-unitary simulation. Experimental results on benchmark circuits demonstrate high fidelity (above 0.94 for small circuits up to 8 qubits, above 0.85 for medium-scale circuits of 10–16 qubits, and above 0.80 for large-scale circuits up to 32 qubits), up to 45% reduction in circuit depth, and a 10× speedup compared to exact evaluation at 14 qubits.
This paper explores the application of genetic algorithms (GAs) to optimize quantum circuits. The core claim is that GA can effectively improve the efficiency and accuracy of quantum computation by strategically modifying the topology and control parameters of quantum circuits. The proposed mechanism treats a quantum circuit as a genetic individual, leveraging the principles of genetic algorithms – including crossover, mutation, and selection – to iteratively enhance circuit performance. This approach represents a novel method for quantum circuit optimization, offering a potentially robust and adaptable solution compared to traditional optimization techniques. We present a framework for implementing this approach, focusing on the algorithmic steps and considerations for successful application. The exploration will cover the challenges and potential benefits of integrating evolutionary algorithms with the unique characteristics of quantum computation. ---
Abstract Most of the existing qubit mapping algorithms are deterministic, resulting in a lack of diversity in the generated quantum circuit mappings, which makes it difficult to strike a balance between quality and diversity, and prevents them from being flexibly adapted to different quantum computing tasks. To solve this problem, this paper proposes the Genetic Algorithm-based Quantum Circuit Mapping (GAQCM) framework, which is based on the idea of genetic algorithm, evaluates the quality of mapping by the fitness function, and continuously improves the mapping scheme through several iterations. The GAQCM framework is designed to be flexible, providing a variety of choices, crossover operations and several unique mutation methods are designed to improve the performance of the algorithm. The framework also introduces a neighbourhood gate-based initialisation strategy to improve the algorithm efficiency and convergence speed. Experimental results show that the GAQCM framework reduces the number of SWAP gates by an average of 44.6% and 62.0%, and reduces the hardware gate overhead by 13.8% and 14.9% in the t|ket > and Qiskit compilers, respectively, compared to 2QAN. The framework allows users to customise the fitness function and parameter settings according to their specific needs, and is suitable for a variety of quantum computing tasks.
We investigate the role of crossover in Quantum Circuit Synthesis (QCS) with Genetic Algorithms (GAs) using the commonly used list encoding. We start with a preliminary investigation into the level and development of epistasis in QCS. Then, we perform three experiments comparing the performance of a GA with one-point crossover against a search strategy that only uses mutation. For the gate and qubit counts we tested, the GA with crossover performed on par with the mutation-only variant on one of the tested syntheses targets and underperformed on the remaining two. This motivates further research on the suitability of standard crossover operators for QCS and prompts the need to develop more efficient, problem-specific encodings and operators.