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.
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.
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.
Genetic algorithms are highly effective optimization techniques for many computationally challenging problems, including combinatorial optimization tasks like portfolio optimization. Quantum computing has also shown potential in addressing these complex challenges. Combining these approaches, quantum genetic algorithms leverage the principles of superposition and entanglement to enhance the performance of classical genetic algorithms. In this work, we propose a novel quantum genetic algorithm introducing an innovative crossover strategy to generate quantum circuits from a binary solution. We incorporate a heuristic method to encode entanglement patterns from parent solutions into circuits for the next generation. Our algorithm advances quantum genetic algorithms by utilizing a limited number of entanglements, enabling efficient exploration of optimal solutions without significantly increasing circuit depth, making it suitable for near-term applications. We test this approach on a portfolio optimization problem using an IBM 127 qubits Eagle processor (ibm_quebec) and simulators. Compared to state-of-the-art algorithms, our results show that the proposed method improves fitness values by 33.6% over classical genetic algorithm and 37.2% over quantum-inspired genetic algorithm, using the same iteration counts and population sizes with real quantum hardware employing 100 qubits. These findings highlight the potential of current quantum computers to address real-world utility-scale combinatorial optimization problems.
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. ---
In the literature, there are many Quantum Inspired Evolutionary Algorithms (QIEA) that proved good performance and results when applied to solving a myriad of problems. However, the real quantum representation increases precision for numerical optimisation problems and reduces the memory storage need, alternatively to the binary representation. On the other hand, evolutionary algorithms' performance mainly depends on the crossover and mutation operators, reaching equilibrium between the explorative and exploitative features of evolutionary algorithms. This paper proposes new quantum genetic operators for real quantum representation, instead of the 1/5 rule present in AEIQ-R, to improve the performance of the quantum genetic algorithm with real representation. Three crossover and two mutation operators are proposed and tested to optimise four functions with different dimensions. Friedman's test indicated a significant difference between the combinations, and that combination composed of quantum arithmetic crossover and quantum creep mutation have the best performance.