The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case

The Quantum Approximation Optimization Algorithm [1, 2] is designed to find approximate solutions to combinatorial search problems, and here we consider its application to finding large independent sets in random graphs. The graphs have $n$ vertices and $dn\over 2$ edges chosen uniformly at random, with $d$, the average degree of each graph, fixed. The quantum algorithm consists of an alternation of $2p$ unitaries, half of which are single-qubit unitaries and the other half only interact qubits that are connected by an edge in the graph. On a bounded-degree graph, with $p$ fixed or growing slowly with $n$, the QAOA does not “see” the whole graph. This means that bits output by the QAOA are uncorrelated at graph distances larger than $2p$. Looking at random graphs of average degree $d$, when $2p$ is less than a multiple of $\log n$ we will show that the power of the algorithm is limited. More precisely if $2p\leq w\log n/\log(d/\ln 2)$ for any $w<1$ and $d$ big enough, the QAOA fails to produce an independent set larger than .854 times the optimal. (The ratio of logs is independent of the base of the log.) If $p$ is large enough that the algorithm “covers” the whole graph we have no indication that the algorithm has limited power.

In the first QAOA paper [1] it was shown that there exists a set of large Max-Cut instances on which the $p=2$ algorithm fails to achieve an approximation ratio of better than 0.756. These are bipartite 3-regular graphs with $o(n)$ squares. Although completely satisfiable, at this shallow depth, the QAOA can not detect if there are large odd length loops which would make it not completely satisfiable and hence the approximation ratio is provably less than $1$. Recently [3] looking at Max-Cut constructed a sequence of $d$-regular bipartite graphs for which the QAOA at depth $p<(1/3~{}\mathrm{log}_{2}n-4)d^{-1}$ fails to find an approximation ratio better than some $d$ dependent constant less than $1$. This result is similar to the one in this paper as it considers $p$ growing logarithmically with $n$. However theirs is a worst case result and ours is for typical instances. Also crucially [3] require that the cost function have a $Z_{2}$ symmetry and that the initial state be an eigenstate of the $Z_{2}$ operator. In our setup these conditions are not needed and for the problem we study they are not met.

Our proof method uses the Overlap Gap Property (OGP) exhibited by the large independent sets of random graphs with bounded average degree established in [4]. Roughly speaking the OGP says that for a given random graph, the intersection of any two large (i.e. nearly optimal) independent sets is either big or small, that is, there is no middle ground. The OGP was established to be an obstruction to a variety of classical algorithms, including local algorithms [4],[5],[6], Markov Chain Monte Carlo (and related) methods, [7],[8],[9], and Approximate Message Passing type algorithms [10]. The application of the OGP as a barrier to quantum algorithms is novel. It depends on the locality of the QAOA: the unitary operators in the algorithm only connect vertices which are connected in the input graph. As a result, because of the bounded average degree, when $p$ is a small multiple of $\log n$, changing a single edge of the graph affects only $o(n)$ qubits of the final state. We will use this to show that outputting a large independent set contradicts the OGP.

It is worth remarking that the OGP is conjectured to not hold for the low energy configurations of the Sherrington-Kirkpatrick model. Assuming that the not hold conjecture is true, Montanari recently [11] constructed a polynomial time Approximate Message Passing algorithm for finding a near ground state configuration.

The QAOA has been applied to the Sherrington Kirkpatrick model at fixed $p$ in the infinite $n$ limit [12]. The associated graph is fully connected (each vertex has degree $n-1$) so the QAOA sees the whole graph at the lowest values of $p$. The techniques of this paper for bounded degree graphs cannot be applied to show any obstacle to the performance of the QAOA on this model.

The computational problem we focus on is Maximum Independent Set or MIS. Given a graph defined as a collection of vertices and edges, an independent set is a subset of the vertices with no graph edge between any two vertices in the set. It is easy to find a small independent set. Finding a big independent set is the challenge. In fact finding the largest independent set in an arbitrary graph is an NP-hard problem. But here we focus on random graphs and are interested in finding big independent sets but not necessarily the biggest. We define $\alpha(G)$ as the independence ratio which is the size of the biggest independent set in $G$ divided by the number of vertices. Given a graph $G$, an algorithm will output an independent set and the quality of the algorithm can be measured by the size of the output divided by $n$ as compared to $\alpha(G)$.

