Reachability Deficits in Quantum Approximate Optimization
V. Akshay H. Philathong M. E. S. Morales J. Biamonte







    [e-mail:]akshay.vishwanathan@skoltech.ru
      http://quantum.skoltech.ru
    Deep Quantum Laboratory, Skolkovo Institute of Science and Technology, 3 Nobel Street, Moscow, Russia 121205

    Deep Quantum Laboratory, Skolkovo Institute of Science and Technology, 3 Nobel Street, Moscow, Russia 121205

    Deep Quantum Laboratory, Skolkovo Institute of Science and Technology, 3 Nobel Street, Moscow, Russia 121205

    Deep Quantum Laboratory, Skolkovo Institute of Science and Technology, 3 Nobel Street, Moscow, Russia 121205
    
    
 


The quantum approximate optimization algorithm (QAOA) has rapidly become a cornerstone of contemporary quantum algorithm development. Despite a growing range of applications, only a few results have been developed towards understanding the algorithms ultimate limitations. Here we report that QAOA exhibits a strong dependence on a problem instances constraint to variable ratio—this problem density places a limiting restriction on the algorithms capacity to minimize a corresponding objective function (and hence solve optimization problem instances). Such reachability deficits persist even in the absence of barren plateaus <cit.> and are outside of the recently reported level-1 QAOA limitations <cit.>. These findings are among the first to determine strong limitations on variational quantum approximate optimization.



Reachability Deficits in Quantum Approximate Optimization
    J.D. Biamonte
    December 30, 2023
=========================================================





  
*Introduction.
Variational hybrid quantum/classical algorithms have  become an area of significant interest <cit.>. These algorithms minimize objective functions which can be largely agnostic to systematic errors. This increases their potential in current Noisy Intermediate-Scale Quantum devices (NISQ) <cit.>. These hybrid algorithms involve parameterized quantum circuits trained in a classical learning loop. Particular interest is the Quantum Approximate Optimization Algorithm (or QAOA) designed to find approximate solutions to combinatorial optimization problems <cit.>. Although QAOA has been shown to approximate solutions to problems such as MAX-CUT <cit.> and realize Grover's search algorithm <cit.>, little is known about its ultimate limitations. 

Recent findings suggest that randomly parameterized quantum circuits in the large scale will suffer from barren plateaus resulting in an exponentially low probability to find correct solutions <cit.>. Recent results also show that classical algorithms in a certain restrictive (single depth) setting can outperform level-1 QAOA <cit.>. Can higher depth versions achieve advantage over classical algorithms?  

QAOA performance has an evident dependence on the circuit-depth and it is observed that increasing depth improves the quality of the possible approximation (at the cost of increasing the parameter search space). We show that circuit depth is not the only limiting restriction. Indeed, we found that finding appropriate solutions has strong dependence on the ratio of a problems constraint to variables (problem density). Hence, QAOA exhibits strong dependence on a problems density and for any fixed ansatz, there exists problem instances of high-density that appear not to be accessible. This feature persists as a fundamental limitation exhibited by QAOA.   

As a means to study the performance of QAOA, we turn to constraint satifiability– a tool with a successful history.  Such problems are expressed in terms of n variables and m clauses (or constraints). The density of such problem instances is the clause to variable ratio, the clause density α = m/n. k-SAT clauses are randomly generated to form instances by uniformly selecting unique k-tupels from the union of a variable set (cardinality n>k) and its element wise negation.  We consider both random instances of the NP-complete decision problem 3-SAT, as well as random instances of 2-SAT which is efficiently solvable. QAOA aims to approximate solutions to optimization version of these problems, MAX-2-SAT and MAX-3-SAT. Both are NP-Hard for exact solutions and APX-complete for approximations beyond a certain ratio <cit.>. In these settings, the algorithm's limiting performance exhibits strong dependence on the problem density in both cases.  

