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 alternating operator ansatz (QAOA) is a heuristic hybridquantum-classical algorithm for finding high-quality approximate solutions tocombinatorial optimization problems, such as Maximum Satisfiability. While QAOAis well-studied, theoretical results as to its runtime or approximation ratioguarantees are still relatively sparse. We provide some of the first lowerbounds for the number of rounds (the dominant component of QAOA runtimes)required for QAOA. For our main result, (i) we leverage a connection betweenquantum annealing times and the angles of QAOA to derive a lower bound on thenumber of rounds of QAOA with respect to the guaranteed approximation ratio. Weapply and calculate this bound with Grover-style mixing unitaries and (ii) showthat this type of QAOA requires at least a polynomial number of rounds toguarantee any constant approximation ratios for most problems. We also (iii)show that the bound depends only on the statistical values of the objectivefunctions, and when the problem can be modeled as a $k$-local Hamiltonian, canbe easily estimated from the coefficients of the Hamiltonians. For theconventional transverse field mixer, (iv) our framework gives a trivial lowerbound to all bounded occurrence local cost problems and all strictly $k$-localcost Hamiltonians matching known results that constant approximation ratio isobtainable with constant round QAOA for a few optimization problems from theseclasses. Using our novel proof framework, (v) we recover the Grover lower boundfor unstructured search and -- with small modification -- show that our boundapplies to any QAOA-style search protocol that starts in the ground state ofthe mixing unitaries.

Lower Bounds on Number of QAOA Rounds Required for Guaranteed Approximation Ratios