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 Plus annual

Presents the access of premium content as premium feature

Premium Content

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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The Quantum Approximate Optimization Algorithm (QAOA) is designed to run on agate model quantum computer and has shallow depth. It takes as input acombinatorial optimization problem and outputs a string that satisfies a highfraction of the maximum number of clauses that can be satisfied. For certainproblems the lowest depth version of the QAOA has provable performanceguarantees although there exist classical algorithms that have betterguarantees. Here we argue that beyond its possible computational value the QAOAcan exhibit a form of Quantum Supremacy in that, based on reasonable complexitytheoretic assumptions, the output distribution of even the lowest depth versioncannot be efficiently simulated on any classical device. We contrast this withthe case of sampling from the output of a quantum computer running the QuantumAdiabatic Algorithm (QADI) with the restriction that the Hamiltonian thatgoverns the evolution is gapped and stoquastic. Here we show that there is anoracle that would allow sampling from the QADI but even with this oracle, ifone could efficiently classically sample from the output of the QAOA, thePolynomial Hierarchy would collapse. This suggests that the QAOA is anexcellent candidate to run on near term quantum computers not only because itmay be of use for optimization but also because of its potential as a route toestablishing quantum supremacy.

Quantum Supremacy through the Quantum Approximate Optimization Algorithm