We call the QAOA problem general when considering random 3-SAT and 2-SAT instances with the standard one-body driver Hamiltonian <cit.>. In both cases we found strong limiting dependence of QAOA for clause densities above ∼ 1. Moreover, the difference between the two problems (i.e. 2- vs 3-SAT) seemed negligible to a visual approximation. The density played the dominate role correlating inversely with performance. We further consider this same scenario, replacing the driver Hamiltonian with a n-body projector (|+⟩⟨+|)^⊗n. While problem density dependence is still strongly exhibited, we found a decrease in the error of best-possible-approximation. Finally, by considering a single projector onto a solution space and the same driver as above, the variational version of Grover's search algorithm is recovered. While the clause density is fixed for a given n, the analytical solutions of this model provide a test bed to ascertain that energy approximation is critically dependent on circuit depth at each fixed density.  







  
*Quantum Approximate Optimization.
The usual procedure in implementing QAOA is as follows <cit.>:

    
  * Create ansatz states, |ψ(γ,β)⟩ on a quantum computer where, γ=(γ_1,γ_2,....,γ_p) and β=(β_1,β_2,....,β_p) are tunable over some fixed range. The state is prepared by applying a sequence of 2p-parameter gates acting on the reference state, |+⟩^⊗n as, 
    
    |ψ(γ,β)⟩=∏_i=1^p𝒰(γ_i,β_i)|+⟩^⊗n,
 
    where
    
    𝒰(γ_k,β_k)=exp-β_kℋ_x·exp-γ_k𝒱.

    
  * Measurement of this state (<ref>) is done to compute the expected value of the objective function of interest, ⟨𝒱⟩. For QAOA, the objective function is the optimization  problem.
    
  * Classical optimization algorithms are used to assign a set of parameters, γ^* and β^* that minimize ⟨ψ(γ,β)|𝒱|ψ(γ,β)⟩. 
    
  * Steps 1 and 2 are repeated by adjusting parameters to approximately minimize 𝒱,   ⟨ψ(γ^*,β^*)|𝒱|ψ(γ^*,β^*)⟩≈min(𝒱) . 


The variational ansatz states created by QAOA take inspiration from the quantum adiabatic algorithm, where a system is initialized in an easy to prepare ground state of a local Hamiltonian ℋ_x= ∑_iσ_x^(i), the driver Hamiltonian, which  is  then  slowly  transformed  to  the problem  Hamiltonian, 𝒱 <cit.>. Trotterization of this procedure gives a long QAOA sequence as can be understood from equation (<ref>). 
However, the Trotter approximation is evidently violated for a typical sequence. Outside of this understanding, the performance of QAOA seems rather remarkable.



  
*Quantum Approximation in Boolean Satisfiability.
Boolean satisfiability is the problem of determining satisfiability of a Boolean expression written in conjunctive normal form (CNF). It is possible to map  any Boolean satisfiability problem into 3-SAT; conjunction of clauses restricted to 3 literals, via Karp reduction. It is well known that decision 3-SAT is NP-complete  <cit.>. Decision 2-SAT, is the problem restricted to clauses limited to 2 literals. This problem can be solved in polynomial-time <cit.>. 2-SAT exhibits an algorithmic phase transition at a critical clause to variable ratio, α_c = 1 <cit.>. The transition is emperically exhibited in 3-SAT numerics <cit.>. This implies that for α < α_c almost all instances are satisfiable and for α  > α_c, almost all instances are not.

Known algorithms exhibit a slow-down around the phase transition, suggesting that most of the hard-instances are concentrated near this point. This signature of an easy-hard-easy transition is exhibited for the decision version of SAT. 

 In order to approximate solutions of MAX- 3-SAT and MAX-2-SAT, an embedding scheme maps SAT-instances into Hamiltonians <cit.> as : 


    ℋ_SAT = ∑_l𝒫(l),


where l indexes each clause in the SAT instance and 𝒫(l) are rank-one projectors that penalize each unsatisfiable assignments with at-least 1 unit of energy. By this construction, we embed solutions to the MAX-3-SAT or MAX-2-SAT into the ground state space of ℋ_SAT. 2-SAT instances requires only quadratic interactions whereas 3-SAT requires 3-body ones. Satisfiable instances are characterized by a zero ground state energy, E_g = 0 and unsatisfiable instances with E_g≥ 1, representative of the minimum violated clauses.

