Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Proceedings of the AAAI Conference on Artificial Intelligence

An Innovative Genetic Algorithm for the Quantum Circuit Compilation Problem

Riccardo Rasconi, Angelo Oddi

Published Jul 17, 2019• 34 citations
Publisher

Abstract

Quantum Computing represents the next big step towards speed boost in computation, which promises major breakthroughs in several disciplines including Artificial Intelligence. This paper investigates the performance of a genetic algorithm to optimize the realization (compilation) of nearest-neighbor compliant quantum circuits. Currrent technological limitations (e.g., decoherence effect) impose that the overall duration (makespan) of the quantum circuit realization be minimized, and therefore the makespanminimization problem of compiling quantum algorithms on present or future quantum machines is dragging increasing attention in the AI community. In our genetic algorithm, a solution is built utilizing a novel chromosome encoding where each gene controls the iterative selection of a quantum gate to be inserted in the solution, over a lexicographic double-key ranking returned by a heuristic function recently published in the literature.Our algorithm has been tested on a set of quantum circuit benchmark instances of increasing sizes available from the recent literature. We demonstrate that our genetic approach obtains very encouraging results that outperform the solutions obtained in previous research against the same benchmark, succeeding in significantly improving the makespan values for a great number of instances.

DOI
10.1609/aaai.v33i01.33017707

Related papers

Quantum circuit compilation by genetic algorithm for quantum approximate optimization algorithm applied to MaxCut problem

Lis Arufe, Miguel Ángel González, Angelo Oddi +2 more

The Quantum Circuit Compilation Problem (QCCP) is challenging to the Artificial Intelligence community. It was already tackled with temporal planning, constraint programming, greedy heuristics and other techniques. In this paper, QCCP is formulated as a scheduling problem and solved by a genetic algorithm. We focus on QCCP for Quantum Approximation Optimization Algorithms (QAOA) applied to the MaxCut problem and consider Noisy Intermediate Scale Quantum (NISQ) hardware architectures. Based on the fact that these algorithms apply a set of basic quantum operations repeatedly over a number of rounds, we propose a genetic algorithm approach, termed Decomposition Based Genetic Algorithm (DBGA), that in each round extends the partial solutions obtained for the previous ones. DBGA is compared to the state of the art across a set of conventional instances. The results of the experimental study provided interesting insight in the problem structure and showed that DBGA is quite competitive with the state of the art. In particular, DBGA outperformed the best current method on the largest instances and provided new best solutions to most of them.

Swarm and Evolutionary Computation•Jan 7, 2022•23 citations

New coding scheme to compile circuits for Quantum Approximate Optimization Algorithm by genetic evolution

Lis Arufe, Riccardo Rasconi, Angelo Oddi +2 more

Compiling quantum circuits on target quantum hardware architectures is one of the key issues in the development of quantum algorithms, and the related problem is known as the Quantum Circuit Compilation Problem (QCCP). This paper presents a genetic algorithm for solving QCCP instances for Quantum Approximate Optimization Algorithms (QAOA). In particular, such instances represent quantum circuits for the resolution of both MaxCut and Graph-Coloring combinatorial problems. The presented algorithm represents a significant improvement over an already existing genetic algorithm called Decomposition Based Genetic Algorithm (DBGA), and is characterized by a completely new coding scheme that allows to reduce the number of SWAP gates introduced in the decoding step, consequently reducing the circuit depth. After providing a description of the problem, this paper presents the newly produced genetic algorithm (termed DBGA-X) in detail, especially focusing on the new coding/decoding scheme. Subsequently, a set of results will be presented that demonstrate the superior performance of the new method compared with the results obtained from recent literature against the same benchmark. In addition, new benchmarks characterized by larger quantum architectures and by a higher number of compilation passes are proposed in this paper, to the aim of testing the scalability of the proposed method in more realistic scenarios.

Applied Soft Computing•May 25, 2023•9 citations

Solving quantum circuit compilation problem variants through genetic algorithms

