The compilation of quantum circuits on a given quantum architecture is one of the critical issues when developing quantum algorithms. The related problem is known as the Quantum Circuit Compilation Problem (QCCP). It is known that the current quantum chip technology (Noisy Intermediate-Scale Quantum) is afected by noise that can be originated by diferent sources and significantly limits the circuit's usability. Generally, one important source of noise is the onset of decoherence during the quantum circuit's execution. Decoherence can be described as the dificulty of a quantum state to hold its superposition in time; therefore, quantum circuits should be characterized by a limited depth (i.e., makespan) in order to terminate their execution before qubits start to decohere. The other important source of noise is due to the presence of quantum binary gates (e.g., CNOTs); it is in fact known that the noise produced by binary gates is an order of magnitude greater than the noise produced by unary gates. Hence, trying to minimize the number of the circuit's binary gates can also positively afect the stability of the circuit. In this work, we analyze how a multiobjective approach can be useful to reduce the circuit's noise thus improving its stability, focusing on the minimization of both the circuit's makespan and the number of swap gates that are synthesized as a product of the compilation process, as every swap gate is a binary gate composed of a sequence of three CNOT gates. In particular, we tackle instances of the Quantum Approximate Optimization Algorithm (QAOA) for the resolution of the MaxCut problem, and provide some preliminary results combining an existing genetic algorithm with two well-known multiobjective approaches.
3 4 (a) N = 4 2 7 (b) N = 8 1 6 9 3 14 2 3 4 5 6 11 18 22 29 33 40 (e) N = 72 (f) N = 127
In the QAOA model, the same set of gates must be applied over a number of rounds to obtain
a near optimal solution to the MaxCut problem. Figure 2 shows a MaxCut instance and one
solution, considering a single round, compiled on the smallest of the circuits in Figure 1. In this
work we assume that each qstate is initially located in qubit . The distribution of quantum
gates on qubits is subject to two constraints: (
The study performed in this work is based on the currently available gate-based quantum chip technology, known as Noisy Intermediate-Scale Quantum (NISQ) [4, 5]. NISQ chips are basically quantum processors containing up to about 1000 qubits (https://www.ibm.com/quantum/blog/quantum-roadmap-2033) that are neither suficiently advanced for fault-tolerance, nor large enough to prove quantum supremacy over classical computing. Moreover, these processors are susceptible to a phenomenon known as quantum decoherence, as well as sensitive to their environment (i.e., they are noisy). Decoherence can be described as the dificulty of a quantum state to hold its superposition in time; in other words, for a quantum circuit to return reliable results, the computation should terminate before the proq1 q3 q4 1 2 3 4 n1 n2 n3 n4 cessor’s qubits start to decohere. Hence, quantum circuits should be characterized by a limited depth (i.e., makespan) in that the shallower the circuit, the sooner the quantum computation ends, and the smaller the decoherence efect sufered by the circuit. Another source of noise is caused by the presence of quantum binary gates (e.g., CNOTs); it is in fact known that the noise produced by binary gates is an order of magnitude greater than the noise produced by unary gates. Hence, trying to minimize the number of the circuit’s binary gates also represents an important issue to positively afect the stability of the circuit.
However, minimizing the circuit’s depth and minimizing the number of binary gates are generally mutually conflicting objectives [ 6]; this is also illustrated in Figure 3, where we show two diferent solutions for an instance of an 8-qubit hardware where we must execute a single round of the following 8 − gates: (2,3), (3,8), (4,5), (4,7), (4,8), (5,7), (6,8), (7,8). These solutions are shown by means of Gantt charts, representing the operations on each qstate over time. In this work it is assumed that − gates take 3 time units on continuous edges and 4 time units on dashed edges, that the swap gates require 2 time units on all edges, and the mix gates require 1 time unit.
The solution depicted in Figure 3(a) has depth 18 and requires 8 swap gates, whereas the solution depicted in Figure 3(b) has depth 25 but only requires 5 swap gates. For this same instance it also exists a solution with depth 19 and 6 swap gates (not pictured), which can be considered a good compromise between both objectives, hence motivating a multiobjective approach.
In this work, we start from the Decomposition Based Genetic Algorithm (DBGA-X) proposed in [7]. In each iteration ∈ {1, . . . , } it solves the subproblem defined by rounds 1, . . . , , starting from solutions to the subproblem defined by rounds 1, . . . , − 1 and inserting the − and mix gates corresponding to round , also inserting swap gates when necessary.
We keep the coding and decoding schemas and genetic operators. In particular, chromosomes for round are triplets (− 1, ℎ1, ℎ2) where − 1 is a solution graph for subproblem 1, . . . , − 1, ℎ1 is a permutation of the set of − gates of round , and ℎ2 indicates how to insert swaps before inserting the corresponding − gate of ℎ1. In the decoding step, when q8 p-s(q6,q8) q7 (sqw6,aqp7) p-s(q4,q7) qq56 ((ssqqww36,,aaqqpp57)) (psqw2-s,aq(p5q)6,q8)(sqw1,aqp5) q4 p-s(q4,q7)
swap ttseaQqqq123 (q3,q5) (sqw2,aqp5) inserting a gate − (, ), a set of swap gates are introduced to move concurrently towards and towards through one of the shortest paths on the hardware between the qubits where they are currently located. ℎ2 codifies in which edge of that shortest path the − gate will be inserted. We also keep using the extension of the partial mapping crossover (PMX) operator and a mutation operator that randomly modifies the ℎ2 part of the chromosome. We refer the interested reader to [7] for further details of the method.
In order to extend DBGA-X to deal with two objectives at once, we consider two evolution strategies borrowed from well-known multiobjective approaches: • The first is the Nondominated Sorting Genetic Algorithm II (NSGA-II) [ 8], which difers from a standard genetic algorithm mainly in the replacement step, in which we choose individuals based on the concepts of dominance and crowding distance. We enhance the diversity of the method by penalizing solutions with duplicated values of both objective functions before the replacement step. • The second is the Multiobjective Evolutionary Algorithm based on Decomposition (MOEA/D) [9], which divides the whole problem into a set of single-objective problems, each defined by a scalarization function based on diferent weights. A neighborhood relation between problems is defined so that they can help each other during the evolution.
The benchmark instances are taken from [7], and the solving methods are implemented in C++ and run in a Intel Core i5-7400 CPU at 3.00GHz with 16 GB RAM. As for parameter setting, in both multiobjective versions we choose a population size of 1000 chromosomes (so in the case of MOEA/D we solve 1000 single-objective subproblems), a stop condition of 100 generations without adding a new non-dominated solution to the Pareto front, a 100% crossover probability and a 0.05% mutation probability for each position of each chromosome.
Specifically for MOEA/D, we have tried Tchebychef and weighted sum scalarization functions and the first one seems to perform better experimentally. Additionally, we use a neighborhood size of 100 for each solution (i.e. the 100 solutions from the “closest” single-objective problems). In the crossover step all solutions are mated, choosing as the other parent a solution from the neighborhood with 95% probability, and any solution with 5% probability.
Figure 4 shows some preliminary results of the multiobjective versions of DBGA-X in three instances with 40, 72 and 127 qubits. We show the Pareto fronts obtained by the NSGA-II version and the MOEA/D version. For comparison reasons, we also run single-objective versions of DBGA-X to either minimize makespan (i.e. circuit depth) or to minimize the number of swap gates.
Each method is run 10 times, and in the figures we plot the best result from all runs in the case of single-objective, and the Pareto front with the best hypervolume [10] from all runs in the case of multiobjective. The average running time of the multiobjective methods is reasonable, of about 30 seconds for instances with 40 qubits, 2 minutes for 72 qubits and 8 minutes for 127 qubits.
It can be seen that both multiobjective versions are able to reach approximate Pareto sets with a variety of solutions that obtain a good compromise between both objectives. In these instances, the Pareto fronts obtained by the NSGA-II version clearly outperform those of the MOEA/D version, particularly on the larger instances. It is also interesting that neither NSGA-II or MOEA/D are able to reach the best single-objective solutions, although this was the expected behavior, as multiobjective approaches are eficient at obtaining good compromise solutions, but usually less eficient at the extremes of the Pareto front.
This paper is a first step in expanding our previous research in the QCCP by considering the minimization of several objectives at once, in particular the circuit depth and the number of added swap gates. Minimizing both objectives is useful to deal with the decoherence problem, however we illustrated its conflicting nature and so motivated a multiobjective approach. We combined a previous genetic algorithm from the literature with two well-known multiobjective approaches and we have seen that a NSGA-II strategy obtains a good variety of solutions, and better Pareto fronts than a MOEA/D strategy.
For future work, we first plan to perform an exhaustive experimental analysis using many instances of several sizes and also considering additional rounds of QAOA (as the experiments shown in this paper consider a single round), in order to obtain proper conclusions. However, from the preliminary results it seems that the spread of solutions of the obtained Pareto fronts can be improved, so we plan to devise some enhancements to the multiobjective procedures. Applying QAOA to diferent problems, as the Minimum Vertex Cover Problem or the Graph Coloring Problem is also an interesting avenue for future work.
This research has been supported by the Spanish Government under research projects PID2019106263RB-I00 and PID2022-141746OB-I00. A. Oddi and R. Rasconi were supported by the ESA Contract No. 4000112300/14/D/MRP “Mars Express Data Planning Tool MEXAR2 Maintenance”. computing, in: 2016 IEEE International Conference on Rebooting Computing (ICRC), 2016, pp. 1–6. [4] J. Preskill, Quantum Computing in the NISQ era and beyond, Quantum 2 (2018) 79. [5] M. Brooks, Beyond quantum supremacy: the hunt for useful quantum computers, Nature 574 (2019) 19–21. [6] G. Li, Y. Ding, Y. Xie, Tackling the qubit mapping problem for nisq-era quantum devices, in: Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS ’19, Association for Computing Machinery, New York, NY, USA, 2019, pp. 1001–1014. [7] L. Arufe, R. Rasconi, A. Oddi, R. Varela, M. A. González, New coding scheme to compile circuits for quantum approximate optimization algorithm by genetic evolution, Applied Soft Computing 144 (2023) 110456. [8] K. Deb, A. Pratap, S. Agarwal, T. Meyarivan, A fast and elitist multiobjective genetic algorithm: Nsga-ii, IEEE Transactions on Evolutionary Computation 6 (2002) 182–197. [9] Q. Zhang, H. Li, Moea/d: A multiobjective evolutionary algorithm based on decomposition,
IEEE Transactions on Evolutionary Computation 11 (2007) 712–731. [10] E. Zitzler, L. Thiele, Multiobjective optimization using evolutionary algorithms — a comparative case study, in: Parallel Problem Solving from Nature — PPSN V Proceedings, Springer Berlin Heidelberg, 1998, pp. 292–301.