Generating target graph couplings for the quantum approximate optimization algorithm from native quantum hardware couplings

We present methods for constructing any target coupling graph using limited global controls in an Ising-like quantum spin system. Our approach is motivated by implementing the quantum approximate optimization algorithm (QAOA) on trapped-ion quantum hardware to find approximate solutions to MaxCut. We present a mathematical description of the problem and provide approximately optimal algorithmic constructions that generate arbitrary unweighted coupling graphs with $n$ nodes in $O\left(n\right)$ global entangling operations and weighted graphs with $m$ edges in $O\left(m\right)$ operations. These upper bounds are not tight in general, and we formulate a mixed-integer program to solve the graph coupling problem to optimality. We perform numeric experiments on small graphs with $n\le 8$ and show that optimal sequences, which use fewer operations, can be found using mixed-integer programs. Noisy simulations of MaxCut QAOA show that our implementation is less susceptible to noise than the standard gate-based compilation.

Figure 1

An example construction for the union-of-stars algorithm for an unweighted graph (Theorem t11). The original graph (left) can be decomposed into two star graphs, represented in blue and green, respectively. Since each star is a complete bipartite graph, it can be constructed using Lemma t9, with the sets $V_1,V_2,V_3$ specified for each of the stars. The construction of each star takes four Ising operations, but since one operation is common across the stars, we end up with a total of seven operations for this construction by combining the common one using Lemma t8.

Figure 2

A different star decomposition for the example in Fig. 1. In Theorem t11, choosing a different ordering for the vertices can result in a decomposition into a larger number of stars and therefore in a larger number of Ising operations. The ordering for vertices in this case is $u_0,w_0,w_1,w_2,u_2$, while the ordering for Fig. 1 is $u_1,u_2$. Notice that the maximum degree for any star is 2 in this decomposition, which could possibly be useful under different error assumptions.

Figure 3

A comparison of the union-of-stars construction to the optimal sequence found with the brute force MIP for random unweighted graphs with seven vertices and measured by the (a) $L_0$ norm and (b) $L_1$ norm defined in Sec. 3b. The upper bound proved with the union of stars is $3n-2$ for the $L_0$ norm (total number of Ising operations) and $n-1$ for $L_1$ (sum of the absolute magnitude of strengths).

Figure 4

A comparison of union of stars against optimality for random weighted graphs on seven vertices for the (a) $L_0$ and (b) $L_1$ norms. The upper bound now depends on the expected number of edges as described in the main text. That some constructions exceed this expectation reflects the nonzero probability of having more edges than $\overline{m}$.

Figure 5

Largest graph coupling number observed in the optimal generation of unweighted graphs of up to eight vertices compared to the $3n-2$ upper bound from the union-of-stars construction.

Figure 6

Decomposition of the $Z_i{Z}_j$ terms into (a) cnotgates and (b) ion native $XX$ interactions. One-qubit rotations are analogous to the definition given before Eq. (6) and $R_{XX}\left(\chi \right)=exp\{-i(\chi /2){\sigma }_1^x{\sigma }_2^x\}$.

Figure 7

Approximation ratio when simulating the noisy $p=1$ QAOA for two different compilation methods. “cnot” compilation refers to compiling in terms of two-qubit $\mathit{XX}$ (locally equivalent to cnot gates) gates, while “GMS” refers to compiling following the union-of-stars method and building in terms of global Mølmer-Sørenson interactions. Major and minor noise sources are detailed in the text and have a fixed relationship as indicated on the horizontal axis. Each subfigure shows an inset displaying the example unweighted graph that is considered for both compilation schemes.

Figure 8

QAOA circuit for $p=1$ using global MS interactions which build an (a) four-node star graph and (b) four-node complete graph missing the edge connecting nodes 0 and 1.