Entanglement perspective on the quantum approximate optimization algorithm

Many quantum algorithms seek to output a specific bitstring solving the problem of interest—or a few if the solution is degenerate. It is the case for the quantum approximate optimization algorithm (QAOA) in the limit of large circuit depth, which aims to solve quadratic unconstrained binary optimization problems. Hence, the expected final state for these algorithms is either a product state or a low-entangled superposition involving a few bitstrings. What happens in between the initial $N$-qubit product state ${|0\rangle }^{\otimes N}$ and the final one regarding entanglement? Here, we consider the QAOA algorithm for solving the paradigmatic MaxCut problem on different types of graphs. We study the entanglement growth and spread resulting from randomized and optimized QAOA circuits and find that there is a volume-law entanglement barrier between the initial and final states. We also investigate the entanglement spectrum in connection with random matrix theory. In addition, we compare the entanglement production with a quantum annealing protocol aiming to solve the same MaxCut problems. Finally, we discuss the implications of our results for the simulation of QAOA circuits with tensor network-based methods relying on low-entanglement for efficiency, such as matrix product states.

Figure 1

(a) Sketch of the bipartite entanglement entropy $S$ as a function of the QAOA layer for solving a generic MaxCut problem. The initial state is a product state with $S=0$. In the limit of a large number of layers, QAOA solves asymptotically the combinatorial problem of interest. Thus one expects the final state to be low-entangled. In intermediate steps, optimized QAOA circuits generate volume-law entanglement $S\sim N$ with $N$ the number of qubits. (b) A QAOA circuit according to Eq. (2) with layers $\ell \le p$. We used $U_{{\beta }_{\ell }}={\prod }_j{u}_{{\beta }_{\ell }}$ with $u_{{\beta }_{\ell }}$ acting on individual qubits according to Eq. (3).

Figure 2

Sketch of the graphs considered in this paper with $N=8$ vertices. (a) Linear graph. (b) A 3-regular graph. (c) Complete graph.

Figure 3

Data averaged over ${10}^3$ problems and randomized QAOA circuits. The statistical error bars are smaller than the symbols and not displayed. (a)–(c) Growth of the bipartite von Neumann entanglement entropy $S$ defined in Eq. (6) versus the number of randomized QAOA layers $\ell$. (a) Linear graphs. (b) Complete graphs. (c) 3-regular graphs. The straight dashed line corresponds to the saturation value following Eq. (7). (a) For $\ell \lesssim N^2$, the entanglement in the linear graphs shows a diffusive growth $\propto \sqrt{\ell }$ with a size-independent prefactor. (b) In complete graphs, the saturation happens after a number of QAOA layers of order one. (c) Based on the properties of 3-regular graphs, we expect the entanglement to saturate for ${\ell }_{\mathrm{sat}}\sim lnN$, corresponding to the average shortest path between two vertices. (d) Average shortest path length in 3-regular graphs as a function of the graph size $N$. Each data point is averaged over ${10}^3$ random graphs. For $N\to +\infty$, we observe that the average shortest path grows as $\sim lnN$. For smaller graphs, the average shortest path length is larger than the genuine thermodynamic behavior. (e) For 3-regular graphs, at fixed $\ell$, we show the entanglement growth as a function of size $N$. Straight lines are linear fits of the form $a\left(\ell \right)+b\left(\ell \right)N$ with $a$ and $b\ell$-dependent fitting parameters for $\ell \lesssim {\ell }_{\mathrm{sat}}$. (f) Fitting parameter $b\left(\ell \right)$ showing a behavior compatible with a logarithmic dependence.

Figure 4