Lis Arufe, Riccardo Rasconi, Angelo Oddi +2 more

Abstract The gate-based model is one of the leading quantum computing paradigms for representing quantum circuits. Within this paradigm, a quantum algorithm is expressed in terms of a set of quantum gates that are executed on the quantum hardware over time, subject to a number of constraints whose satisfaction must be guaranteed before running the circuit, to allow for feasible execution. The need to guarantee the previous feasibility condition gives rise to the Quantum Circuit Compilation Problem (QCCP). The QCCP has been demonstrated to be NP-Complete, and can be considered as a Planning and Scheduling problem. In this paper, we consider quantum compilation instances deriving from the general Quantum Approximation Optimization Algorithm (QAOA), applied to the MaxCut problem, devised to be executed on Noisy Intermediate Scale Quantum (NISQ) hardware architectures. More specifically, in addition to the basic QCCP version, we also tackle other variants of the same problem such as the QCCP-X (QCCP with crosstalk constraints), the QCCP-V (QCCP with variable qubit state initialization), as well as the QCCP-VX that includes both previous variants. All problem variants are solved using genetic algorithms. We perform an experimental study across a conventional set of instances taken from the literature, and show that the proposed genetic algorithm, termed $$GA_{VX}$$ G A VX , outperforms previous approaches in the literature.

Natural Computing•Aug 17, 2023•2 citations

Analyzing Heuristic-based Randomized Search Strategies for the Quantum Circuit Compilation Problem

Angelo Oddi, Riccardo Rasconi

In this work we investigate the performance of greedy randomised search (GRS) techniques to the problem of compiling quantum circuits to emerging quantum hardware. Quantum computing (QC) represents the next big step towards power consumption minimisation and CPU speed boost in the future of computing machines. Quantum computing uses quantum gates that manipulate multi-valued bits (qubits). A quantum circuit is composed of a number of qubits and a series of quantum gates that operate on those qubits, and whose execution realises a specific quantum algorithm. Current quantum computing technologies limit the qubit interaction distance allowing the execution of gates between adjacent qubits only. This has opened the way to the exploration of possible techniques aimed at guaranteeing nearest-neighbor (NN) compliance in any quantum circuit through the addition of a number of so-called swap gates between adjacent qubits. In addition, technological limitations (decoherence effect) impose that the overall duration (makespan) of the quantum circuit realization be minimized. One core contribution of the paper is the definition of two lexicographic ranking functions for quantum gate selection, using two keys: one key acts as a global closure metric to minimise the solution makespan; the second one is a local metric, which favours the mutual approach of the closest qstates pairs. We present a GRS procedure that synthesises NN-compliant quantum circuits realizations, starting from a set of benchmark instances of different size belonging to the Quantum Approximate Optimization Algorithm (QAOA) class tailored for the MaxCut problem. We propose a comparison between the presented meta-heuristics and the approaches used in the recent literature against the same benchmarks, both from the CPU efficiency and from the solution quality standpoint. In particular, we compare our approach against a reference benchmark initially proposed and subsequently expanded in [1] by considering: (i) variable qubit state initialisation and (ii) crosstalk constraints that further restrict parallel gate execution.

Fundamenta Informaticae•Sep 28, 2020•0 citations

EAQGA: A Quantum-Enhanced Genetic Algorithm with Novel Entanglement-Aware Crossovers

Mohammad Kashfi Haghighi, Matthieu Fortin-Deschênes, Christophe Père +1 more

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.

arXiv:2504.17923•Apr 24, 2025•0 citations

Genetic algorithm for qubits initialisation in noisy intermediate-scale quantum machines

Zakaria Abdelmoiz Dahi, Francisco Chicano, Gabriel Luque +1 more

