The Overlap Gap Property Limits Limit Swapping in the QAOA

The main result of this work is to show that the OGP exists as a limitation for Max-q-XORSAT on a random regular hypergraph with sufficiently large degree. This is done via the following theorem

The proof is done via contradiction. First, we show that we can trim the Erdös–Rényi hypergraph of average degree λ to a regular hypertree removing at most an 𝒪(1/λ^logλ)-fraction of edges. Then, one can form a λ-regular hypergraph from the hypertree. Assuming an algorithm, that is limited by the OGP, is able to find a near-optimal solution on the regular hypergraph leads to a contradiction since such an algorithm is unable to find near-optimal solution on Erdös–Rényi hypergraph. Thus, the OGP also acts as a barrier to optimization for random regular graph.

This limitation to logarithmic depth local algorithms leads us to re-derive a recently discovered theorem and improve upon its results:

There are several immediate corollaries of this result for the QAOA. The first of which was noted in [6] as a side-note.

The above corollary is a result of optimizing the QAOA under limit swapping of the algorithm run time p and the problem size n. This therefore results in the following corollary:

Here, we standardize the notation we use to denote a hypergraph. A hypergraph G = (V, E) has |V| = n vertices, and |E| = m edges. A graph is q-uniform if every hyperedge connects to exactly q vertices. A graph is d-regular if every vertex has degree d. Conventionally, an instance of the Erdös–Rényi–(Gilbert) q-uniform hypergraph G=GERq(n,p)\mathop {\lim }\limits_{n \to \infty } \mathop {\lim }\limits_{p \to \log n} {1 \over {|E|}}\langle \gamma ,{\bf{\beta }}|H_{XOR}^q|\gamma ,\beta \rangle = {1 \over 2} + v_\infty ^{[q]}(D,\gamma ,{\bf{\beta }})\sqrt {{q \over {2D}}} , is a random graph with n vertices where each hyperedge is added with probability p. The original Erdös–Rényi q-uniform hypergraph G=GERq(n,m)\mathop {\lim }\limits_{n \to \infty } \mathop {\lim }\limits_{p \to \log n} {1 \over {|E|}}\langle \gamma ,{\bf{\beta }}|H_{XOR}^q|\gamma ,\beta \rangle = {1 \over 2} + v_\infty ^{[q]}(D,\gamma ,{\bf{\beta }})\sqrt {{q \over {2D}}} , is chosen randomly from the set of hypergraphs with n vertices and m hyperedges. The former is now more frequently used. The two types of Erdös–Rényi graphs are similar to each other when (nq)p=m\left( \matrix{ n \cr q \cr} \right)p = m. In fact, it has been shown that the two types of random graphs are asymptotically equivalent under certain conditions [12].

Another type of random hypergraph of interest is the d-regular q-uniform hypergraph G = ℝ^q(n, d), where we implicitly assume that nd = qx for some integer x. Unlike Erdös–Rényi graphs that can be generated randomly, there is no easy unbiased way to generate such graphs, though one such method is known as the configuration model introduced by Bollobás [13].

In this paper, we focus on the mean field spin glass model and the related dilute spin glass model. For the mean field model, the main goal, roughly speaking, is to find the ground state energy of a spin glass Hamiltonian. A widely studied model is the Sherrington–Kirkpatrick (SK) model [14]. More generally, an Ising mean field q-spin model is given by the following 2Hq(z)=q!2n(q−1)∑j<k<⋯<qJjk…qzjzk…zq,{H_q}(z) = \sqrt {{{q!} \over {2{n^{(q - 1)}}}}} \sum\limits_{j < k < \cdots < q} {{J_{jk \ldots q}}} {z_j}{z_k} \ldots {z_q}, where the couplings are randomly chosen over a normal distribution and z_i ∈ {–1,1}.

The ground state energy of the mean-field spin glass can be computed exactly [15], which we denote as the Parisi constant 3Πq=limn→∞maxz∈{−1,1}nHq(z)n.{\Pi _q} = \mathop {\lim }\limits_{n \to \infty } \mathop {\max }\limits_{z \in {{\{ - 1,1\} }^n}} {{{H_q}(z)} \over n}.

