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.
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.
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.
Quantum computers are reaching the size necessary to begin to perform useful tasks, however they are still limited by noise. One source of this noise is the error rate of the physical gates the processor uses. This means that when compiling high level quantum programs into executable code, it is vitally important to minimise the number of gates in the executable. It is common for physical qubits to be restricted in which other qubits they can interact with. To meet this constraint, swap gates must be inserted to route logical qubits around the processor. Minimising the number of swap gates inserted is known to be an intractable problem for all but small circuits, which means heuristics must be employed. When using heuristics, there is a trade-off between the run-time and the performance. The run-time/performance trade-off was investigated for a variety of functions which determine how important each gate should be based on its position in the circuit, and it was found that while the quadratic decreasing weight function from the literature had the lowest swap cost, the previously unstudied linear decreasing weight function was faster. Averaged over a number of large random circuits, the relative run-time improvement of the linear function compared to the quadratic outweighs the increase in swap cost. To reduce the time taken to find an initial placement, a method of random sampling was proposed. The distribution of the swap costs for random circuits was modelled as a normal distribution to approximate how many random placements need to be inspected in order to find one within a certain distance of the optimum. It was experimentally observed that when taking a random sample of 100 placements, the best placement in the sample was below the predicted 10th percentile of all placements 96.85% of the time, averaged over physical qubit arrays with between 10 and 16 qubits in varying arrangements. A method for an offline estimation of the number of gates that should be considered when choosing the placement and swap gates was proposed. This speeds up the compilation process by ensuring the swap insertion pass only needs to be performed once per circuit, with negligible difference in swap cost. When generating a circuit whose only purpose is to move the logical qubits from one layout to another, the A* algorithm is guaranteed to find the smallest circuit. The time complexity of A* depends on the quality of the heuristic, and this thesis proposes a new heuristic which significantly outperforms the previous heuristic, and in some circumstances is shown to behave optimally. The swap insertion pass of a circuit can be parallelised by splitting it up into subcircuits, however doing so will affect the swap cost. This thesis calculates the relationship between the number of subcircuits and the swap cost, which brings the estimation of the optimal number of subcircuits offline. This speeds up the compilation of a circuit compared to methods which try multiple different numbers of subcircuits in order to choose the best.
In recent years, the semiconductor industry is increasingly considering alternative computation schemes and in this conjuncture quantum computing has come up as a promising alternative due its ability to perform parallel computations (by exploiting superposition) and capacity to solve some of the intractable problems exponentially faster. But one of the criteria in the realization of quantum circuits is that corresponding descriptions demand a so-called nearest neighbour (NN) constraint to be satisfied. One of the possible solutions towards satisfying such constraints is through the insertion of SWAP gates that makes the qubit interactions within a gate adjacent. But since the incorporation of SWAP gates increases the cost of the circuits, strategies should be employed which satisfy the NN constraint while placing SWAP gates so that the cost are reduced. In this work, we propose improved design strategies to realize low-cost NN-compliant quantum circuits. Two approaches are introduced, where the first approach relies on a graph traversal process and uses heuristics in critical decision-making conditions to design a 1D NN-compliant representation. The second approach considers qubit-to-qubit interactions and realizes the circuits in a 2D platform based on some weighted metric. Both the designs are evaluated over a wide spectrum of benchmarks and results have been compared with related works. In those comparisons, we have seen that our approaches perform fairly better than the reported ones.
Motivated by its promising applications e.g. for database search or factorization, significant progress has been made in the development of automated design methods for quantum circuits. But in order to keep up with recent physical developments in this domain, new technological constraints have to be considered. Limited interaction distance between gate qubits is one of the most common of these constraints. This led to the development of several strategies aiming at making a given quantum circuit nearest neighbor-compliant by inserting SWAP gates into the existing structure. Usually these strategies are of heuristic nature. In this work, we present an exact approach that enables nearest neighbor-compliance by inserting a minimal number of SWAP gates. Experiments demonstrate the applicability of the approach which enabled a comparison of results obtained by heuristic methods to the actual optimum.
A New Heuristic for N -Dimensional Nearest Neighbor Realization of a Quantum Circuit
One of the main challenges in quantum computing is to ensure error-free operation of the basic quantum gates. There are various implementation technologies of quantum gates for which the distance between interacting qubits must be kept within a limit for reliable operation. This leads to the so-called requirement of neighborhood arrangements of the interacting qubits, often referred to as nearest neighbor (NN) constraint. This is typically achieved by inserting SWAP gates in the quantum circuits, where a SWAP gate between two qubits exchanges their states. Minimizing the number of SWAP gates to provide NN compliance is an important problem to solve. A number of approaches have been proposed in this regard, based on local and global ordering techniques. In this paper, a generalized approach for combined local and global ordering of qubits have been proposed that is based on an improved heuristic for cost estimation and is also scalable. The approach can be extended to N -dimensional arrangement of qubits, for any arbitrary values of N . Practical constraints, however, restrict the maximum value of N to 3. Extensive experiments on benchmark functions have been carried out to evaluate the performance in terms of SWAP gate requirements. 3-D organization of qubits shows average reductions of 6.7% and 37.4%, respectively, in the number of SWAP gates over 2-D and 1-D organizations. Also compared to the best 2-D and 1-D results reported in the literature, on the average 8.7% and 8.4% reductions, respectively, are observed.
Currently, quantum computing is developing at a high speed because its high parallelism and high computing power bring new solutions to many fields. However, due to chip process technology, it is difficult to achieve full coupling of all qubits on a quantum chip, so when compiling a quantum circuit onto a physical chip, it is necessary to ensure that the two-qubit gate acts on a pair of coupled qubits by inserting swap gates. It will cause great additional cost when a large number of swap gates are inserted, leading to the execution time of quantum circuits longer. In this paper, we designed a way based on the business to insert swap gates BQA(Busy Qubits Avoid). We exploit the imbalance of the number of gates on qubits, trying to hide the overhead of swap gates. At the same time, we also expect swap gates to make as little negative impact on subsequent two-qubit gates as possible. We have designed a heuristic function that can take into account both of these points. Compared with qiskit, the execution time of the circuit optimized by our proposed method is only 0.5 times that of the qiskit compiled circuit. And when the number of two-qubit gates is large, it will achieve higher level than general conditions. This implies higher execution efficiency and lower decoherence error rate.