English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

The Quantum Approximate Optimization Algorithm (QAOA) finds approximatesolutions to combinatorial optimization problems. Its performance monotonicallyimproves with its depth $p$. We apply the QAOA to MaxCut on large-girth$D$-regular graphs. We give an iterative formula to evaluate performance forany $D$ at any depth $p$. Looking at random $D$-regular graphs, at optimalparameters and as $D$ goes to infinity, we find that the $p=11$ QAOA beats allclassical algorithms (known to the authors) that are free of unprovenconjectures. While the iterative formula for these $D$-regular graphs isderived by looking at a single tree subgraph, we prove that it also gives theensemble-averaged performance of the QAOA on the Sherrington-Kirkpatrick (SK)model defined on the complete graph. We also generalize our formula toMax-$q$-XORSAT on large-girth regular hypergraphs. Our iteration is a compactprocedure, but its computational complexity grows as $O(p^2 4^p)$. Thisiteration is more efficient than the previous procedure for analyzing QAOAperformance on the SK model, and we are able to numerically go to $p=20$.Encouraged by our findings, we make the optimistic conjecture that the QAOA, as$p$ goes to infinity, will achieve the Parisi value. We analyze the performanceof the quantum algorithm, but one needs to run it on a quantum computer toproduce a string with the guaranteed performance.

The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model