(a)–(c) Distribution $P\left(r\right)$ of the adjacent gap ratio defined in Eq. (9) for (a) linear graphs, (b) complete graphs, and (c) 3-regular graphs of size $N=18$, 20, and 22, computed after saturation of the entanglement entropy. (a) The distribution shows a Poisson law, expected for the output of a free-fermionic circuit, see Eq. (10). (b), (c) The distribution shows a GUE law with ${\mathbb{Z}}_2$ symmetry [90]. (d) Average entanglement spectrum (note the scaling by $2^{N/2}$ of the $x$ and $y$ axes, corresponding to the number of Schmidt coefficients) for the different graphs considered, computed after saturation of the entanglement entropy. Data averaged over ${10}^3$ problems and randomized QAOA circuits. The statistical error bars are smaller than the symbols and not displayed. The entanglement spectrum of the complete and 3-regular graphs are shown for $N=22$ and follow the Marchenko-Pastur of Eq. (8). The entanglement spectrum of linear graphs behave differently due to the free-fermionic nature of the QAOA circuit in that case. Finite-size effects are visible (data shown for $N=18$, 20, and 22). (e) Average adjacent gap ratio $\overline{r}$ as a function of the system size $N$. The Poisson value ${\overline{r}}_{\mathrm{Poisson}}=2ln2-1\simeq 0.38629$ and GUE value with ${\mathbb{Z}}_2$ symmetry ${\overline{r}}_{\mathrm{GUE}-{\mathbb{Z}}_2}=0.422085$ [90] are also plotted.

Figure 5

Data averaged over ${10}^2$ problems. The statistical error bars are smaller than the symbols and not displayed. (a), (d) Linear graphs. (b), (e) Complete graphs. (c), (f) 3-regular graphs. Left column: Average bipartite von Neumann entanglement entropy as defined in Eq. (6) versus the number of optimized QAOA layers $\ell \le p$ for various QAOA depths $p$. The system size considered is $N=16$. The entanglement in the case of randomized QAOA layer is also displayed. Right column: The data displayed in the left column is generated for various sizes $N$. For each curve $(N,p)$, the maximum value taken by the entropy $S$ as a function of $\ell$ is extracted: It is then plotted on the right column as a function of the system size $N$. The value taken by the entanglement at saturation ($p\to +\infty$) for randomized QAOA circuits, see Eq. (7), is shown for comparison. Plain lines are linear fits of the form $a\left(p\right)+b\left(p\right)N$ with $a\left(p\right)$ and $b\left(p\right)$ fitting parameters.

Figure 6

Data averaged over ${10}^2$ problems. The statistical error bars are smaller than the symbols and not displayed. (a) (b) (c) Average entanglement spectrum for $N=16$ computed at the end of optimized QAOA circuits ($p=\ell$) for various QAOA depths $p$. The average entanglement spectrum in the randomized QAOA case for $N=16$ computed once the entanglement entropy has reached its saturation value is also displayed. (a) Linear graphs. (b) Complete graphs. (c) 3-regular graphs. (d) Average entanglement spectrum for $N=16$ and $p=\ell =10$ for the three different graphs considered in this paper. The dashed line corresponds to the Marchenko-Pastur distribution of Eq. (8), where the curve has been vertically adjusted to fall over the QAOA data.

Figure 7

Data averaged over ${10}^3$ problems. The statistical error bars are smaller than the symbols and not displayed. (a), (d) Linear graphs. (b), (e) Complete graphs. (c), (f) 3-regular graphs. Left column: Average bipartite von Neumann entanglement entropy for $N=16$ computed as a function of the time $t$ for various total evolution times $T$ following Eqs. (11) and (13). Right column: The data displayed in the left column is generated for various sizes $N$. For each curve $(N,T)$, the maximum value taken by the entropy $S$ as a function of $t$ is extracted: It is then plotted on the right column as a function of system size $N$. The value taken by the entanglement at saturation for randomized QAOA circuits ($p\to +\infty$), see Eq. (7), is shown for comparison. Plain lines are linear fits of the form $a\left(T\right)+b\left(T\right)N$ with $a\left(T\right)$ and $b\left(T\right)$ fitting parameters. (g) Fitting parameter $b\left(T\right)$ for 3-regular and complete graphs showing an algebraic decay $\propto T^{-\alpha }$ with $\alpha \approx 0.5$.