The dilute spin glass model is also known as the XOR-satisfiability (XORSAT) problem. Specifically, given a q-uniform hypergraph G = (V, E) where E ⊂ V^q, and a given signed weight J_i1,…,iq ∈ {–1,+1}, Max-q-XORSAT is the problem of maximizing the following cost function 4HXORq(z)=∑(i1,…,iq)∈E12(1+Ji1i2…iqzi1zi2…ziq).H_{XOR}^q(z) = \sum\limits_{\left( {{i_1}, \ldots ,{i_q}} \right) \in E} {{1 \over 2}} \left( {1 + {J_{{i_1}{i_2} \ldots {i_q}}}{z_{{i_1}}}{z_{{i_2}}} \ldots {z_{{i_q}}}} \right).

In terms of the hypergraph, z_ij refers to the vertices and J_i1i2…iq refers to the hyperedge.

We say that an instance of the problem is satisfied if there is an assignment of values to the bit-string z which satisfies all the clauses (i.e. HXORq(z)=|E|H_{XOR}^q(z) = |E|). Otherwise, we say it is unsatisfiable. Suppose we fix d > q sufficiently large so that we are in the unsatisfiable regime. The maximum number of satisfiable equations in an instance of random XORSAT for both GERq(n,p)H_{XOR}^q(z) = |E|, and ℝ^q(n, d) has been found [16] to be 51|E|maxzHXORq(z)=12+Πqq2d+O(1/d).{1 \over {|E|}}\mathop {\max }\limits_z H_{XOR}^q(z) = {1 \over 2} + {\Pi _q}\sqrt {{q \over {2d}}} + {\cal O}(1/\sqrt d ).

One major obstacle to finding optimal solutions for COPs is known as the Overlap Gap Property (OGP). The term was introduced in [17], though the concept was already used by various authors [18,19].

For the definition of the OGP, one can informally think that for certain choices of disorder J, there is a gap in the set of possible pairwise overlaps of near-optimal solution. Informally, for every two near-optimal solution z¹, z², it is the case that the distance between them is either extremely small, or extremely large. Formally, we define the OGP for a single instance as the following:

Definition 1 (Overlap Gap Property [20]). For a general maximization problem with random input J, the OGP holds if there exists some ϵ > 0, with 0 ≥ μ₁ ≤ μ₂ such that for every z¹, z² that is an ϵ-optimal solution 6HJ(zi)≥maxz∈2nHJ(z)−ϵ,{H_J}\left( {{z^i}} \right) \ge \mathop {\max }\limits_{z \in {2^n}} {H_J}(z) - , it holds that the (normalized) overlap between them is either less than μ₁ or greater than μ₂ 7| R1,2 |∈[ 0,μ1 ]∪[ μ2,1 ],\left| {{R_{1,2}}} \right| \in \left[ {0,{\mu _1}} \right] \cup \left[ {{\mu _2},1} \right], where 8R1,2=1n∑i=1nzi1zi2.{R_{1,2}} = {1 \over n}\sum\limits_{i = 1}^n {z_i^1} z_i^2.

Rather than using the overlap, it is often easier to visualize sets of solutions as clusters using the Hamming distance between two states via the relation 9H1,2n=12| 1−R1,2 |∈[0,a]∪[b,1],{R_{1,2}} = {1 \over n}\sum\limits_{i = 1}^n {z_i^1} z_i^2. where H_1,2 is the Hamming distance between states z¹ and z² and 0 < a < b < 1.

The first interval is trivial as we can simply choose the overlap z¹ with itself. It is the existence of the second overlap, or rather the non-existence of overlap in the interval (a, b), that is difficult to prove.

A general version of it is known as the ensemble-OGP introduced in [21] or coupled-OGP as used in [22]. This version is required to prove limitations of local algorithm for technical reasons and requires an interpolation scheme between two different instances of Erdös–Rényi graphs. For spin glasses, a branching OGP has been developed that makes use of the ultrametric structure in the Parisi solution [23].