We focus on sparse Erdös-Rényi graphs of $n$ nodes and $m$ edges where $m={dn\over 2}$ with $d$ fixed, that is independent of $n$. In other words $\mathbb{G}(n,{dn\over 2})$ is a graph with ${dn\over 2}$ edges chosen by picking this number of edges uniformly at random from the $n(n-1)/2$ possible edges. The average degree of each graph is $d$. The independence ratio $\alpha(\mathbb{G}(n,{dn\over 2}))$ of this graph denoted by $\alpha_{n,d}$ is a random variable with the following known properties. First [13] there exists an $\alpha_{d}$ such that

Second, while the value of $\alpha_{d}$ for finite $d$ is unknown, the asymptotic value of $\alpha_{d}$ as $d$ increases is known [14]:

We are interested in algorithms that take a graph as input and output a large independent set. The natural question that arises is if a polynomial time algorithm can produce independent sets close to $\alpha_{d}$. A simple greedy algorithm achieves asymptotically half of the optimal value, that is, it constructs an independent set of size $n(\ln d/d)(1+o_{d}(1))$ where $o_{d}(1)$ denotes a function of $d$ converging to $0$ as $d\to\infty$. Finding a polynomial time algorithm that provably goes beyond this would be a major achievement and it mirrors a similar problem in the context of dense Erdös-Rényi graphs, which has been open for more than four decades [15]. Our interest is a quantum algorithm, the QAOA. We will show that if $p$, the depth of the QAOA is less than $\epsilon$ log $n$ with $\epsilon$ a small constant, then the QAOA fails to go as far as $.854\alpha_{d}$ for $d$ large. For larger $p$ our arguments do not apply and we cannot say if the QAOA gets close to $\alpha_{d}$ with $p$ say growing as a large constant times log $n$. (Actually if we let $p$ grow fast enough with $n$ the QAOA will find the optimum [1].)

We start by reviewing the QAOA with the graph problem Maximum Independent Set in mind. It is convenient here to work with bits that are $0,1$ valued. Given a classical cost function $C({\boldsymbol{b}})$ defined on $n$-bit strings ${\boldsymbol{b}}=(b_{1},b_{2},\ldots,b_{n})\in\{0,1\}^{n}$, the QAOA is a quantum algorithm that aims to find a string ${\boldsymbol{b}}$ such that $C({\boldsymbol{b}})$ is close to its absolute maximum. The graph-dependent cost function $C$ can be written as an operator that is diagonal in the computational basis, defined as

We only consider “local” cost functions, that is, those that only have interactions between qubits that are connected on the instance graph. The problem dependent unitary operator depends on $C$ and a single parameter $\gamma$

Note that $U(C,\gamma)$ conjugating a single qubit operator produces an operator that only involves that qubit and those connected to it on the graph.

The operator that induces transitions between strings uses

where $X_{j}$ is the Pauli $X$ operator acting on qubit $j$, and the associated unitary operator depends on a parameter $\beta$

Note that $U(B,\beta)$ conjugating a single qubit rotates that qubit and has no effect on other qubits.

We initialize the system of qubits in a product state such as

or

Using a product state for the initial state is the usual choice for the QAOA and is required for the arguments below.

We alternately apply $p$ layers of $U(C,\gamma)$ and $U(B,\beta)$. Let $\boldsymbol{\gamma}=\gamma_{1},\gamma_{2},\ldots,\gamma_{p}$ and $\boldsymbol{\beta}=\beta_{1},\beta_{2},\ldots,\beta_{p}$. The QAOA circuit prepares the unitary operator

which acting on the initial state gives

The associated QAOA objective function is

