A Structured Method for Compiling and Optimizing QAOA Circuits in Quantum Computing

The QAOA circuit is a multilevel parameterized quantum-classical hybrid circuit. It has $p$ optimization levels with two parameters in each level. At each level it runs a circuit with the same structure, with the same set of gates except the rotation angles are changed. Each level is associated with a pair of parameters: $\gamma$ and $\beta$ specifying two different rotation angles for the controlled phase gates and the $RX$ gates. Fig. 2 shows the circuit for QAOA-Maxcut for one level. The values of $\gamma$ and $\alpha$ at level $i$ are determined by machine learning on classical computers, typically stochastic gradient descent, and based on the quantum execution of previous $i-1$ levels. It is shown that QAOA has $78\%$ chance of obtaining an optimal solution in the first level [9].

Hamiltonian simulation is another important application of today’s universal quantum computers. Hamiltonian simulation if performed on classically computers is an intractable problem, as its complexity grows exponentially with the problem size. Richard Feyman [11] is the first to propose to use quantum computers to efficiently solve the problem. 2-local Hamiltonian is a type of Hamiltonian that arise in many physical systems [16]. It has the following form:

The interaction between the qubits in the 2-local Hamiltonian simulation can be represented by a graph $G=\{V,E\}$ where $H_{uv}$ is a two-qubit Hamiltonian and $u-v$ represents an edge in E, and $H_{k}$ is a single-qubit Hamiltonian where $k$ represents a node in $V$. With a further trotterization step for Hamiltonian simulation, all 2-qubit terms can commute flexibly [17]. And Trotterization [34, 20, 31] is a common approach for building a quantum circuit on universal quantum computer to asymptotically approximate the time evolution of a Hamiltonian simulation.

Consider n nodes on a rope, labeled from $A_{1}$ to $A_{N}$. There exists a way to move each node around the rope, by swapping them with their neighbors, to form $\lceil N/2\rceil$ different permutations such that each node is adjacent to every other node once and only once.

The idea is shown in Fig. 4. Let the physical positions on the rope be labeled $P_{i}$, $i\in[1,N]$. First, nodes located in position $P_{i}$, where $i$ is odd, are swapped with their neighbor $P_{i+1}$. Then, nodes that are now located in $P_{j}$ where $j$ is even, are swapped with their neighbor $P_{j+1}$. A circuit corresponding to the idea is shown in Fig. 5. We purposely add an additional pair of SWAPs at the end which will result in the qubits being reversed in its final state. This last pair of swaps is not necessary to have all neighbors interact, only for reversing qubits. Note that for odd-number qubits, in the last pair of SWAPs, we omit one for all-to-all connectivity. We do not discuss it due to space limit.

The line architecture solution has been proposed in previous studies [15, 22, 35]. Overall it takes $N-1$ SWAP layers (assuming each SWAP layer consists of parallel SWAPs) to achieve all-to-all connectivity and reversed qubit arrangement on the line. Certain representation lets one computation gate layer be followed by one SWAP layer [15, 35], and another representation lets two computation gate layers be followed by two SWAP layers [22] but will cut one SWAP layer in the last pair. Ours is the latter.

The line architecture has been solved by previous studies as early as 2017 and 2019 [15, 22]. However, the solution for a mutli-dimensional architecture has never been proposed until recently. We are the first to find a solution for the 2xN grid in 2021 [5] (in its Appendix). It is an important building block for the NxM grid solution. We believe Weidenfeller et al.[35] has a similar building block to this. It is also a building block for Google Sycamore and the hexagon architecture whic we are the first to solve.

The idea is simple, as shown in Fig. 6. Note that each row performs a swap pattern that mirrors that for the line architecture, but the swaps alternate between adjacent units. The reason for the alternating swap pattern is as follows: imagine two parallel strings of nodes such that each node has a partner node on the other string (vertically). If the nodes on both strings move in the same direction, then the nodes will always have the same partner. This movement pattern enable both inter-row and intra-row all-to-all interaction. Interestingly, all intra-row interactions happen simultaneously (one parallel layer) at each step, and all inter-row interactions happen simultaneously, which means they can be separated if necessary.

To handle multi-dimensional architecture, our idea is to break down an $N$-dimensional architecture into multiple $(N-1)$-dimensional units. Assuming there are $M$ units, by looking at the connectivity between these units, it is at least a line. If it has more connectivity than a line, that’s okay too.

If a few condition can be met, we can handle the N-dimensional architecture, by just considering every unit as if it is a “qubit" on a line, every unit-exchange as if it is a “SWAP" in a line, and every inter-unit interaction as if it is a “two-qubit gate" between two qubits. Note that the sub-problem of the N-1 dimensional architecture can be handled in the same way. The Maaps algorithm is shown in Algorithm 1.