Informally speaking, the OGP limits the performance of algorithms by first showing that the set of near-optimal solutions exhibits a strong clustering property. That is, with high probability, a gap exists in their overlaps or equivalently, a gap in the hamming distance between near-optimal solutions. Then, one proceeds to show that if an algorithm is able to find arbitrary near-optimal solution, the algorithm outputs a solution that is in the region forbidden by the OGP. In the context of the QAOA, one typically uses the concentration of measure to prove the limitation of the QAOA at shallow depth [8,22]. We refer the reader to the review papers by Garmanik [3,20] for details on how the OGP limits the performance of algorithms.

The QAOA is a local quantum algorithm [22] designed to find approximate solutions to combinatorial optimization problems [4]. The goal is to find a bit string z ∈ {–1, +1}ⁿ that maximizes the cost function C(z). Given a classical cost function C, we can define a corresponding quantum operator C^{R_{1,2}} = {1 \over n}\sum\limits_{i = 1}^n {z_i^1} z_i^2. that is diagonal in the computational basis, C^|z〉=C(z)|z〉{R_{1,2}} = {1 \over n}\sum\limits_{i = 1}^n {z_i^1} z_i^2.. In addition, define the operator B^=∑jnX^j{R_{1,2}} = {1 \over n}\sum\limits_{i = 1}^n {z_i^1} z_i^2. where X^j{{\hat X}_j} is the Pauli X operator acting on qubit j. Given a set of parameters γ = (γ₁, …, γ_p) ∈ ℝ^p and β = (β₁, …, β_p) ∈ ℝ^p, the QAOA prepares the initial state as |s〉=|+〉n=2−n/2∑z|z〉|s\rangle = | + {\rangle ^n} = {2^{ - n/2}}\sum\nolimits_z {|z\rangle } and applies p layers of alternating unitary operators e−iγkC^|s\rangle = | + {\rangle ^n} = {2^{ - n/2}}\sum\nolimits_z {|z\rangle } and e−iβkB^{e^{ - i{\beta _k}\hat B}} to prepare the state 10|γ,β〉=e−iβpB^e−iγpC^…e−iβ1B^e−iγ1C^|s〉.|\gamma ,\beta \rangle = {e^{ - i{\beta _p}\hat B}}{e^{ - i{\gamma _p}\hat C}} \ldots {e^{ - i{\beta _1}\hat B}}{e^{ - i{\gamma _1}\hat C}}|s\rangle .

For a given cost function C, the corresponding QAOA objective function is the expectation value 〈γ,β|C^|γ,β〉\langle \gamma ,\beta |\hat C|\gamma ,\beta \rangle . The goal in the QAOA at depth p is to find the 2p optimal parameters (γ*, β*) that maximize the expectation value 〈γ, β|C|γ, β〉 (i.e. arg max_{γ, β} 〈γ, β|C|γ, β〉). Heuristics strategies to optimize 〈γ, β|C|γ, β〉 with respect to (γ, β) using a good initial guess have been proposed in [24]. Recently, when applying the QAOA to large girth regular graphs with girth greater than 2p + 1, the graph appears as a regular tree, and the authors of [6] developed an algorithm to find the optimal parameters which we call tree-parameters.

The first result of the QAOA on spin glasses can be found in [5] where the authors applied the QAOA on the Sherrington–Kirkpatrick (SK) model and found an algorithm to evaluate the expectation value in the infinite limit after averaging over the disorder J. More generally, for a q-spin glass with cost function 11Hq(z)=∑j<k<⋯<qJjk…qzjzk…zq,{H_q}(z) = \sum\limits_{j < k < \cdots < q} {{J_{jk \ldots q}}} {z_j}{z_k} \ldots {z_q}, it was shown in [8] that the following theorem holds