By repeatedly measuring the quantum state $\left|\boldsymbol{\gamma},\boldsymbol{\beta}\right\rangle$ in the computational basis, one will find a bit string ${\boldsymbol{b}}$ such that $C({\boldsymbol{b}})$ is near (11) or better. Different strategies have been developed to find optimal $(\boldsymbol{\gamma},\boldsymbol{\beta})$ for any given instance [16, 17]. But here we will show that under certain circumstances no set of parameters $(\boldsymbol{\gamma},\boldsymbol{\beta})$ can achieve a certain level of success so we need not concern ourselves with optimal parameters. So from now on we denote the state produced by the QAOA as $\left|\psi\right\rangle$.

In this paper we are focusing on combinatorial search problem associated with random graphs of bounded average degree $d$, so it it very unlikely that any vertex has degree much larger than $d$. This means that the cost function unitary (4) conjugating say a single qubit operator typically produces an operator acting on no more than roughly $d$ qubits. The “driver” unitary in the form of (6) introduces no spreading at all. We also use for the initial state a product state which has no entanglement. With this form of the QAOA we can establish some general locality properties of the quantum state produced by the quantum circuit. What follows is not restricted to a particular computational problem or to random graphs.

We have discussed the QAOA in general and here we specify it for MIS. For any graph we are looking for a big independent set, that is, a string with a large Hamming weight which corresponds to an independent set. If we choose for the cost function the Hamming weight given by (19) we will easily discover strings with a big Hamming weight but they typically will not be independent sets of the input graph. So we also consider the Independent Set cost function:

where the sum is only over edges in the graph so $C_{\text{IS}}$ is local. We want a big Hamming weight $W$ and $C_{\text{IS}}$ to be as small as possible. So for the objective cost function consider:

When we run the QAOA our goal is to make $C_{\text{obj}}$ big. But the cost function that appears in (4) need not be $C_{\text{obj}}$. We can for starters take the cost function that appears in (4) to be $C_{\text{IS}}$ with the goal of making the quantum expectation of $C_{\text{obj}}$ big. Regardless of what we take to drive this local QAOA, the strings that are output will not be independent sets of the associated graph. However these strings can be pruned to produce independent sets.

Suppose the quantum algorithm outputs a string with a positive value of $C_{\text{obj}}$. By pruning we can produce an independent set of size at least this value. To see this consider the set of graph edges that exist between any of the vertices associated with $1$’s in the output string. Call the number of these edges $N_{E}$. Now for each of these edges pick one of the two associated vertices at random and remove it from the string. This reduces the Hamming weight by at most $N_{E}$ and reduces $C_{\text{IS}}$ by $N_{E}$ so $C_{\text{obj}}$ can not go down. This also shows that the maximum of $C_{\text{obj}}$ is the size of the largest independent set. We call the QAOA augmented by this pruning the QAOA+. Note that the pruning process is done randomly and respects the locality of the underlying graph. When we run the QAOA+ at depth $p$ we mean that the QAOA is run at depth $p-1$ and the pruning is the last layer.

We now show that the shallowest depth version of the QAOA will produce a string with the objective function value being near $1.02n/d$ for large $n$. Here we pick for the starting state a rotation away from the all zeros state so that the initial Hamming weight is not zero. Introduce a parameter $\theta$ and for $\left|s\right\rangle$ take

so the QAOA state is given by the three parameter unitary:

which we call the QAOA with $p=1.5$. Consider the simple case of $\gamma=0$ so the two rotations combine to be one rotation by $\theta+\beta$. This brings the state $\left|0\right\rangle$ to one where each bit $b_{i}$ has expected value $\sin^{2}(\theta+\beta)$. Now the expected value of $C_{\text{obj}}$ is $n[\sin^{2}(\theta+\beta)-(d/2)\sin^{4}(\theta+\beta)]$ whose maximum is $1/2d$ at $\sin(\theta+\beta)=1/\sqrt{d}$. Letting $\gamma$ vary can only improve this.

For arbitrary $\theta$, $\gamma$ and $\beta$ we can evaluate the expectation of $C_{\text{obj}}$ in the state $\left|\psi\right\rangle$ by averaging over instances. It is best to write (23) as

where each $J_{ij}$ is $1$ with probability $d/n$ and $0$ with probability $1-d/n$. Note that this is not exactly the same as the distribution we analyze in the rest of the paper which is a fixed number of edges $nd/2$. But for the purposes of this calculation including edges with probability $d/n$ is more straightforward. In fact we can do the average over $J$ and get the expected value over graphs of the quantum expectation of the objective function