QAOA with standard settings, ℋ_x=∑_iσ_x^(i) and 𝒱 = ℋ_SAT, can now be used to calculate the energy approximation E_g^QAOA, where


    E_g^QAOA =  min_γ,β⟨ψ(γ,β)|ℋ_SAT|ψ(γ,β)⟩.
 







 We numerically study f = E_g^QAOA - min(𝒱) as a function of clause density α, for a p-depth QAOA circuit on randomly generated 3-SAT and 2-SAT  instances (see Fig. <ref>). Although increased depth versions achieve better approximations, the performance or best possible approximation of any arbitrary fixed depth QAOA exhibit a non trivial dependence on the density of the problem, α. 





  
*Reachability Deficits.



Fixed depth QAOA on MAX-3-SAT and MAX-2-SAT instances show limiting performance beyond a critical clause density. Higher depth versions are needed to break free from this limitation. Moreover, we observe recovery of ground state energy to strongly depend on the QAOA circuit depth and also the problem density for fixed problem size.  This limitation is what we refer to as reachability deficits and is formulated as follows: 
   




Let |ψ⟩, be the ansatz states generated from a p–depth QAOA circuit as shown in (<ref>). Then 

    f = min_ψ⊂ℋ⟨ψ|𝒱|ψ⟩ - min_ϕ∈ℋ⟨ϕ|𝒱|ϕ⟩,

characterises the limiting performance of QAOA. The R.H.S of equation (<ref>) can be expressed as a function, f(p,α,n).
For p ∈ℕ and fixed problem size, ∃ α > α_c such that  f ≠ 0. This is a reachability deficit. 


Fixed depth QAOA exhibit such reachability deficits even when modified with a new driver ℋ_x = (|+⟩⟨+|)^⊗n (see Fig. <ref>). The modified version requires lower circuit depths for achieving similar performance as standard QAOA but still exhibits reachability deficits.

We analyse numerically the dependence of p^*, the critical circuit depth, or the minimum circuit depth for which QAOA returns the exact ground state energies (or least number of violated clauses) for both MAX-3-SAT and MAX-2-SAT up-to a set tolerance (see Fig. <ref>). The tolerance is set as a condition on the overlap between the QAOA generated state and the exact ground state which can be calculated as follows:

Let {|gs_i⟩} be the d degenerate ground states of ℋ_SAT then the overlap is given by,

    η = ∑_i=1^d⟨ψ_p(γ,β)||gs_i⟩^2.

Instances to the left (classically easy),  α < α_c require low critical depth to recover exact ground state energies and for instances, α > α_c, the critical depth is higher and grows with α. Note in particular that the transition point does not coincide with the algorithmic phase transition point exhibited in decision version of 3-SAT, although the critical depth of exhibited reachability deficits is closer for 2-SAT's critical point.






Reachability deficits are different from barren plateaus <cit.>, where randomly parameterised quantum circuits for large problem sizes have exponentially low success in finding states that minimize the objective function. In the case of barren plateaus the state that achieves global minima of the objective function is accessible but choosing initial parameters randomly have greater probability to set the initial guess on a plateau of states where evaluation of gradients concentrates to zero. In contrast, irrespective of the initial parameter setting, QAOA with depth p < p^* cannot reach optimal values as the corresponding state that achieves it becomes inaccessible.




  
*Variational Grover Search.
Variational Grover search <cit.> can be thought of as QAOA  with the following setting,


𝒱=|ω⟩⟨ω| 


and 


ℋ_x=(|+⟩⟨+|)^⊗n,


where |ω⟩∈ℂ_2^⊗n is the objective state we are searching for. Hence the objective function of interest here is the minimization of the expected value of the Hamiltonian ℋ = 1 - |ω⟩⟨ω| over the QAOA ansatz state |ψ(γ,β)⟩ or,

    min_γ,β⟨( 1 - |ω⟩⟨ω|) ⟩_|ψ( γ , β)⟩ = min_γ,β(1 - ⟨ω||ψ(γ,β)⟩^2).