In [6], the authors evaluated the performance of the QAOA for Max-q-XORSAT on large-girth (D + 1)-regular graphs. By restricting to graphs that are regular and have girth (also known as the shortest Berge-cycle) greater than 2p + 1, the subgraph explored by the QAOA at depth p will appear as a regular tree. Since the optimal cut fraction is of the form 1/2+O(1/D)V_p^{(q)}({\bf{\gamma }},{\bf{\beta }}) in a typical random graph as in (5), we have 131|E|〈γ,β|HXORq|γ,β〉=12+vp[q](D,γ,β)q2D+O(1/D).{1 \over {|E|}}\langle {\bf{\gamma }},{\bf{\beta }}|H_{{\rm{XOR}}}^q|{\bf{\gamma }},{\bf{\beta }}\rangle = {1 \over 2} + v_p^{[q]}(D,{\bf{\gamma }},{\bf{\beta }})\sqrt {{q \over {2D}}} + {\cal O}(1/\sqrt D ).

Let 14vp[q](γ,β)=limD→∞vp[q](D,γ,β),v_p^{[q]}(\gamma ,\beta ) = \mathop {\lim }\limits_{D \to \infty } v_p^{[q]}(D,\gamma ,\beta ), then, we have the following theorem

Furthermore, the authors also made the following conjecture based on promizing numerical evidence,

Conjecture 5 (Conjecture of [6]). Optimizing the QAOA using tree-parameters found in [6], the Parisi value for the Sherrington–Kirkpatrick model can be reached: 15limp→∞vp[2](γ,β)=Π2.v_p^{[q]}(\gamma ,\beta ) = \mathop {\lim }\limits_{D \to \infty } v_p^{[q]}(D,\gamma ,\beta ),

While we are unable to prove or disprove the conjecture, we prove later that the generalized Parisi value Πq is not obtainable if the OGP is present.

One point to note is that in [7], it has been shown that at low depth p, if a problem exhibits the OGP, then the locality of the QAOA makes it such that it is prevented from getting close to the optimal value if it does not see the whole graph. Specifically, the following theorem is proven.

The authors of [6] noted that assuming the OGP also holds for regular hypergraphs, then a similar argument can be used to show that the QAOA’s performance as measured by the algorithm in Theorem 4 does not converge to the Parisi value Πq for even q ≥ 4. This is because the large girth assumption implies that the graph has at least D^p vertices so p is always less than ϵ log n in this limit. For the Max-q-XORSAT, the subgraph explored at constant p has q[(q – 1)^pDp + … + (q – 1)D + 1] vertices. This lays the foundation of Theorem 10 later.

The first equivalence between spin glass and MaxCUT for the QAOA was shown in [6], where the performance of the QAOA at depth p on the SK model as n → ∞ to is equal to the performance of the QAOA at depth p on MaxCUT problems on large-girth (D + 1)-regular graphs when D → ∞. In the follow-up work of [8], they generalize this result to show that the QAOA’s performance for the q-spin model is equivalent to that for Max-q-XORSAT on any large girth D-regular hypergraphs in the limit D → ∞.

The equivalence of performance of the QAOA on dense and sparse graph is also shown to hold in the case of Erdös–Rényi graph.

Proof. The proof is as follows: first, we need to show that for some λ ∈ ℤ⁺, a λ-regular q-uniform hypertree can be embedded into an Erdös–Rényi hypergraph of sufficiently high average connectivity. Then, we show that a λ-regular q-uniform hypergraph can be generated from said hypertree. Finally, we show that algorithm 𝒜 must also fail to find solutions arbitrarily close to the optimal solution in a λ-regular q-uniform hypergraph as doing so would result in a contradiction.

We note that a COP instance with m chosen edges can be converted into a regular instance changing only oλ(1/λ){o_\lambda }(1/\sqrt \lambda )¹ edges. This reduction has been used several times before as in [16,26] and recently in [27]. We follow the proof of [27] but simplify one of the lemmas using GERq(n,p)G_{ER}^q(n,p) later to avoid the combinatoric arguments needed when considering GERq(n,m)G_{ER}^q(n,m), and extend the argument from constant depth l to ϵ log n.

Here, we show that an Erdös–Rényi hypergraph can be converted into a hypertree by changing only o(1/λ)o(1/\sqrt \lambda ) edges. Given GERq(n,m)_{ER}^q(n,m) with average degree γ, define λ′=⌈ λ+λlogλ ⌉{\lambda ^\prime } = \left\lceil {\lambda \; + \;\sqrt \lambda \log \lambda } \right\rceil . Let d_i be the degree of vertex V_i. Modify the graph as follows:

• Remove edges until d_i < γ′ for all vertices.

• Add edges to all vertices until d_i = λ′ where each vertex is chosen with probability proportional to λ′ – d_i. In order to prove this, we will need the following lemmas.

Proof. Note that the distribution of edges in an Erdös–Rényi follows a binomial distribution B(m, 1/n). For each vertex v_i, the number of edges removed is either 0 or d_i – λ′ so Δ_i := max (λ′,0). The first moment of Δ_i is bounded by 23E[ Δi ]=∑d>λ′P(Δi=k)(k−λ′)=∑d>λ′P(Δi≥k)≤∫λ′∞P(di≥x)dx.\left[ {{\Delta _i}} \right] = \sum\limits_{d > {\lambda ^\prime }} P \left( {{\Delta _i} = k} \right)\left( {k - {\lambda ^\prime }} \right) = \sum\limits_{d > {\lambda ^\prime }} P \left( {{\Delta _i} \ge k} \right) \le \int_{{\lambda ^\prime }}^\infty P \left( {{d_i} \ge x} \right)dx.

Where we used the fact that the expectation value of a random variable equals the cumulative function in the second equality.

The second moment can also be bounded as 24E[ Δi2 ]=∑d>λ′P(Δi=k)(k−λ′)2≤∫λ′∞P(di≥x)2(x−λ′)dx.\left[ {\Delta _i^2} \right] = \sum\limits_{d > {\lambda ^\prime }} P \left( {{\Delta _i} = k} \right){\left( {k - {\lambda ^\prime }} \right)^2} \le \int_{{\lambda ^\prime }}^\infty P \left( {{d_i} \ge x} \right)2\left( {x - {\lambda ^\prime }} \right)dx.

Using Chernoff’s bound for the binomial distribution, we have 25P(di≥x)≤2exp{ −(x−λ′)23λ′ }.P\left( {{d_i} \ge x} \right) \le 2\exp \left\{ { - {{{{\left( {x - {\lambda ^\prime }} \right)}^2}} \over {3{\lambda ^\prime }}}} \right\}.

Applying Eq. (25) to the second moment bound, we have 26∫λ′∞2(x−λ′)exp{ −(x−λ′)23λ′ }dx=3λ′exp{ −(λ′−λ)23λ }=Oλ(λexp{ −c(logλ)2 }).\matrix{ {\int_{{\lambda ^\prime }}^\infty 2 \left( {x - {\lambda ^\prime }} \right)\exp \left\{ { - {{{{\left( {x - {\lambda ^\prime }} \right)}^2}} \over {3{\lambda ^\prime }}}} \right\}dx} \hfill & { = 3{\lambda ^\prime }\exp \left\{ { - {{{{\left( {{\lambda ^\prime } - \lambda } \right)}^2}} \over {3\lambda }}} \right\}} \hfill \cr {} \hfill & { = {{\cal O}_\lambda }\left( {\lambda \exp \left\{ { - c{{(\log \lambda )}^2}} \right\}} \right).} \hfill \cr } for some c > 0. Thus, both the first and second moments are bounded by 𝒪_λ(d^{–c′ log d}) for some constant c′ > 0.

For the total number of edges removed Δ, we note that by a union bound, Δ≤Δ˜\Delta \le \tilde \Delta , where Δ˜:=∑iΔi\tilde \Delta : = \sum\nolimits_i {{\Delta _i}} . Furthermore, we have E[Δ˜]=nE[ Δi ][\tilde \Delta ] = n\left[ {{\Delta _i}} \right]. Unless Δ_i and Δ_j share the same edge, they are independent, so 27Var(Δ˜)≤nE[ Δi2 ]+2∑i,jCov(Δi,Δj).{\mathop{\rm Var}\nolimits} (\tilde \Delta ) \le n\left[ {\Delta _i^2} \right] + 2\sum\limits_{i,j} {{\mathop{\rm Cov}\nolimits} } \left( {{\Delta _i},{\Delta _j}} \right).

