The quantum approximate optimization algorithm (QAOA) is a nearterm hybrid algorithm intended to solve combinatorial optimization problems, such as MaxCut. QAOA can be made to mimic an adiabatic schedule, and in the p → ∞ limit the final state is an exact maximal eigenstate in accordance with the adiabatic theorem. In this work, the connection between QAOA and adiabaticity is made explicit by inspecting the regime of p large but finite. By connecting QAOA to counterdiabatic (CD) evolution, we construct CDQAOA angles which mimic a counterdiabatic schedule by matching Trotter "error" terms to approximate adiabatic gauge potentials which suppress diabaticmore »
QED driven QAOA for networkflow optimization
We present a general framework for modifying quantum approximate optimization algorithms (QAOA) to solve constrained network flow problems. By exploiting an analogy between flowconstraints and Gauss' law for electromagnetism, we design lattice quantum electrodynamics (QED) inspired mixing Hamiltonians that preserve flow constraints throughout the QAOA process. This results in an exponential reduction in the size of the configuration space that needs to be explored, which we show through numerical simulations, yields higher quality approximate solutions compared to the original QAOA routine. We outline a specific implementation for edgedisjoint path (EDP) problems related to traffic congestion minimization, numerically analyze the effect of initial state choice, and explore tradeoffs between circuit complexity and qubit resources via a particlevortex duality mapping. Comparing the effect of initial states reveals that starting with an ergodic (unbiased) superposition of solutions yields better performance than beginning with the mixer groundstate, suggesting a departure from the ``shortcut to adiabaticity" mechanism often used to motivate QAOA.
 Award ID(s):
 1653007
 Publication Date:
 NSFPAR ID:
 10321352
 Journal Name:
 Quantum
 Volume:
 5
 ISSN:
 2521327X
 Sponsoring Org:
 National Science Foundation
More Like this


Quantum computational supremacy arguments, which describe a way for a quantum computer to perform a task that cannot also be done by a classical computer, typically require some sort of computational assumption related to the limitations of classical computation. One common assumption is that the polynomial hierarchy ( P H ) does not collapse, a stronger version of the statement that P ≠ N P , which leads to the conclusion that any classical simulation of certain families of quantum circuits requires time scaling worse than any polynomial in the size of the circuits. However, the asymptotic nature of thismore »

Quantum computers and simulators may offer significant advantages over their classical counterparts, providing insights into quantum manybody systems and possibly improving performance for solving exponentially hard problems, such as optimization and satisfiability. Here, we report the implementation of a lowdepth Quantum Approximate Optimization Algorithm (QAOA) using an analog quantum simulator. We estimate the groundstate energy of the Transverse Field Ising Model with longrange interactions with tunable range, and we optimize the corresponding combinatorial classical problem by sampling the QAOA output with highfidelity, singleshot, individual qubit measurements. We execute the algorithm with both an exhaustive search and closedloop optimization of themore »

We introduce a notion of \emph{generic local algorithm} which strictly generalizes existing frameworks of local algorithms such as \emph{factors of i.i.d.} by capturing local \emph{quantum} algorithms such as the Quantum Approximate Optimization Algorithm (QAOA). Motivated by a question of Farhi et al. [arXiv:1910.08187, 2019] we then show limitations of generic local algorithms including QAOA on random instances of constraint satisfaction problems (CSPs). Specifically, we show that any generic local algorithm whose assignment to a vertex depends only on a local neighborhood with o(n) other vertices (such as the QAOA at depth less than ϵlog(n)) cannot arbitrarilywell approximate boolean CSPs ifmore »

We propose a neural network approach that yields approximate solutions for highdimensional optimal control problems and demonstrate its effectiveness using examples from multiagent path finding. Our approach yields controls in a feedback form, where the policy function is given by a neural network (NN). Specifically, we fuse the HamiltonJacobiBellman (HJB) and Pontryagin Maximum Principle (PMP) approaches by parameterizing the value function with an NN. Our approach enables us to obtain approximately optimal controls in realtime without having to solve an optimization problem. Once the policy function is trained, generating a control at a given spacetime location takes milliseconds; in contrast,more »