as $n$ times an explicit function of $d$ and the parameters $\theta$, $\gamma$ and $\beta$. For each $d$ we can optimize numerically. For $d=3$ we get $.969n/3$. We see for large $d$ that (27) approaches $1.02n/d$ and the parameters $\theta$ and $\beta$ go down as $\sqrt{d}$. Pulling out a $1/d$ and rescaling $\theta$ and $\beta$ we have a function that has a limit as $d$ goes to infinity. The optimum of this function is $1.02$.

What we have shown is that there is a form of the QAOA that we call the QAOA+ which at its lowest depth finds an independent set whose size is at least a constant times $n/d$. There are simple classical algorithms that can beat this. Our goal here was to show that the lowest depth QAOA+ can be analyzed on random instances and that it is a good starting point for understanding the QAOA at higher depth.

We now describe the Overlap Gap Property which is the key to showing the limitation of the QAOA on random graphs. For random graphs, this property is satisfied by independent sets with size larger than a certain multiplicative factor $\eta^{*}\in(0,1)$ away from optimality. Specifically, this will be done for

For each $\eta\in(0,1)$ and a graph $G$ on $n$ nodes let

where $\mathcal{I}(G)$ is the set of all independent sets. That is, $\mathcal{I}(\eta,G)$ is the set of independent sets in $G$ which are of size at least $\eta$ times the asymptotic optimal. We call these large independent sets $\eta$-optimal. For any two $n$ node graphs $G_{1}$ and $G_{2}$, and for every $0<\tau\leq\eta$, let $\mathcal{O}^{Ab}(\eta,G_{1},G_{2},\tau)$ denote the set of pairs $\sigma_{1},\sigma_{2}$ such that $\sigma_{j}\in\mathcal{I}(\eta,G_{j}),j=1,2$ and

that is, it is the set of pairs of $\eta$-optimal independent sets whose intersection size normalized by the asymptotic size of the largest independent set is above $\tau$. Similarly, let $\mathcal{O}^{Be}(\eta,G_{1},G_{2},\tau)$ denote the set of pairs $\sigma_{1},\sigma_{2}$ such that $\sigma_{j}\in\mathcal{I}(\eta,G_{j}),j=1,2$ and

that is, it is the set of pairs of $\eta$-optimal independent sets whose intersection size normalized by the asymptotic size of the largest independent set is below $\tau$.

Let $G_{0}$ and $G_{m}$ be chosen independently with distribution $\mathbb{G}(n,{dn\over 2})$. We are going to introduce an interpolation between these two graphs. Let $(i^{a}_{1},j^{a}_{1}),\ldots,(i^{a}_{m},j^{a}_{m})$ with $a=0,m$ be the corresponding sets of $m$ edges of the two graphs. For every $t=0,1,2,\ldots,m$ consider an interpolating random graph $G_{t}$ with edges

$G_{t}$ uses the first $m-t$ edges from $G_{0}$ and the remaining $t$ edges from $G_{m}$. For each fixed $t$, the graph $G_{t}$ is distributed as $\mathbb{G}(n,m)$, modulo the potential repetitions of edges. With high probability, the total number of edge repetitions is $O(1)$ with respect to $n$ so they can be ignored.

The theorem makes two claims. First it says that across all pairs $G_{t_{1}},G_{t_{2}}$ of graphs in the interpolating sequence, every $\eta$-optimal independent set $\sigma_{1}$ in $G_{t_{1}}$ and every $\eta$-optimal independent set $\sigma_{2}$ in $G_{t_{2}}$ have normalized intersection either at most $\tau_{1}$ or at least $\tau_{2}$, except for an exponentially small probability. There is essentially no middle ground of pairs whose normalized intersection size is between $\tau_{1}$ and $\tau_{2}$. This is the Overlap Gap Property. The second says, for two independent random graphs sampled from $\mathbb{G}(n,{dn\over 2})$ all corresponding pairs of large independent sets have normalized intersection at most $\tau_{1}$. For a proof and further discussion see [4].