Since the degree of each vertex is not independent (i.e. follows a multinomial distribution), the covariance term is negative. Therefore, as n → ∞, Δ is at most n𝒪_λ(d^{–c log d}) for some c > 0 with high probability.

The process of removing edges does not create cycles (i.e. destroy tree-like property). However, we need to ensure that the graph was initially tree-like and remains tree-like after adding edges. Rather than working with G=GERq(n,m)G\;{\rm{ = }}\;_{ER}^q(n,m), we will work with G=GERq(n,p)G\;{\rm{ = }}\;_{ER}^q(n,p) for the next lemma and use the fact that a graph containing a k-cycle is a monotone increasing property and that for any monotone increasing graph property 𝒫, P(∈GERq(n,m))≤C·P(∈GERq(n,p))P\left( {{\cal P} \in _{ER}^q(n,m)} \right) \le C\cdotP\left( {{\cal P} \in _{ER}^q(n,p)} \right) for some constant 𝒞 [28].

Proof. Let p=c+logn+λloglogn(q−1n)~O(logn/nq−1)p = {{c + \log n + \lambda \log \log n} \over {\left( {\mathop {q - 1}\limits^n } \right)}}\~{\cal O}\left( {\log n/{n^{q - 1}}} \right) for some constant c > 1, and k, ∈ ℕ. Let X be the number of k-cycles. Leaving k in the big-𝒪 notation to account for k as a function of n later, we have 28EX=(nk)pk~O((q!)kn2klogknnkqk!).X = \left( \matrix{ n \cr k \cr} \right){p^k}\~{\cal O}\left( {{{(q!)}^k}{{{n^{2k}}{{\log }^k}n} \over {{n^{kq}}k!}}} \right).

By Markov’s inequality, we thus have 29P(X>0)≤O((q!)klogknnk(q−2)k!),P(X > 0) \le {\cal O}\left( {{{{{(q!)}^k}{{\log }^k}n} \over {{n^{k(q - 2)}}k!}}} \right), which vanishes in the limit n → ∞ implying that the number of constant k-cycles is o(1). The same argument implies that cycles of size log n and (log n)^logn also vanish.

Now we show that the l-local neighbourhood of an arbitrary vertex has at most o(1) k-cycles. In the limit n → ∞, the degree of each vertex follows a Poisson distribution with mean λ. Let Υ denote the degree of an arbitrary vertex. The probability that any vertex v has degree at most log n is given by 30P(Y≤logn)=1−P(Υ>logn).P(Y \le \log n) = 1 - P(Y > \log n).

From the Chernoff bound for the Poisson distribution, we have that 31P(Υ>x)≤e−λ(eλ)xxx~O(cx/xx)=o(1),P(Y > x) \le {e^{ - \lambda }}{{{{(e\lambda )}^x}} \over {{x^x}}}\~{\cal O}\left( {{c^x}/{x^x}} \right) = o(1), for some constant c so all vertices have degree at most log n with high probability.

Thus, the l-local neighbourhood has at most (log n)^ϵlogn vertices. Repeating the same argument for the number of k-cycles shows that only o(1) of the l-local neighbourhood will contain a cycle.

Proof. Right after removing edges, every vertex has at most degree λ′ so given some constant λ and l ≤ ϵ log n, the l-local neighbourhood B_G(v, l) is upper-bound by λ′^ϵlogn and is a hypertree. Then, we have to add on average n(λ log λ) ~ Θ(n) edges but since B_G(v, l) is of order 𝒪(λ′^ϵlogn), the probability that an added hyperedge contains at least two vertices in B_G(v, l) is 𝒪(λ′^ϵlogn/n).

Choose ϵ < 1/log λ′. As a result, adding clauses results in o(1) fraction of l-local neighbourhood forming a cycle.

Now, we show that a λ-regular, q-uniform hypergraph is locally also a hypertree.

