Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: The Quantum Approximate Optimization Algorithm Needs to See the Whole
  Graph: Worst Case Examples   The Quantum Approximate Optimization Algorithm can be applied to search
problems on graphs with a cost function that is a sum of terms corresponding to
the edges. When conjugating an edge term, the QAOA unitary at depth p produces
an operator that depends only on the subgraph consisting of edges that are at
most p away from the edge in question. On random d-regular graphs, with d fixed
and with p a small constant time log n, these neighborhoods are almost all
trees and so the performance of the QAOA is determined only by how it acts on
an edge in the middle of tree. Both bipartite random d-regular graphs and
general random d-regular graphs locally are trees so the QAOA's performance is
the same on these two ensembles. Using this we can show that the QAOA with
$(d-1)^{2p} < n^A$ for any $A<1$, can only achieve an approximation ratio of
1/2 for Max-Cut on bipartite random d-regular graphs for d large. For Maximum
Independent Set, in the same setting, the best approximation ratio is a
d-dependent constant that goes to 0 as d gets big.

21
The categories of this paper are: adap-org
7
The categories of this paper are: hep-th
32
The categories of this paper are: atom-ph
15
The categories of this paper are: nucl-ex
10
The categories of this paper are: q-bio
23
The categories of this paper are: solv-int
12
The categories of this paper are: nucl-th
1
The categories of this paper are: cs
29
The categories of this paper are: funct-an
16
The categories of this paper are: stat
9
The categories of this paper are: nlin
14
The categories of this paper are: math-ph
27
The categories of this paper are: comp-gas
33
The categories of this paper are: plasm-ph
17
The categories of this paper are: q-fin
36
The categories of this paper are: cmp-lg