The unitary gates that appear in equation (<ref>) can be simplified into the following expressions;

    exp-iγ_k𝒱   = exp-iγ_k|ω⟩⟨ω|
       =1 + (e^-iγ_k - 1 )|ω⟩⟨ω|,

similarly,

    exp-iβ_kℋ_x   = exp-iβ_k|+⟩⟨+|^⊗n
       =1 + (e^-iβ_k - 1 )|+⟩⟨+|^⊗n .

We can then write the prepared ansatz state from a p-depth QAOA circuit as, 

    |ψ_p(γ,β)⟩=A_p1/√(N-1)∑_x ≠ω|x⟩ + B_p|ω⟩,

where, the amplitudes of one step can be related to the amplitudes of the next step via the recursive application of the matrix, 

    M_p=  [    1 + a(N-1)/N -a(b+1)√(N-1)/N;      -a√(N-1)/N    (b+1)(1+a/N) ].

Here, a=e^-iγ_p-1,  b=e^-iβ_p-1 and N=2^n. Substituting equation (<ref>) in equation (<ref>) we obtain the approximated energy as 

    E^QAOA_g= 1-B_p^2.


Minimization in equation (<ref>) is done numerically and the approximate energy as a function of circuit-depth is computed (see Fig. <ref>). For each problem size it is observed that approximated energy converges to the exact ground state energy E_g=0, when the circuit-depth reaches the critical value, p^*. At this depth, QAOA is able to exactly recover |ψ_p^*(γ^*,β^*)⟩=|ω⟩ for some set of parameters γ^* and β^*. 

If we set p < p^*, the minimization in equation (<ref>) terminates with E_g^QAOA > 0. This implies that in equation (<ref>), A_p^2≠ 0. It is evident that in such a case, QAOA cannot reach the state |ω⟩. The reachability deficit is removed only when the QAOA circuit is set with p ≥ p^*. To establish the dependence of p^* on the problem density, we increase n, the size of the search space and recover a Grover scaling, 𝒪(√(N)) for p^*.    




  
*Discussion.
QAOA has been applied many times throughout the literature, with many findings reporting its surprising success.  However, findings to date appear to be implicitly constrained to instances of low-problem density (the ratio of an instances constraints to variables).  Hence, considered instances are not representative of statistical likely examples, and are only representative of the low-density subset. It is precisely this low-density subset which appears not to exhibit reachability deficits.  

Although the decision version of 2-SAT differs considerably from 3-SAT (complexity classes P and NP-Complete respectively), their optimization versions, MAX-2-SAT and MAX-3-SAT (both NP-Hard) show a remarkable similarity in critical QAOA depth requirement (see Fig. <ref>).   

We observe that instances with relatively low clause density require low depth QAOA circuits when compared to high density instances to approximate the minimum of an objective function up-to a given accuracy. Treating the critical QAOA depth as the computational cost, this crossover from low depth to high depth circuits is similar to the behaviour of computational resources reported for classical MAX-SAT solvers <cit.>. Indeed the exhibited point of this crossover in MAX-SAT <cit.> is rather different from the computational phase transition point in Boolean satisfiability, further investigations are necessary in order to report a MAX-SAT phase transition in QAOA.




10

mcclean2018barren
Jarrod R McClean, Sergio Boixo, Vadim N Smelyanskiy, Ryan Babbush, and Hartmut
  Neven.
Barren plateaus in quantum neural network training landscapes.
Nature communications, 9(1):4812, 2018.

hastings2019classical
Matthew B Hastings.
Classical and quantum bounded depth approximation algorithms.
arXiv preprint arXiv:1905.07047, 2019.

Peruzzo2014
Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou,
  Peter J. Love, Alán Aspuru-Guzik, and Jeremy L. O'Brien.
A variational eigenvalue solver on a photonic quantum processor.
Nature Communications, 5(1), July 2014.