We formalize the four conditions that must be satisfied to handle any multi-dimensional at each recursive step:

• •

  Define "units" such that the connectivity of the units forms a line.

• •

  Define intra-unit (IA) operations. That is, all-to-all interaction within a unit, in linear time.

• •

  Define inter-unit (IE) operations: Having all-to-all interaction between two neighboring units, in linear time.

• •

  Define unit exchange (UE) operations: Exchanging the locations of two neighboring units in linear time.

With the four above conditions, Maaps can ensure linear time all-to-all interaction. It can be proved rigorously. We sketch the proof. Assuming the $N-1$ dimensional sub-space size is X, and the number of units is $M$. The total size is $M*X$ for the N-dimensional space. Assuming the $(N-1)$-dimensional sub-problem has linear solution O(X). Since the inter-unit interaction happens $2M+O(1)$ times and is linear, and the intra-unit interaction is linear $O(X)$, the complexity is then $O(M*X)$ linear to the size of the entire N-dimensional space.

We demonstrate how Maaps applies to 3 important architectures: 2D lattice, Sycamore, and hexagon. We start with the 2D lattice example as it illustrates the application of Maaps most clearly.

We can handle IBM heavy-hex architectures, by adapting the line solution.

Although there is no line embedding that covers all the nodes in these IBM architectures, we can still find a line embedding that covers the overwhelming majority of them. In Fig. 18, we show an example of one such line embedding, with the gray nodes being off the line embedding.

A very simple approach would be to run two full sets of iterations for the line architecture in a row. It will ensure interaction between all nodes in the line, as well as the interaction between nodes on and off the line. As mentioned previously and proved in prior and our studies [35, 5], a node (whether it is even-numbered or odd numbered) moves towards a certain direction until it hits the border, once it hits the border, it stops for one step, and then changes the direction. In total it travels N steps with one step being stopped. It may not visit all physical locations, but if we let it continue and do another set of full iterations, it will cover each physical location, as shown in Fig. 19. That ensures a node on the line is neighbor to each off-line node. Next we swap the nodes off the line onto the line and then run the line solution again. This guarantees to have all the nodes interact with each other in linear time. The total depth is 6n+O(1) if the input graph is clique. The idea is illustrated in Fig. 18.

When we have a problem graph that is not a clique, we can try to avoid executing gates that do not appear in the problem graph, and then eliminate the cycles that do not include any active gate. We find the minimal cycle from which no more gate execution occurs. That will give us the actual number of cycles to execute a problem graph.

We find that mapping the nodes in the problem graph to the physical qubits in Maaps structure is important since different mapping will result in different depths. We show an example in Fig. 20.

Finding the mapping from the problem graph to the Maaps structure is important, yet challenging. The goal is to minimize the number of continuous cycles that cover active gates. We use a subgraph-isomorphism approach.

Before we discuss this solution, we define a series of pattern graphs $pg\_k$, $k=1...n$ for Maaps pattern. If we gradually build a graph based on which edges in the problem graph have been executed with respect to the computation cycle number, we will have a series of graphs.

Since our problem is to find the minimal number cycles, we can try to fit the problem graph into the each of the $pg\_k$ graphs, from k = 1 to $l$, where $l$ represents the first graph that can cover all edges in the problem graph. If the input problem graph is not a subgraph of $pg_{k}$, we advance to $pg_{k+1}$. This is guaranteed to terminate since any problem is a subgraph of the clique graph. At most we let $k$ be $n$ which is total number of vertices.

Fitting a graph into another graph is a well studied problem, – the subgraph-isomorphism problem. We use a recent subgraph-isomorphism algorithm to implement it [13].

However, the subgraph-isomorphism approach has large overhead. Our experiments show that it takes un-necessarily long time to find a mapping when the qubit number goes above 27 qubits. Moreover, it has to follow Laaps or Maaps exactly, which may not necessarily be the best case.

When handling large problem graphs, we partition a large problem graph into small but dense components and minimize the cut edges [6][14][4]. The hardware coupling graph is also divided into multiple partitions such that each partition is mapped to one partition of the problem graph. We define the degree $D_{i}$ of each partition $G_{i}$ as the number of cut-edges with one node in $G_{i}$. We map the partition $G_{i}$ with highest $D_{i}$ to the center of hardware coupling graph. Then for each mapped graph partition $G_{j}$, we rank their un-mapped neighbours and pick the one with the highest degree to be mapped close to its mapped neighbour. We repeat this until all partitions are mapped.