Proof. As we are interested in the large n limit, we first show that for fixed p, the dominant term in the probability that a cycle is formed in the large n limit is given by (q−1)pλpn−1−⋯−λp−1(q−1)p−1{{{{(q - 1)}^p}{\lambda ^p}} \over {n - 1 - \cdots - {\lambda ^{p - 1}}{{(q - 1)}^{p - 1}}}}. Consider p = 1 and choose any hyperedge. Then, the first (q – 1) vertices form no cycle with probability 1. The next hyperedge added will form a cycle with probability q−1n−1{{q - 1} \over {n - 1}}. This process repeats until we reach the last hyperedge for the root vertex (i.e. the λ hyperedge) where the probability of forming a cycle is given by (λ−1)(q−1)n−1{{(\lambda - 1)(q - 1)} \over {n - 1}} so the dominant term is of the form λ(q−1)n−1{{\lambda (q - 1)} \over {n - 1}}. In other words, the term that contributes the highest probability of forming a cycle at depth p is when we are filling up the last hyperedge. For p = 2 and higher, choosing the first hyperedge already has a non-trivial probability of forming a cycle as we might add a vertex at the p−1 level. Focusing on p = 2, this means that adding the first (q−1) vertices has a probability of λ(q−1)−1n−1{{\lambda (q - 1) - 1} \over {n - 1}} to form a vertex. If we are in the middle of filling up the second layer (i.e. some of the p = 1 vertices already have degree λ), then the adding the next hyperedge and vertex would form a cycle with a p = 1 vertex with λ(q−1)−cn−1−c{{\lambda (q - 1) - c} \over {n - 1 - c}} for some constant c while the probability that it forms a cycle with a p = 2 vertex is given by c*λ(q−1)n−1−λ(q−1){{c*\lambda (q - 1)} \over {n - 1 - \lambda (q - 1)}}. For the very last hyperedge added in p = 2, the probability of forming a cycle is given by (q−1)2(λ2−1)n−1−λ(q−1){{{{(q - 1)}^2}\left( {{\lambda ^2} - 1} \right)} \over {n - 1 - \lambda (q - 1)}} which is the dominant term. This process can be iterated to show that the dominant term is of the form O(qpλpn−⋯−λp−1(q−1)p−1){\cal O}\left( {{{{q^p}{\lambda ^p}} \over {n - \cdots - {\lambda ^{p - 1}}{{(q - 1)}^{p - 1}}}}} \right) at depth p. For any fix λ and p ≤ ϵ log n for some constant ϵ > 0, the probability that at p distance away from any vertex v_i remains tree-like is given by 32max(0,1−(q−1)λn−1−⋯−(q−1)pλpn−1−⋯−λp−1(q−1)p−1),\max \left( {0,1 - {{(q - 1)\lambda } \over {n - 1}} - \cdots - {{{{(q - 1)}^p}{\lambda ^p}} \over {n - 1 - \cdots - {\lambda ^{p - 1}}{{(q - 1)}^{p - 1}}}}} \right), since 33O(cϵlognn)=O(nϵlogcn){\cal O}\left( {{{{c^{\log n}}} \over n}} \right) = {\cal O}\left( {{{{n^{\log c}}} \over n}} \right) choose ϵ<1logc=1log(λq) < {1 \over {\log c}} = {1 \over {\log (\lambda q)}} so that limn→∞(nϵlogc−1){\lim _{n \to \infty }}\left( {{n^{\log c - 1}}} \right) goes to 0 . Then the probability that at ϵ log n distance away from any vertex is tree like converges to unity for n → ∞, 34limn→∞1−⋯−(q−1)pλpn−1−⋯−λp−1(q−1)p−1=1.\mathop {\lim }\limits_{n \to \infty } 1 - \cdots - {{{{(q - 1)}^p}{\lambda ^p}} \over {n - 1 - \cdots - {\lambda ^{p - 1}}{{(q - 1)}^{p - 1}}}} = 1.

Now we can show that the OGP is also an obstruction in random regular hypergraphs via contradiction. Assume that an algorithm 𝒜 at logarithmic depth is able to find solutions arbitrarily close to the optimal solution for the Maxq-XORSAT on a regular hypergraph. Then this would imply that 𝒜 is also able to find such solutions when performed on an Erdös–Rényi hypergraph since both graphs are p-locally the same. However, this contradicts Theorem 6 and thus, the OGP must also restrict the performance of logarithmic depth local algorithms when applied to a regular hypergraph.

