Progress toward favorable landscapes in quantum combinatorial optimization

The performance of variational quantum algorithms relies on the success of using quantum and classical computing resources in tandem. Here, we study how these quantum and classical components interrelate. In particular, we focus on algorithms for solving the combinatorial optimization problem MaxCut, and study how the structure of the classical optimization landscape relates to the quantum circuit used to evaluate the MaxCut objective function. In order to analytically characterize the impact of quantum features on the critical points of the landscape, we consider a family of quantum circuit ansätze composed of mutually commuting elements. We identify multiqubit operations as a key resource and show that overparameterization allows for obtaining favorable landscapes. Namely, we prove that an ansatz from this family containing exponentially many variational parameters yields a landscape free of local optima for generic graphs. However, we further prove that these ansätze do not offer superpolynomial advantages over purely classical MaxCut algorithms. We then present a series of numerical experiments illustrating that noncommutativity and entanglement are important features for improving algorithm performance.

Figure 1

Pictorial representation of how ansatz selection can be informed by the interplay between the problem instance and the underlying optimization landscape structure for solving the MaxCut problem. In particular, the graph structure (a) can be utilized to guide the development of an ansatz (b) for a VQA that yields favorable landscape properties (c), resulting in enhanced convergence. Here, we introduce a family of ansätze as a toy model that allows for analytically studying the associated landscape critical point structure, and prove that an ansatz from this family containing exponentially many variational parameters yields a landscape that is free of local optima. We go on to use this ansatz family as a starting point for exploring relations between inclusion of quantum features in ansätze, scalability, and VQA performance.

Figure 2

Purely classical algorithm for solving MaxCut. Start with a random bipartition $(A_0,A_0^c)$ of the vertices $V$. Then, iteratively construct new bipartitions $(A_1,A_1^c),(A_2,A_2^c),...,(A_m,A_m^c)$. At each iteration $j=1,\cdots ,m$, pick an ansatz element $S_k\in \mathcal{A}$. Beginning with an ansatz element labeled by $k=0$, implement the $\mathsf{flip}\left(S_k\right)$ operation by flipping the assignments of each vertex in $S_k$ to obtain $A_j\oplus S_k$ and $A_j^c\oplus S_k$. If $\mathsf{flip}\left(S_k\right)$ increases the CutVal such that $\mathsf{CutVal}(A_j\oplus S_k)>\mathsf{CutVal}\left(A_j\right)$ (or, equivalently, decreases the objective function $J$), then increment $j$ and set $A_{j+1}=A_j\oplus S_k$ and $A_{j+1}^c=A_j^c\oplus S_k$ and return to $k=0$. Otherwise, increment $k$ and repeat the flip operation until $\mathsf{CutVal}(A_j\oplus S_k)>\mathsf{CutVal}\left(A_j\right)$ is satisfied. Continue this procedure until a bipartition $(A_m,A_m^c)$ is reached such that $\mathsf{CutVal}\left(A_m\right)$ cannot be increased any further by a single flip.

Figure 3

The performance of the $\mathbb{X}$-ansatz, whose circuit diagram is shown in panel (a), for solving MaxCut on complete graphs is shown in panel (b). In panel (a), boxes represent variational ansatz elements. Connected boxes represent entangling ansatz elements that are generated by $k$-body $X$ operators acting nontrivially on $k$ “boxed” qubits. In panel (b), the approximation ratio is shown as a function of the $k$-body depth for different problem sizes $n$. The circles correspond to the average taken over 100 randomly chosen graph instances and BFGS initial conditions. The shaded areas show the corresponding standard deviations. The gray dashed line indicates the threshold for when better approximation ratios than the classical ansatz (10) are achieved.

Figure 4

The role of noncommutativity is assessed by introducing variational ansatz elements generated by Pauli $Z$ operators into the $\mathbb{X}$-ansatz. This is achieved by alternating between ansatz elements generated by $k$-body $X$ (orange) and (a) $k$-body $Z$ (green) operators and (b) single-qubit $Z$ operators (blue). In panel (c), the approximation ratio is shown as a function of the $k$-body depth for $n=8$ qubits. The circles and triangles correspond to the average taken over 100 randomly chosen complete graphs and BFGS initial conditions. The shaded areas show the corresponding standard deviations.

Figure 5

A comparison of different versions of QAOA with the $\mathbb{X}$- and $\mathbb{XZ}$-ansätze for $n=8$ qubits is shown. The circles and triangles correspond to the average approximation ratio taken over 100 randomly chosen complete graphs and BFGS initial conditions. The shaded areas show the corresponding standard deviations.

Figure 6

Comparison between the performance of the classical ansatz (10) coupled with a BFGS algorithm and the performance of the GW algorithm. The ratio between the two corresponding approximation ratios ${\alpha }_{\text{grad}}$ and ${\alpha }_{\text{GW}}$ is shown as a function of the vertex degree of a $k$-regular graph for $n=30,50,70$. Each data point shows the average value of ${\alpha }_{\text{grad}}/{\alpha }_{\text{GW}}$ taken over 200 different graph realizations, and the associated shaded area shows the standard deviation. The straight red line indicates when BFGS and (10) performs better, on average, than the GW algorithm.