---
abstract: 'The quantum approximate optimization algorithm (QAOA) has become a cornerstone of contemporary quantum applications development. Here we show that the [*density*]{} of problem constraints versus problem variables acts as a performance indicator. Density is found to correlate strongly with approximation inefficiency for fixed depth QAOA applied to random graph minimization problem instances. Further, the required depth for accurate QAOA solution to graph problem instances scales critically with density. We performed a detailed reanalysis of the data reproduced from Google’s Sycamore superconducting qubit quantum processor executing QAOA applied to minimization problems on graphs. We found that Sycamore approaches a rapid fall-off in approximation quality experienced beyond intermediate-density instances. Our findings offer new insight into performance analysis of contemporary quantum optimization algorithms and contradict recent speculation regarding low-depth QAOA performance benefits.'
author:
- 'V. Akshay'
- 'H. Philathong'
- 'I. Zacharov'
- 'J.D. Biamonte'
bibliography:
- 'ref.bib'
date: 17 July 2020
title: 'Reachability Deficits Implicit in Google’s Quantum Approximate optimization of Graph Problems'
---

Introduction {#introduction .unnumbered}
============

Quantum approximate optimization (QAOA) is the most studied gate-based approach towards quantum enhanced optimization. Google’s Sycamore quantum processor was recently used to demonstrate QAOA applied to graph minimization problems [@arute2020quantum]. This recent study [@arute2020quantum] follows Sycamore’s demonstration of computational capabilities surpassing those of classical supercomputers for specific sampling tasks [@arute2019quantum].

Such contemporary milestones have dramatically increased interest in harnessing quantum processors for more practical means. Towards this goal, recent experimental demonstrations of quantum algorithms also include quantum chemistry [@aspuru2005simulated; @o2016scalable], machine learning [@biamonte2017quantum; @xia2018quantum], simulation of condensed matter systems [@lloyd1996universal; @lamata2014efficient] as well as discrete optimization [@kadowaki1998quantum; @arute2019quantum; @pagano2019quantum]. While the ultimate prospects of quantum enhanced algorithms is tantalizing, the computational capacity of existing and near term applications remains unclear.

Recently Google’s Sycamore quantum processor, which is based on fifty four superconducting qubits, has demonstrated promising results related to quantum enhanced discrete optimization (i.e. the so called, QAOA algorithm). The authors [@arute2020quantum] experimentally realized QAOA for three classes of graph optimization problems. Such problems assign energy to graphs, which depend on nodes—represented as qubits—taking binary values. The experiments minimized this energy for three classes of graphs up to twenty three nodes [@arute2020quantum].

QAOA is an instance of the class of variational quantum algorithms. Variational algorithms vary over a family of quantum states to minimize an objective function calculated from easy to measure observables. Proposed primarily in [@farhi2014quantum; @mcclean2016theory], the variational approach is in theory equivalent to the quantum circuit model under a polynomial (Karp) reduction [@biamonte2019universal]. Hence, the variational approach is as powerful as a general quantum computer. However only restricted forms—which require significant classical resources in the optimization step—can currently be realized in practice.

Indeed, the advantage of the variational approach is also its weakness. A classical optimization loop iteratively adjusts a quantum state prepared by an adjustable quantum circuit (an ansatz). High depth circuits of fixed structure have been proven to represent universal resources for quantum computation [@lloyd2018quantum; @morales2019universality] and hence can emulate the gate model piece-wise. However, higher depth circuits demand a significant optimization task to be performed on a classical computer. In contrast, while reasonably short depth circuits have shown noise-free quantum advantage [@lin2016performance; @crooks2018performance; @marsh2019quantum; @wang2018quantum; @jiang2017near; @morales2018variational], less remains known about the depth of circuits required to enable practical advantage using noisy circuits.

Changing to a state dependent picture and extending recent results related to satisfiability [@akshay2020reachability], here we propose an order parameter which correlates with the performance of QAOA. In particular, we consider the ratio of graph edges to graph nodes (called graph density). Though a careful comparison, we empirically observe the following findings. (i) Google’s recent Sycamore data represents a statistically narrow subset of random instances having densities that are at the edge of a fall-off region. (ii) Longer depth circuits become a necessity for increasingly accurate approximations and this depth correlates with increasing density.

Contemporary demonstrations of QAOA serve as benchmarks to enable practically relevant demonstrations of optimization and other quantum algorithms [@otterbach2017unsupervised; @willsch2020benchmarking; @abrams2019implementation; @bengtsson2019quantum; @pagano2019quantum; @qiang2018large]. Our results illuminate the first QAOA performance indicators. By applying our analysis techniques phenomenologically to Google’s Sycomore data, we shed new light on the significance of this recent experimental milestone [@arute2020quantum]. Indeed, the Sycomore data contained effects that prior analysis techniques overlooked.

Results {#results .unnumbered}
=======

Google considered up to a depth-five QAOA ansatz on three separate classes of graph problems [@arute2020quantum]. Under experimental noise, Google was able to realize functional depth-three ansatz performance whereas depths four and five were critically limited by noise. The depth three ansatz involves classical optimization over only six real parameters, three of which are constrained in the interval $[0, \pi)$ whereas the remaining three are in $[0, 2\pi)$.

We reproduced Google’s ideal (noiseless) data using exact numerical supercomputer emulations (see Fig. \[g\_metric\]). Further, we show that QAOA on random graph instances generated at varying densities exhibit strong density dependent performance. Although higher depths achieve better performance, the density dependence is still exhibited (see Fig. \[fixed\_n\_performance\]). Moreover, higher depths necessitate increasingly more parameters to be optimized in the classical step.

Based on the comparison of random graphs at approximately the same densities with the restrictive graph instances Google considered, we do not observe any topology dependent performance bias that can be attributed statistical relevance. This finding suggests density—albeit a coarse graining—is the salient limiting performance indicator for fixed depth QAOA (see Fig. \[comparision\_performance\]).

With density as an order parameter, we find that solutions of random instances generated below densities of $0.5$ to show the best performance independent of the number of nodes. Beyond density $0.5$, we find the performance to strongly depend on density for fixed number of nodes. In particular, we observe a sharp fall-off behaviour in performance which appears to saturate logistically beyond density $1.5$. It is under this new outlook Google’s data are compared and contrasted (see Fig. \[performance\_3dlandscape\] and Fig. \[performance\_2D projection\]).

Firstly, the authors [@arute2020quantum] consider the Hardware-Grid problem wherein the generated random instances are native to the inherent hardware connectivity layout of Google’s Sycamore chip (sometimes called, [*interaction graph*]{}). Here the instances generated by varying the number of nodes ($n$) which we found to appear at densities between $1.0$ and $1.5$. Our exact simulation of depth three QAOA suggests the success probability (or the state overlap) to worsen with the number of nodes (increasing density), achieving a meager $0.07$ for nodes $n=20$ (at density = 1.3).

Secondly, the experiments considered $3$-Regular Graphs. In this case the randomly generated instances have an even number of nodes with constant density $1.5$. We found success probability to worsen with the number of nodes achieving roughly the same value of $0.07$ for nodes $n=20$ (at density = 1.5).

In both cases we find the considered instances appear on the edge of a fall-off region in our analysis of the density dependent performance landscape. It is for instances beyond these densities (that is, beyond critical approximation density fall off) that we observe limited performance for depth three QAOA ansatz.

Finally, the mean field Sherrington-Kirkpatrick (SK) model is considered where the generated graph instances are fully connected and have the maximum possible density ($(n-1)/2$) for $n$ nodes ranging from $10$ to $20$.

Unlike the previous two cases, the SK instances scale up density linearly with $n$. Furthermore, for any fixed $n$, such graph instances have the highest density and therefore QAOA should indicate poor performance. This agrees exactly with our emulation. For each $n$, we observe the success probability for the SK model to be the lowest in the considered family of graphs (see the bottom pane on Fig. \[g\_metric\]).

Conclusions {#conclusions .unnumbered}
===========

To assess QAOA performance, Google applies [*approximation ratio*]{}—a standard technique in the classical theory of graph optimization (see e.g. [@arute2020quantum]). Under this setting, an almost constant performance across the three graph problem families is visually observed—reproduced in Fig. \[g\_metric\] top pane.

It is only under other indicators such as (i) best approximation error and (ii) success probability—see Methods—that the density dependence in approximation inefficiency is visually revealed (a.k.a. reachability deficits). Although the effect can be inferred from Google’s approximation ratio, the effect of reachability deficits are highly suppressed visually.

We finally assert that future experimental and numerical studies related to QAOA should report and contrast algorithmic performance with instance densities.

Methods {#methods .unnumbered}
=======

#### **QAOA.** {#qaoa. .unnumbered}

Given an objective function which encodes the solution to an optimization problem in the ground state of a Hamiltonian, $\mathcal{V}$, the usual QAOA procedure is as follows,

1.  Generate ansatz states, $\ket{\psi(\boldsymbol{\gamma},\boldsymbol{\beta})}$ on a quantum computer, where $\boldsymbol{\gamma}=(\gamma_{1},\gamma_{2},\cdots,\gamma_{p})$ and $\boldsymbol{\beta}=(\beta_{1},\beta_{2},\cdots,\beta_{p})$ are tunable real parameters over some fixed range. The state is prepared by applying a sequence of 2*p*-parameter unitary gates acting on the reference state $\ket{+}^{\otimes{n}}$ which is the symmetric superposition of all $2^{n}$ computational basis states as follows, $$\label{qaoa equation}
            \ket{\psi(\boldsymbol{\gamma},\boldsymbol{\beta})}=\prod_{k=1}^{p} \mathcal{U}(\gamma_{k},\beta_{k})\ket{+}^{\otimes{n}},$$ where $$\label{driverandproblem}
            \mathcal{U}(\gamma_{k},\beta_{k})=\exp{-i \beta_{k}\mathcal{H}_{x}} \cdot \exp{-i \gamma_{k}\mathcal{V}}.$$ The Hamiltonian $\mathcal{H}_{x}=\sum_{i} \sigma_{x}^{(i)}$ is called the driver Hamiltonian, and $\mathcal{V}$ is the problem Hamiltonian where ground states correspond to the bit strings that minimizes the objective function of interest.

2.  Measurement of the state in Eq.  is done to compute the expected value, $\bra{\psi(\boldsymbol{\gamma},\boldsymbol{\beta})}\mathcal{V}\ket{\psi(\boldsymbol{\gamma},\boldsymbol{\beta})}$. This is an approximation which can be calculated efficiently on a classical computer.

3.  Steps 1 and 2 are repeated and a classical optimization algorithms is used to assign a set of optimum parameters, $\boldsymbol{\gamma}^{*}$ and $\boldsymbol{\beta}^{*}$ that minimize $\bra{\psi(\boldsymbol{\gamma},\boldsymbol{\beta})}\mathcal{V}\ket{\psi(\boldsymbol{\gamma},\boldsymbol{\beta})}$. $\bra{\psi(\boldsymbol{\gamma}^{*},\boldsymbol{\beta}^{*})}\mathcal{V}\ket{\psi(\boldsymbol{\gamma}^{*},\boldsymbol{\beta}^{*})}$ then represents an approximate solution to the optimization problem.

#### **Problem description.** {#problem-description. .unnumbered}

In this paper we study minimization problem on graphs. The objective function of interest can be defined as follows:

Given an undirected weighted graph $G=(V,E)$, with $|V| = n$ nodes and $|E| = m$ edges. $E$ denotes the set of edges in $G$ as $E = \lbrace (i,j) \rbrace$, where $i \neq j $ and $i,j \in V$. In general, the edge weights are defined as a map $w:\, E \rightarrow \mathbb{R}$. Yet in our case and without loss of generality, we restrict to sampling $w_{ij}$s from a uniform distribution over $\lbrace -1,+1 \rbrace$.

Minimization problems on $G$ are defined thorough a cost-function $\mathcal{C}(\boldsymbol{z})$ with a corresponding embedding as quantum Hamiltonian operator. Here we employ the following as our objective function, $$\mathcal{C} = \sum_{(i,j) \in E} w_{ij}Z_{i}Z_{j},$$ where $\boldsymbol{z}$ denotes the bitstring or bit assignment to the nodes in $G$ and $Z_{i}$ corresponds to the Pauli $Z$ operator action on the $i^{th}$ qubit. In general, with appropriate cost-function construction and Ising spin encoding, minimization on graphs can represent solving a family of NP-hard optimization problems such as MAX-CUT, Vertex cover and Maximum Independent Set to name a few.

#### **Performance metrics.** {#performance-metrics. .unnumbered}

QAOA performance is analysed under the following two performance metrics,

1.  the error in best possible approximation,

2.  the success probability or the ground state overlap.

Let $\ket{\psi}$, be the *p*–depth QAOA ansatz states generated by Eq. , we define the error in best possible approximation as $$\label{reachabilitydef}
    f = \min_{\ket{\psi} \subseteq \mathbb{C}_{2}^{\otimes{n}}} \bra{\psi}\mathcal{C}\ket{\psi} - \min_{\ket{\phi} \in \mathbb{C}_{2}^{\otimes{n}}} \bra{\phi}\mathcal{C}\ket{\phi}.$$ This quantity characterises the limiting performance of QAOA. The first term on the right indicates minimization over the set of reachable states generated by a fixed depth QAOA ansatz whereas the second term represents the exact optimum value of $\mathcal{C}$ computed by minimization over the entire Hilbert space.

To calculate the success probability or the ground state overlap, let $\lbrace\ket{\text{gs}_{i}}\rbrace$ be the set of *d* degenerate ground states of $\mathcal{C}$ then the overlap is given by, $$\eta = \sum_{i=1}^{d}{\abs{\bra{\psi_{p}(\boldsymbol{\gamma},\boldsymbol{\beta})}\ket{\text{gs}_{i}}}^{2}}.$$

A well known performance metric is the approximation ratio defined as, $$r = \frac{\langle \mathcal{C} \rangle}{\mathcal{C}_{min}}.$$ It is under this performance metric that Google’s data are represented [@arute2020quantum]. Although this metric is bounded between $[0,1]$, and it can directly be used to contrast performance with other polynomial-time approximation algorithms, we observe the effect of density dependence to be visually suppressed. This is due to the logistic behaviour of the error in best possible approximation, $\langle \mathcal{C} \rangle - \mathcal{C}_{min}$. Since both $\langle \mathcal{C} \rangle$ and $\mathcal{C}_{min}$ grow with density for any given $n$ and fixed depth QAOA ansatz, the ratio visually conceals density dependence. This is further illustrated when we consider success probability as our performance indicator. Under this choice we clearly observe the limiting performance of QAOA.

#### **Graph Instances.** {#graph-instances. .unnumbered}

Here we present the construction of random problem instances used in our work.

*Fixed $n$ case.* We first show the approximation inefficiency or the feature of density dependent performance under the two metrics by studying QAOA on the uniform random graph model, $G_{n,m}$ for fixed $n$. The density in the case of such graph problems can be defined as the ratio of the number of edges to the number of nodes, $m/n$.

Random instances are generated by initializing an empty graph on the vertex set of size $|V|= n$. Then, $m$ edges are constructed in such a way that all possible $\binom{\binom{n}{2}}{m}$ choices are equally likely with random weights drawn from $\lbrace -1,+1 \rbrace$.

*3-regular graphs*. A 3-regular graph, also known as a cubic graph, is when each node in the graph has degree equal to 3. The density of generated instance in this case is constant ($density = 1.5$) as the number of edges required for constructing a 3-regular graph is given by $3\times\frac{n}{2}$, for even $n$.

*2-D grid graphs*. These graphs are interesting mainly due to the inherent hardware connectivity of Google’s Sycamore. Such graphs are generated by constructing an $N \times N$ square grid and randomly deleting nodes on the boundaries to construct random grid instance with $n \leq N^2$ nodes. Unlike the case of regular graphs, 2-D grid graphs do not share a constant density across the generated instance. The maximum number of edges in a square/ partially square grid is given by $\lfloor 2n - 2\sqrt{n} \rfloor$. Therefore, at most density of such instances is bounded above by $2.0$.

#### **Numerical Methods.** {#numerical-methods. .unnumbered}

The large calculations were performed on Skotlech’s Zhores computer [@Zacharov2019]. The programs were written in Python with Intel optimised libraries. The code is available by reasonable request.

The authors acknowledge support from the project, [*Leading Research Center on Quantum Computing*]{} (Agreement No. 014/20). [*Data and code availability.*]{} The generated numerical data and the code for generating the data will be made available on GitHub after this paper is published. The authors acknowledge the use of Skoltech’s Zhores supercomputer for obtaining the numerical results presented in this paper. [*Competing interests.*]{} The authors declare no competing interests. [*Author contributions.*]{} All authors conceived and developed the theory and design of this study and verified the methods. JB proposed the study and supervised its execution. VA, HP and IZ developed and deployed the parallel code to collect numerical data. All authors contributed to interpret the results and wrote the manuscript.

![image](fixed_10NGnm_energy.pdf){width="\textwidth"} ![image](fixed_10NGnm_overlap.pdf){width="\textwidth"}

![image](g_compare_grid_regular_energy.pdf){width="\textwidth"} ![image](g_compare_grid_regular_overlap.pdf){width="\textwidth"}

![image](3d_energy.pdf){width="80.00000%"} ![image](3d_overlap.pdf){width="80.00000%"}

![image](energy_contour.pdf){width="90.00000%"} ![image](overlap_contour.pdf){width="90.00000%"}