Discrete-variable gate-model quantum machines are promising quantum systems considering their wide applicability. Being in their noisy-intermediate-scale era, they allow executing only circuits of limited complexity and fitting the machines' features. Thus, such systems implement a key and unavoidable tailoring process to produce the most possible compact and device-compliant circuit. The qubits' initialisation is a primary and complex step that can ease/jeopardise the tailoring process and restrict/extend the machine's computational capacities. Ultimately, this bottleneck can be responsible of making quantum leaps like quantum supremacy. As a step towards the former, this work investigates how evolutionary algorithms can enhance the qubits' initialisation by tackling it as a single-objective problem using a genetic algorithm. The experiments used instances representing 19 real IBM quantum machines with 7 to 65 qubits and 9 different qubit topologies. Also, 76 GHZ circuits of sizes 7-65 qubits and 25%-100% of entanglement were created and studied. Extensive standard and statistical comparisons have been made against the IBM qubit initialiser that is currently used in real quantum machines. Results showed that the proposal outperforms IBM in 64 instances and is similar to it in 10 ones, with an average circuit-compression gain up to 46%.

Genetic and Evolutionary Computation Conference (GECCO)•Jul 8, 2022•5 citations
Quantum Computing represents the next big step towards speed boost in computation, which promises major breakthroughs in several disciplines including Artificial Intelligence. This paper investigates the performance of a genetic algorithm to optimize the realization (compilation) of nearest-neighbor compliant quantum circuits. Currrent technological limitations (e.g., decoherence effect) impose that the overall duration (makespan) of the quantum circuit realization be minimized, and therefore the makespanminimization problem of compiling quantum algorithms on present or future quantum machines is dragging increasing attention in the AI community. In our genetic algorithm, a solution is built utilizing a novel chromosome encoding where each gene controls the iterative selection of a quantum gate to be inserted in the solution, over a lexicographic double-key ranking returned by a heuristic function recently published in the literature.Our algorithm has been tested on a set of quantum circuit benchmark instances of increasing sizes available from the recent literature. We demonstrate that our genetic approach obtains very encouraging results that outperform the solutions obtained in previous research against the same benchmark, succeeding in significantly improving the makespan values for a great number of instances.
The Quantum Circuit Compilation Problem (QCCP) is challenging to the Artificial Intelligence community. It was already tackled with temporal planning, constraint programming, greedy heuristics and other techniques. In this paper, QCCP is formulated as a scheduling problem and solved by a genetic algorithm. We focus on QCCP for Quantum Approximation Optimization Algorithms (QAOA) applied to the MaxCut problem and consider Noisy Intermediate Scale Quantum (NISQ) hardware architectures. Based on the fact that these algorithms apply a set of basic quantum operations repeatedly over a number of rounds, we propose a genetic algorithm approach, termed Decomposition Based Genetic Algorithm (DBGA), that in each round extends the partial solutions obtained for the previous ones. DBGA is compared to the state of the art across a set of conventional instances. The results of the experimental study provided interesting insight in the problem structure and showed that DBGA is quite competitive with the state of the art. In particular, DBGA outperformed the best current method on the largest instances and provided new best solutions to most of them.
Compiling quantum circuits on target quantum hardware architectures is one of the key issues in the development of quantum algorithms, and the related problem is known as the Quantum Circuit Compilation Problem (QCCP). This paper presents a genetic algorithm for solving QCCP instances for Quantum Approximate Optimization Algorithms (QAOA). In particular, such instances represent quantum circuits for the resolution of both MaxCut and Graph-Coloring combinatorial problems. The presented algorithm represents a significant improvement over an already existing genetic algorithm called Decomposition Based Genetic Algorithm (DBGA), and is characterized by a completely new coding scheme that allows to reduce the number of SWAP gates introduced in the decoding step, consequently reducing the circuit depth. After providing a description of the problem, this paper presents the newly produced genetic algorithm (termed DBGA-X) in detail, especially focusing on the new coding/decoding scheme. Subsequently, a set of results will be presented that demonstrate the superior performance of the new method compared with the results obtained from recent literature against the same benchmark. In addition, new benchmarks characterized by larger quantum architectures and by a higher number of compilation passes are proposed in this paper, to the aim of testing the scalability of the proposed method in more realistic scenarios.
Abstract The gate-based model is one of the leading quantum computing paradigms for representing quantum circuits. Within this paradigm, a quantum algorithm is expressed in terms of a set of quantum gates that are executed on the quantum hardware over time, subject to a number of constraints whose satisfaction must be guaranteed before running the circuit, to allow for feasible execution. The need to guarantee the previous feasibility condition gives rise to the Quantum Circuit Compilation Problem (QCCP). The QCCP has been demonstrated to be NP-Complete, and can be considered as a Planning and Scheduling problem. In this paper, we consider quantum compilation instances deriving from the general Quantum Approximation Optimization Algorithm (QAOA), applied to the MaxCut problem, devised to be executed on Noisy Intermediate Scale Quantum (NISQ) hardware architectures. More specifically, in addition to the basic QCCP version, we also tackle other variants of the same problem such as the QCCP-X (QCCP with crosstalk constraints), the QCCP-V (QCCP with variable qubit state initialization), as well as the QCCP-VX that includes both previous variants. All problem variants are solved using genetic algorithms. We perform an experimental study across a conventional set of instances taken from the literature, and show that the proposed genetic algorithm, termed GAVXGA_{VX}GAVX​ G A VX , outperforms previous approaches in the literature.
In this work we investigate the performance of greedy randomised search (GRS) techniques to the problem of compiling quantum circuits to emerging quantum hardware. Quantum computing (QC) represents the next big step towards power consumption minimisation and CPU speed boost in the future of computing machines. Quantum computing uses quantum gates that manipulate multi-valued bits (qubits). A quantum circuit is composed of a number of qubits and a series of quantum gates that operate on those qubits, and whose execution realises a specific quantum algorithm. Current quantum computing technologies limit the qubit interaction distance allowing the execution of gates between adjacent qubits only. This has opened the way to the exploration of possible techniques aimed at guaranteeing nearest-neighbor (NN) compliance in any quantum circuit through the addition of a number of so-called swap gates between adjacent qubits. In addition, technological limitations (decoherence effect) impose that the overall duration (makespan) of the quantum circuit realization be minimized. One core contribution of the paper is the definition of two lexicographic ranking functions for quantum gate selection, using two keys: one key acts as a global closure metric to minimise the solution makespan; the second one is a local metric, which favours the mutual approach of the closest qstates pairs. We present a GRS procedure that synthesises NN-compliant quantum circuits realizations, starting from a set of benchmark instances of different size belonging to the Quantum Approximate Optimization Algorithm (QAOA) class tailored for the MaxCut problem. We propose a comparison between the presented meta-heuristics and the approaches used in the recent literature against the same benchmarks, both from the CPU efficiency and from the solution quality standpoint. In particular, we compare our approach against a reference benchmark initially proposed and subsequently expanded in [1] by considering: (i) variable qubit state initialisation and (ii) crosstalk constraints that further restrict parallel gate execution.
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.
Discrete-variable gate-model quantum machines are promising quantum systems considering their wide applicability. Being in their noisy-intermediate-scale era, they allow executing only circuits of limited complexity and fitting the machines' features. Thus, such systems implement a key and unavoidable tailoring process to produce the most possible compact and device-compliant circuit. The qubits' initialisation is a primary and complex step that can ease/jeopardise the tailoring process and restrict/extend the machine's computational capacities. Ultimately, this bottleneck can be responsible of making quantum leaps like quantum supremacy. As a step towards the former, this work investigates how evolutionary algorithms can enhance the qubits' initialisation by tackling it as a single-objective problem using a genetic algorithm. The experiments used instances representing 19 real IBM quantum machines with 7 to 65 qubits and 9 different qubit topologies. Also, 76 GHZ circuits of sizes 7-65 qubits and 25%-100% of entanglement were created and studied. Extensive standard and statistical comparisons have been made against the IBM qubit initialiser that is currently used in real quantum machines. Results showed that the proposal outperforms IBM in 64 instances and is similar to it in 10 ones, with an average circuit-compression gain up to 46%.