Within each hardware coupling partition, we use the Maaps method. Different partitions run concurrently. After all partitions are handled separately, we handle the remaining cut edges. At this stage, the sub-graph with remaining edges will be sparse. We can divide them into multiple disjoint connected components and handle each one of them separately, again with Maaps pattern. If it is very sparse, we can use a heuristic approach to move qubits that participate in two-qubit operators close to each other using the Floyd-Warshall algorithm, for one pair at one time.

For small-scale experiments, we use synthetic 2D lattice architecture similar to that in [2] and [16]. We use four grid sizes: $3\times 4$, $4\times 4$, $4\times 5$ and $5\times 5$.

In addition, we also use the interaction graph for 2-local Hamiltonian, including 1-D NNN Ising model, 2-D NNN XY model, and 3-D NNN Heisenberg model (’NNN’ stands for the next nearest neighbouring) [16].

First, we show experiment results for the large scale problem graphs with different densities and qubit counts, on IBM heavy-hex and Google sycamore-like architectures.

On the IBM heavy-hex architectures, our compiler achieves up to 3X improvement in depth over QAIM for random graphs with 0.3 density, and up to 4X improvement for random graphs with 0.5 density; the improvement over Paulihedral is even greater. Similar speedups are seen for the regular graphs. In both cases, the improvement increases with the number of qubits, indicating that our compiler is able to scale better to larger problems compared to the baselines, thanks to the linear bound guaranteed by our approach.

On the Google sycamore-like architectures, we observe the same speedups over QAIM on both random and regular graphs. Our compiler also achieves lower depths for each benchmark on the sycamore-like architecture, compared to on the heavy-hex architecture. This is because for the IBM architectures, we ran the standard Laaps pattern on a line-embedding, whereas for the sycamore-like architecture we used the specialized Maaps pattern. The improvement demonstrates that our 2D Maaps pattern is able to take advantage of the increased connectivity of the non-linear sycamore-like architecture to improve upon the basic linear pattern.

Our compiler performs better than the Paulihedral baseline, and performs on par with the QAIM baseline. While our compiler achieves better gate counts on the IBM heavy-hex architecture, the QAIM compiler achieves better gate counts on the Google sycamore-like architectures the 64 and 128 qubit benchmarks. This is because the Maaps pattern used for sycamore-like architectures uses many swaps to facilitate intra-row interactions, since there are no direct connections between qubits in a given row. Despite this, our compiler still achieves gate counts very close to the QAIM compiler, and even achieves a better gate count on the sycamore-like architecture for 256 qubits. This suggests our compiler is able to scale to larger architectures better than QAIM with respect to gate count.

When calculating ESP on large benchmarks, the large number of gates quickly drives the product down to 0, so we do not directly show the numbers for large benchmarks. However, gate count provides a good indicator of ESP; a smaller gate count indicates higher ESP. Our gate counts are on par with or better than that of QAIM and Paulihedral. Decoherence error is related to depth; our compiled circuits have significantly lower circuit depths, implying a much smaller decoherence error compared to QAIM. Since fidelity combines these two factors of ESP and decoherence error, overall our compiler should achieve a better fidelity.

We ran both random and regular graphs ranging from 10 to 25 qubits on small $N\times M$ 2D architectures. The results are shown in Table 2.

Our compilation achieves better depths than QAIM as well as better gate counts on all small benchmarks tested. Since ESP is correlated to gate count, our compiler also achieves better ESP values for almost all the small benchmarks. Unlike the larger benchmarks, where we used a heuristic based on graph partitioning to find an initial mapping, on smaller benchmarks we can afford to run a subgraph isomorphism algorithm to obtain the optimal mapping for following our Maaps pattern exactly.

In addition, we also compare our approach with the QAOA-OLSQ compiler [32]. The results are in Table. 3. Due to the compilation overhead of QAOA-OLSQ, the comparison was only conducted for up to 15 qubits.

For the most of cases, our approach has better depth than QAOA-OLSQ, except one case 15-4, the 15-qubit density 40% graph, where our depth is 11 and QAOA-OLSQ’s depth is 9. However, in this case, OLSQ takes more than 2 days to run. Our gate count is slightly worse than the QAOA-OLSQ method. But again, QAOA-OLSQ is a (near-)optimal solver and its compilation overhead is of magnitudes larger than ours. All these benchmarks are compiled within 0.3 seconds by our compiler. But it takes hours for QAOA-OLSQ when qubit number is beyond 15 and graph density is beyond 30%.

The results for 2-local Hamiltonian experiments are shown in Table 4. These were run on medium scale 64-qubit Google sycamore-like and IBM ring-life architectures. Our compiler beats the QAIM baseline for all 2-local benchmarks.