dicarlo2009demonstration
Leonardo DiCarlo, Jerry M Chow, Jay M Gambetta, Lev S Bishop, Blake R Johnson,
  DI Schuster, J Majer, Alexandre Blais, L Frunzio, SM Girvin, et al.
Demonstration of two-qubit algorithms with a superconducting quantum
  processor.
Nature, 460(7252):240, 2009.

debnath2016demonstration
Shantanu Debnath, Norbert M Linke, Caroline Figgatt, Kevin A Landsman, Kevin
  Wright, and Christopher Monroe.
Demonstration of a small programmable quantum computer with atomic
  qubits.
Nature, 536(7614):63, 2016.

barends2016digitized
Rami Barends, Alireza Shabani, Lucas Lamata, Julian Kelly, Antonio Mezzacapo,
  Urtzi Las Heras, Ryan Babbush, Austin G Fowler, Brooks Campbell, Yu Chen,
  et al.
Digitized adiabatic quantum computing with a superconducting circuit.
Nature, 534(7606):222, 2016.

farhi2014quantum
Edward Farhi, Jeffrey Goldstone, and Sam Gutmann.
A quantum approximate optimization algorithm.
arXiv preprint arXiv:1411.4028, 2014.

wang2018quantum
Zhihui Wang, Stuart Hadfield, Zhang Jiang, and Eleanor G Rieffel.
Quantum approximate optimization algorithm for maxcut: A fermionic
  view.
Physical Review A, 97(2):022304, 2018.

jiang2017
Zhang Jiang, Eleanor G. Rieffel, and Zhihui Wang.
Near-optimal quantum circuit for grover's unstructured search using a
  transverse field.
Phys. Rev. A, 95:062317, Jun 2017.

morales2018variational
Mauro ES Morales, Timur Tlyachev, and Jacob Biamonte.
Variational learning of grover's quantum search algorithm.
Physical Review A, 98(6):062333, 2018.

cook1971complexity
Stephen A Cook.
The complexity of theorem-proving procedures.
In Proceedings of the third annual ACM symposium on Theory of
  computing, pages 151–158. ACM, 1971.

kadowaki1998quantum
Tadashi Kadowaki and Hidetoshi Nishimori.
Quantum annealing in the transverse Ising model.
Physical Review E, 58(5):5355, 1998.

krom1967decision
Melven R Krom.
The decision problem for a class of first-order formulas in which all
  disjunctions are binary.
Mathematical Logic Quarterly, 13(1-2):15–20, 1967.

goerdt1996threshold
Andreas Goerdt.
A threshold for unsatisfiability.
Journal of Computer and System Sciences, 53(3):469–486, 1996.

crawford1993experimental
James M Crawford and Larry D Auton.
Experimental results on the crossover point in satisfiability
  problems.
In Artificial Intelligence, volume 81, pages 31–57, 1996.

lucas2014ising
Andrew Lucas.
Ising formulations of many NP problems.
Frontiers in Physics, 2:5, 2014.

whitfield2012ground
James Daniel Whitfield, Mauro Faccin, and JD Biamonte.
Ground-state spin logic.
EPL (Europhysics Letters), 99(5):57004, 2012.

biamonte2008nonperturbative
JD Biamonte.
Nonperturbative k-body to two-body commuting conversion
  Hamiltonians and embedding problem instances into Ising spins.
Physical Review A, 77(5):052331, 2008.

grover1996fast
Lov K Grover.
A fast quantum mechanical algorithm for database search.
arXiv preprint quant-ph/9605043, 1996.



haastad2001some
Johan Håstad.
Some optimal inapproximability results.
Journal of the ACM (JACM), 48(4):798–859, 2001.

zhang2001phase
Weixiong Zhang.
Phase transitions and backbones of 3-sat and maximum 3-sat.
In International Conference on Principles and Practice of
  Constraint Programming, pages 153–167. Springer, 2001.

coppersmith2004random
Don Coppersmith, David Gamarnik, MohammadTaghi Hajiaghayi, and Gregory B
  Sorkin.
Random max sat, random max cut, and their phase transitions.
Random Structures & Algorithms, 24(4):502–545, 2004.





*


  

