It is of note that proving that the OGP exists in a problem is much easier when the underlying graph is an Erdös–Rényi hypergraph as compared to a regular hypergraph since only the former can be described by a probability distribution. This is why there is no proof that the OGP exists for the Max-q-XORSAT on regular graph as it requires the Poisson distribution found in an Erdös–Rényi hypergraph. Given Theorem 9 and that it is possible to show that the OGP exists in both Erdös–Rényi hypergraphs and regular hypergraphs in some problems [29], it is reasonable to think that if the OGP exists in the former, it also exists in the latter. Motivated by this, we make the following conjectures.

Conjecture 11. If the overlap gap property exists in a COP with an underlying Erdös–Rényi hypergraph of sufficiently high connectivity, then it also exists when the underlying hypergraph is a regular hypergraph of sufficiently high degree.

Conjecture 12 (Monotonicity of the OGP). For the Max-q-XORSAT problem, the overlap gap property is a monotonically increasing graph property.

We note that the proof of Theorem 9 is much simpler if the conjectures are true as can be seen in Appendix A.

We refer the reader to numerous numerical studies about how the performance of the QAOA is unable to surpass the OGP barrier. For instance, the authors of [6] numerically evaluated the performance of the QAOA on Max-3- XORSAT up to p = 14 and got 0.6623Π₃. For the 3-spin glass, the OGP inhibits the AMS algorithm’s performance to get to 0.987Π₃ [30]. A study of the QAOA on Max-q-XORSAT problem similarly finds that for n = 18, the QAOA is unable to get close to the 0.987 approximation ratio even at a depth of p = 30 for q = 3 [31].

Instead, we provide some numerical evidence that instances of the OGP can occur in random regular hypergraphs of odd degree. Our numerical simulation proceeds in the following manner. First, we define the problem size n, uniformity q, and degree d, where we implicitly assume that nd is a multiple of q. Then, randomly generate a d-regular q-uniform hypergraph so that the total number of hyperedges |E| = (nd/q). Next, we randomly generate the list J = {–1, +1}^|E| for the coupling strength of the hyperedges. Finally, we perform a branch and bound algorithm and record those whose cut-fraction exceeds a certain threshold.

Once we have the list of bit-strings and their corresponding cut-fraction, we have to choose some ϵ > 0 such that the list of bit-strings that are ϵ-optimal solutions is small. By default, we limit the bit-strings that are at least 95% to the optimal solution. Finally, compute the overlap between all such ϵ-optimal bit-string and obtain the overlap spectrum.

We find that on average, when d < q, the OGP is not present. It is only when d is greater than q that instances of problems exhibiting the OGP first appear. The numerical simulations were run on q = 3 and varying n up to 30. A histogram of the distribution of solutions can be found in Figure 1 while the typical evolution of the overlap spectrum can be found in Figure 2.

Figure 1.

Plot of a typical cluster of solutions. Y-axis indicates fraction of clauses satisfied and X-axis represents the Hamming distance from the state |1〉^⊗n (e.g.the state |–1〉^⊗n/2 ⊗ |1^⊗n/2 hasavalue 0.5 on the X-axis.

Figure 2.

Typical evolution of the overlap spectrum of a n = 30 Max-3-XORSAT instance with constant degree 15. Here, the plot is based on the Hamming distance rather than overlaps. Typically, the optimal solution and the first few optimal solutions do not exhibit the OGP. At some distance ϵ away from the optimal solution, the OGP occurs. Increasing ϵ further includes additional sub-optimal solution until the set of overlaps is dense.

We also ran simulations on the SK model as it is believed, though not yet proven, that the SK model does not exhibit the OGP [3,30]. We find that indeed the SK model does not exhibit the OGP at n = 45 as can be seen in Figure 3.

Figure 3.

The overlap spectrum of an instance of the SK model with = 45. No gap was observed and including additional suboptimal solution merely monotonically increases the overlap until the set of overlap is dense.