# Information scrambling and entanglement in quantum approximate optimization
algorithm circuits

Chen Qian<EMAIL_ADDRESS>Beijing Academy of Quantum Information
Sciences, Beijing 100193, China  State Key Laboratory of Low Dimensional
Quantum Physics, Department of Physics, Tsinghua University, Beijing, 100084,
China  Wei-Feng Zhuang  Beijing Academy of Quantum Information Sciences,
Beijing 100193, China  Rui-Cheng Guo  State Key Laboratory of Low Dimensional
Quantum Physics, Department of Physics, Tsinghua University, Beijing, 100084,
China  Meng-Jun Hu  Beijing Academy of Quantum Information Sciences, Beijing
100193, China  Dong E. Liu<EMAIL_ADDRESS>Beijing Academy of
Quantum Information Sciences, Beijing 100193, China  State Key Laboratory of
Low Dimensional Quantum Physics, Department of Physics, Tsinghua University,
Beijing, 100084, China  Frontier Science Center for Quantum Information,
Beijing 100184, China

###### Abstract

Variational quantum algorithms, which consist of optimal parameterized quantum
circuits, are promising for demonstrating quantum advantages in the noisy
intermediate-scale quantum (NISQ) era. Apart from classical computational
resources, different kinds of quantum resources have their contributions in
the process of computing, such as information scrambling and entanglement.
Characterizing the relation between complexity of specific problems and
quantum resources consumed by solving these problems is helpful for us to
understand the structure of VQAs in the context of quantum information
processing. In this work, we focus on the quantum approximate optimization
algorithm (QAOA), which aims to solve combinatorial optimization problems. We
study information scrambling and entanglement in QAOA circuits respectively,
and discover that for a harder problem, more quantum resource is required for
the QAOA circuit to obtain the solution. We note that in the future, our
results can be used to benchmark complexity of quantum many-body problems by
information scrambling or entanglement accumulation in the computing process.

##  I Introduction

Quantum computation is considered to have a crucial computational speed-up
compared with classical computing, because it consumes not only classical
computational resources but also quantum resources [1]. As the most important
feature of quantum mechanics, entanglement offers essential resource for
quantum computation [2, 3]. Besides, since quantum circuits are actually
unitary channels, the quantity characterizing spatiotemporal entanglement
properties of a channel, namely information scrambling, should be viewed as a
considerable resource as well [4, 5, 6, 7, 8]. The concept of information
scrambling was first introduced by Hayden and Preskill [9] to demonstrate that
the quantum information of a diary thrown into a black hole will spread to the
whole system, and finally recover from the black hole evaporation. In last
decades, studies of this physical process mostly focus on the area of black
hole information and quantum gravity [10, 11]. Recently, more and more works
turn their attention to information scrambling in quantum circuits, which pave
the way to applications involving benchmarking noise [12], recovering lost
information [13], characterizing performance of quantum neural networks [14,
15, 16], unifying chaos and random circuits [17, 18], and so on [19, 20]. In
addition, the process of information scrambling is observed experimentally on
superconducting quantum processors [21, 22]. Briefly, studying information
scrambling and entanglement properties offers us an overview of how much
quantum resource is needed for specific quantum circuits.

Variational quantum algorithms (VQAs) belong to the leading strategies to
potentially present quantum advantage on near-term NISQ devices [5], which
include a series of algorithms such as variational quantum eigensolver (VQE)
[23], quantum machine learning (QML) [24] and quantum approximate optimization
algorithm (QAOA) [25]. VQAs share the common structure of optimizing
parameters with a classical optimizer and running parameterized quantum
circuits to solve problems. In particular, QAOA is proposed to solve the
quadratic unconstrained binary optimization (QUBO) problems [26], which can be
translated into computing minimal expectation values of an Ising Hamiltonian.
Based on these settings, QAOA is widely applied in combinatorial optimization
problems, e.g., traffic congestion, finance, and many-body physics [27, 28].
It is useful to give a thorough analysis to the scrambling and entanglement
properties of the optimal parameterized quantum circuits in order to benchmark
the quantum resource consumed when we utilize VQAs to calculate a certain
problem.

The role of entanglement for VQAs has been extensively studied from different
perspectives [29, 30, 31, 32, 33]. In recent papers, bipartite entanglement
entropy in $p$-layer QAOA circuits was investigated. Chen, _et al._ compared
the entanglement required between ADAPT-QAOA and standard QAOA solving certain
problems [31], and Dupont, _et al._ characterize entanglement generated in
QAOA circuit with entanglement volume law [32]. However, details about
entanglement generation in the $p$-layer circuit and its connection to
complexity of problems still remains an open question. Moreover, in the aspect
of information scrambling, Shen, _et al._ established a correlation between
scrambling ability and loss function in the training process of quantum neural
networks [14], which raises an interesting question of whether a comparable
correlation occurs in QAOA.

Therefore, our aim in this paper is to investigate the connection between
complexity of QUBO problems and quantum resource (including information
scrambling and entanglement) consumed in the QAOA circuits. In this work, we
address a special type of QUBO problems whose solutions are non-degenerate in
order to concentrate on the quantum resource generated during the computing
process. When we embed these solutions to quantum circuits, the target states
are product states. Since both initial and final states have no entanglement,
all quantum resource generated in the circuit is only for computing steps. As
we have fixed all basic settings of the optimization algorithm, we can build a
clear link between the amount of quantum resources used in QAOA circuits and
the complexity to solve QUBO problems.

Next, we need to discriminate the concept “complexity of QUBO problems”. This
concept includes two different definitions [26]:

1\. The complexity to solve a QUBO problem mathematically, which is highly
dependent on structure of the graph.

2\. The computational complexity of solving a QUBO problem using certain
algorithms. Both algorithm and properties of the graph are relevant to this
computational complexity.

The two complexities may not have a definitive correlation. In this work, we
only discuss solving QUBO problems via QAOA, thus we take the second
definition to “complexity of QUBO problems” throughout the paper. Although a
general mathematical expression of computational complexity of solving QUBO
problems via QAOA is still an open question, we find it may be determined by
some important attributes of a QUBO graph, like

$\mathcal{C}\sim f\left(D,w_{ij},h_{k}\right),$ (1)

where $D$ is the density of a graph, $w_{ij}$ and $h_{k}$ are weights of edges
and nodes of the graph, detailed definitions are introduced in Sec. II.1.

Based on all above settings, we present our results in two parts: Firstly, we
treat the QAOA circuit as a quantum channel to compare information scrambling
characterized by tripartite information with QAOA computational complexity
characterized by success rates, and our results are obtained for three
different kinds of QUBO problems. Secondly, we compare entanglement
accumulation in QAOA circuit with five QUBO problems where the corresponding
graphs have different edges but the weights of edges and nodes are the same.
Notably, we propose a quantity to characterize entanglement accumulation
inside QAOA circuit, which has the form of average area of entanglement
entropy generated during the evolution of the quantum circuit. Finally, we
claim that for every cases we consider, there exists a remarkable positive
correlation between the complexity of QUBO problems and information
scrambling, as well as between the complexity and entanglement.

In what follows, we first briefly review the background of QAOA and tripartite
information and introduce our implementation in Sec. II, and then compare
information scrambling and entanglement entropy with complexity of problems in
Sec. III and Sec. IV respectively. At last, we discuss our results and provide
future lines of research in Sec. V.

##  II Preliminaries

In this section, we briefly review the basic concepts on QAOA and tripartite
mutual information describing information scrambling. After that, we introduce
our basic settings in this work.

###  II.1 The quantum approximate optimization algorithm

As we discussed in Sec. I, QAOA is a quantum algorithm aiming to solve
combinatorial optimization problems, which was first brought by Farhi, _et
al._ [25]. Usually, a combinatorial optimization problem can be represented by
a QUBO model, where we can associate a weighted graph $G=\left(V,E\right)$
with nodes $V=\left\\{1,2,\cdots,N\right\\}$ and edges
$E=\left\\{\left(i,j\right),i\neq j\right\\}$. In this graph, the weight of
the edge $\left\\{i,j\right\\}$ is denoted by $w_{ij}$, and the weight of the
node $k$ is denoted by $h_{k}$. Connection property of the graph can be
characterized by density of the graph:

$D=\frac{2E}{N(N-1)},$ (2)

where $E$ is the number of edges and $N(N-1)/2$ is the maximal potential
connections. The graph can be mapped into an Ising model in quantum many-body
physics with $V$ represents independent terms $Z_{i}$ and $E$ represents
interaction terms $Z_{i}Z_{j}$. Therefore, the most general form of an Ising
Hamiltonian reads

$H_{C}=\mathop{\sum_{i,j=1}^{N}w_{ij}Z_{i}Z_{j}+\sum_{k=1}^{N}h_{k}Z_{k}\,},$
(3)

where $Z_{i}$ are $\sigma_{z}$ operators with eigenvalues $\pm 1$, $w_{ij}$
and $h_{k}$ are coupling strengths of the interaction and independent terms.
The target of QAOA is to achieve the minimal quantum mean value $\left\langle
H_{C}\right\rangle$ via optimized parameters. Here, the QAOA circuit with
$p$-layer and $2p$ parameters is as follows

$\left|\vec{\beta},\vec{\gamma}\right\rangle=U_{B}\left(\beta_{p}\right)U_{C}\left(\gamma_{p}\right)\cdots
U_{B}\left(\beta_{1}\right)U_{C}\left(\gamma_{1}\right)\mathrm{H}^{\otimes
N}\left|0\right\rangle^{\otimes N}\,,$ (4)

where $U_{B}\left(\beta_{i}\right)=e^{-i\beta_{i}H_{B}}$,
$H_{B}=\sum_{i=1}^{N}X_{i}$,
$U_{C}\left(\gamma_{i}\right)=e^{-i\gamma_{i}H_{C}}$, and $\mathrm{H}$ means
Hardmard gate. The $2p$ parameters
$\vec{\beta}=\left(\beta_{1},\beta_{2},\cdots\beta_{p}\right)$ and
$\vec{\gamma}=\left(\gamma_{1},\gamma_{2},\cdots\gamma_{p}\right)$ are
optimized by classical optimization algorithm, after that they are applied to
the parameterized quantum circuit Eq. $\left(\ref{eq:QAOA-cir}\right)$ to
obtain a smaller mean value $\left\langle H_{C}\right\rangle$. When QAOA finds
the minimum of $\left\langle H_{C}\right\rangle$, it outputs a set of optimal
parameters $\left\\{\vec{\beta}_{opt},\vec{\gamma}_{opt}\right\\}$ at the same
time, here state $\left|\vec{\beta}_{opt},\vec{\gamma}_{opt}\right\rangle$ is
the ground state of Eq. $\left(\ref{eq:H_C}\right)$.

We note that $\left\\{\vec{\beta}_{opt},\vec{\gamma}_{opt}\right\\}$ has
multiple solutions for a certain $H_{C}$ as one choose different initial
parameters $\left\\{\vec{\beta}_{0},\vec{\gamma}_{0}\right\\}$. The choice of
$\left\\{\vec{\beta}_{0},\vec{\gamma}_{0}\right\\}$ may result in seeking
$\left\\{\vec{\beta}_{opt},\vec{\gamma}_{opt}\right\\}$ of the problem easier
or harder. Thus, to characterize properties of QAOA circuits solving the
problem $H_{C}$ with less bias, we should turn to statistical average values
of numerous samplings with random initial parameters.

###  II.2 Information scrambling and entanglement

The “butterfly effect” in quantum systems, where localized quantum information
spreads to degrees of freedom of the entire system as a result of a small
disturbance, is referred to as information scrambling. Hosur, _et al._ use
information scrambling to characterize the ability of a channel to process
quantum information, they quantify scrambling as tripartite mutual
information, which can be understood as entanglement between input and output
of the channel [4]. For any unitary channel $\hat{U}$ in a $N$-qubit Hilbert
space, it can be decomposed to

$\hat{U}=\sum_{i,j=1}^{2^{N}}U_{ij}\left|i\right\rangle\left\langle
j\right|\,,$ (5)

where $\left\\{\left|i\right\rangle\right\\}$is the basis of $2^{N}$ Hilbert
space. Denoting $\left\\{\left|i\right\rangle\right\\}$ as the basis of
$N$-qubit input legs and $\left\\{\left|j\right\rangle\right\\}$ as the basis
of $N$-qubit output legs, the unitary operator $\hat{U}$ can be mapped to a
state $\left|U\right\rangle$ in the form of

$\left|U\right\rangle=\sum_{i,j=1}^{2^{N}}\frac{U_{ij}}{\sqrt{2^{n}}}\left|i\right\rangle\left|j\right\rangle\,,$
(6)

which represents an entanglement state of input qubits and output qubits.
Since $\left|U\right\rangle$ is a pure entangled state, we can define
entanglement entropy between input and output states. Usually we divide the
input part into subsystems $A$ and $B$, and output part into $C$ and $D$, then
entanglement entropy of $AC$ reads

$S_{AC}=-\mathrm{Tr}\left(\rho_{AC}\mathrm{log}_{2}\rho_{AC}\right)\,,$ (7)

where $\rho_{AC}=\mathrm{Tr}_{BD}\left(\left|U\right\rangle\left\langle
U\right|\right)$. Similarly, mutual information between $A$ and $C$ can be
obtained as

$I\left(A:C\right)=S_{A}+S_{C}-S_{AC}\,,$ (8)

which can be understood as how much information from input subsystem $A$
spread into output subsystem $C$ via the channel $\hat{U}$. Considering
different conditions the information spreading from $A$ to $C$ and $D$,
tripartite mutual information is introduced with the form

$I_{3}\left(A:C:D\right)=I\left(A:C\right)+I\left(A:D\right)-I\left(A:CD\right)\,,$
(9)

which is well-defined to characterize information scrambling. If there is no
scrambling, all information of $A$ will be found in $C$ or $D$ (suppose
$\left|A\right|<\left|C\right|,\left|D\right|$), either $I\left(A:C\right)$ or
$I\left(A:D\right)$ equals to $I\left(A:CD\right)$ and another one equals to
zero, then Eq. $\left(\ref{eq:tri-info}\right)$ turns to be zero. If
information of $A$ is fully scrambled to the whole output system, we cannot
recover the information only by accessing $C$ or $D$, which means
$I\left(A:C\right)=I\left(A:D\right)\sim 0$, then we obtain
$I_{3}\left(A:C:D\right)\sim-I\left(A:CD\right)\sim-2\left|A\right|$.

Tripartite mutual information is also defined as topological entanglement
entropy in topological quantum field theory [34], which is topologically
invariant and represents a universal characterization of the many-body
entanglement in the ground state of a topologically ordered two-dimensional
system. Since time can be viewed as an additional dimension for quantum
unitary channels, tripartite mutual information is a good way to describe the
overall characteristics of entanglement in quantum channels.

###  II.3 Implementation

Here we introduce some settings throughout the paper. For QAOA circuit, we use
the package of Qcover to perform our simulations [35], the classical
optimization algorithm we choose is Constrained Optimization BY Linear
Approximation (COBYLA). The number of qubits of problems we consider is all
$N=7$.

By taking the QAOA circuits as unitary channels to study information
scrambling, we build up subsystems of $A$($\left|A\right|=1$),
$B$($\left|B\right|=6$), $C$($\left|C\right|=3$) and $D$($\left|D\right|=4$)
in Fig. 1. Denoting that there are $245$ combinations for $ABCD$ with the same
number of qubits, since QAOA circuits have no natural choice of these
subsystems. We have tried several other combinations and find even
$I_{3}\left(A:C:D\right)$ are different in values, the tendency in our results
is invariant. Because tripartite information is a universal quantity
describing scrambling ability of a channel, one choice is enough to reflect
properties of the circuit we work on.

To study entanglement properties in detail, we consider von Neumann
entanglement entropy of one qubit in the QAOA circuit. Since entanglement
entropy of one random qubit cannot imply the full structure of the
entanglement properties, we compute average values of Von-Neumann entropy for
every qubits in the form of

$\bar{S}=\frac{-\sum_{i=1}^{N}\mathrm{Tr}\left(\rho_{i}\mathrm{log}_{2}\rho_{i}\right)}{N}\;,$
(10)

where
$\rho_{i}=\mathrm{Tr}_{i}\left(\left|\vec{\beta}_{opt},\vec{\gamma}_{opt}\right\rangle\left\langle\vec{\beta}_{opt},\vec{\gamma}_{opt}\right|\right)$
is the reduced density matrix after tracing out $i$th qubit from final state
computed by QAOA.

Figure 1:  One layer of QAOA circuit and our choice of subsystems $ABCD$.

Finally, we come to a concrete definition of complexity of QUBO problems. We
have proposed the attributes relevant to complexity in Eq. $\left(\ref{eq:def-
complexity}\right)$, and now we need a corresponding function form deduced
from QAOA computing results to reflect the complexity. For a certain computing
result $\left|\vec{\beta}_{opt},\vec{\gamma}_{opt}\right\rangle$, we take the
distance between quantum mean value $\left\langle H_{C}\right\rangle$ and
exact solution of the problem $E_{C}$ to be [36, 37]

$\alpha=\frac{\left\langle H_{C}\right\rangle}{E_{C}}\;.$ (11)

The value was first introduced to benchmark the accuracy of approximate
optimization algorithms [38, 39]. As the initial parameters of QAOA are chosen
randomly, if we compute the same problem for different times, the final
parameters can be distinct from each other, which lead to different $\alpha$
values. We can only say, a harder problem has less probability for QAOA to
achieve a high $\alpha$ value. Thus, in this work we characterize complexity
of a QUBO problem as a statistical probability when the $\alpha$ value is
larger than a certain bound we expect in a number of samplings. That is, if we
sample a QUBO problem $n$ times and among them there are $s$ samples whose
$\alpha$ values larger than the bound we set, then we can define the
complexity of the problem to be the rate

$R=\frac{s}{n}\;,$ (12)

which is also named as “success rate” [30]. In ideal circumstances, this rate
should be positively correlated with complexity $\mathcal{C}$ as

$\mathcal{C}\propto R\;.$ (13)

However, some problems, such as local minima problem caused by gradient based
optimization algorithm [40], in QAOA may suppress $R$ and break the relation,
which will be discussed in Sec. III.

##  III Scrambling in QAOA circuit versus Complexity of the problems

In this section, we investigate quantum information scrambling in QAOA
circuits. The circuits are designed specially for solving QUBO problems with
non-degenerate solutions, whose corresponding Ising Hamiltonians $H_{C}$ have
separable ground states. As we have introduced in Sec. II.2, we take the
circuits as unitary channels and quantify scrambling ability of the channels
by tripartite information $I_{3}$. Our aim is to find some correlation between
complexity of the problems and tripartite information.

###  III.1 Comparison between different kinds of graphs

As a start of this subsection, we first go back to the function of complexity
Eq. $\left(\ref{eq:def-complexity}\right)$. As we have fixed the degeneracy of
QUBO solutions and basic settings of QAOA, the computational complexity of
QUBO problems should only relate to two factors: density of the graph $D$ and
weights of the graph $\left\\{w_{ij},h_{k}\right\\}$. In order to present a
clear comparison, in the following we choose three typical kinds of graphs:

1\. Linear graphs with their corresponding Ising Hamiltonians in the form of
$Z-ZZ$.

2\. Complete graphs with their corresponding Ising Hamiltonians in the form of
$Z-ZZ$.

3\. Linear graphs with their corresponding Ising Hamiltonians in the form of
$Z+ZZ$.

Among the three cases, the $1$st and $2$nd cases have fixed graph weights but
differ in graph density, whereas the $1$st and $3$rd cases have fixed graph
density but differ in weights. According to Eq. $\left(\ref{eq:prop-
complex}\right)$, we expect if we fix one factor and change the other, the
success rate $R$ will evolve monotonically.

_1\. Linear graph with $Z-ZZ$-type Hamiltonian:_ This kind of Ising
Hamiltonians have only neighborhood interactions, which have the form of

$H_{linear}=+w\sum_{i=1}^{N}Z_{i}-\sum_{i=1}^{N-1}Z_{i}Z_{i+1}\,,$ (14)

where $w$ is a weight parameter with $w\in\left[0.5,1.5\right]$. Since all
QUBO problems corresponding to this kind of graphs have non-degenerate
solutions, their Ising Hamiltonians share the same ground states
$\left|1\right\rangle^{\otimes N}$. As is shown in Fig. 2(a), success rate $R$
increases as the number of layers in QAOA circuit increases, and then becomes
saturated after $p\sim 6$. From Fig. 2(b) we note that even $I_{3}$ is very
small, the positive correlation between $\left|I_{3}\right|$ and success rates
is still visible.

To quantify the correlation, we introduce Pearson correlation coefficient
here. Generally, Given two data sets $X$ and $Y$, the correlation between them
can be characterized by

$\rho_{XY}=\frac{\sigma_{XY}}{\sigma_{X}\sigma_{Y}}\,,$ (15)

where $\sigma_{XY}$ is their covariance, $\sigma_{X}$ and $\sigma_{Y}$ are
their own variances. If two data sets have positive correlation, Pearson
correlation coefficient takes the range of $(0,1]$. Now, by taking the data of
$\left|I_{3}\right|$ and $R$ in Fig. 2(b), we can obtain the Pearson
correlation coefficient $\rho_{I_{3}R}\approx 0.4297$, which indicates an
obvious positive correlation.

Figure 2:  The comparison between success rates to solve $\left\langle
H_{linear}\right\rangle_{min}$ and information scrambling in the circuits with
number of qubits $N=7$ for the _linear_ model of $Z-ZZ$-type Hamiltonians.
Here $w\in\left[0.5,1.5\right]$, we randomly choose $15$ different weights.
(a). In this figure, each point represents a $p$-layer QAOA circuit to compute
$\left\langle H_{linear}\right\rangle_{min}$ with one randomly chosen $w$. We
loop the QAOA circuit $10^{2}$ times, use Eq.
$\left(\ref{eq:complexity}\right)$ to obtain a success rate (orange point),
and take an average value of $I_{3}$ (dark green point). We keep using these
settings in all following $R-p$ and $I_{3}-p$ figures. The orange lines are
success rates of QAOA with different layers, where we set $\alpha\geq 0.996$,
and entanglement entropy of $C$ and $D$ in final state $\leq 0.02$. There are
$15$ lines in the figure, representing $15$ problems solved by QAOA with
different weights $w$. The dark green lines are average values of
$\left|I_{3}\right|$ in these QAOA circuits corresponding to the orange lines.
(b). Using the data from (a), we show a correlation plot for $R$ and
$\left|I_{3}\right|$ from the same circuit (same $p$ and $w$).

_2\. Complete graph with $Z-ZZ$-type Hamiltonian:_ For complete graphs, the
corresponding Ising Hamiltonians are

$H_{complete}=+w\sum_{i=1}^{N}Z_{i}-\sum_{i,j=1,i\neq j}^{N}Z_{i}Z_{j}\,,$
(16)

where $w\in\left[0.5,1.5\right]$ and each pair of nodes is connected by an
edge. See Fig. 3(a) we can find that, looking for the minimal mean value of
Eq. $\left(\ref{eq:H-complete-exact}\right)$ is much harder than Eq.
$\left(\ref{eq:H-line-exact}\right)$, since the success rates are much lower
compared with the linear case especially for small layers. In this case, Eq.
$\left(\ref{eq:H-complete-exact}\right)$ have the same range of weights as Eq.
$\left(\ref{eq:H-line-exact}\right)$, but the graph density is much larger
than Eq. $\left(\ref{eq:H-line-exact}\right)$. It seems when we fix the
weights, more connections make the QUBO problems harder to solve. About this
issue, more details will be discussed in the next subsection. The success
rates grow fast after $p\sim 8$, tripartite information also grows to about
$-1.86$ simultaneously. From Sec. II.2 we have known the maximal tripartite
information $I_{3}(A:C:D)$ is $-\left|A\right|\sim-2$, this means information
encoded in the initial state $\left|+\right\rangle^{\otimes N}$ should be
sufficiently scrambled to reach the exact final state
$\left|1\right\rangle^{\otimes N}$ in the computing process.

Figure 3:  The comparison between success rates for $p$-layer QAOA to compute
$\left\langle H_{complete}\right\rangle_{min}$ and information scrambling in
the circuit for different layers with number of qubits $N=7$ for the
_complete_ model with $Z-ZZ$-type Hamiltonians. Here
$w\in\left[0.5,1.5\right]$, we randomly choose $15$ $w$s, and we take $10^{2}$
loops as well. (a). The orange lines are success rates of QAOA of different
layers to compute $\left\langle H_{complete}\right\rangle_{min}$ with
different $w$s, with the condition $\alpha\geq 0.996$, and entanglement
entropy of $C$ and $D$ in final state $\leq 0.02$. The dark green lines are
$\left|I_{3}\right|$ in these QAOA circuits corresponding to the orange lines.
(b). Using the data from (a), we show a correlation plot for $R$ and
$\left|I_{3}\right|$ from the same circuit.

Moreover, a positive correlation is also presented in Fig. 3(b). Using Eq.
$\left(\ref{eq:correlator}\right)$ we know Pearson correlation coefficient in
this case is $\rho_{I_{3}R}\approx 0.6581$. The correlation between tripartite
information $I_{3}$ and success rate $R$ seems stronger than the above linear
graph case. This phenomenon can be observed in Fig. 2 and Fig. 3, as the layer
$p$ goes on, $R$ stops increasing at some value in Fig. 2(a) whereas $R$ in
Fig. 3(a) keeps increasing. Ideally, in a QAOA circuit, more layers indicate a
more optimal result, and therefore a larger $R$ value. However, the classical
optimization algorithm of QAOA is gradient based, when the function is complex
and has many parameters, the minima evaluated by gradients may be far from the
global minimum [40]. This problem is an obstacle of all VQAs. For QAOA, more
layers bring a larger optimal parameter space, which may leads to more local
minima and suppress the value of $R$.

_3\. Linear graph with $Z+ZZ$-type Hamiltonian:_ Now we study linear graphs
with very different weights from Eq. $\left(\ref{eq:H-line-exact}\right)$,
namely

$H^{\prime}_{linear}=+\sum_{i=1}^{N}Z_{i}+v\sum_{i,i+1}^{N-1}Z_{i}Z_{i+1}\,,$
(17)

where $v\in\left[2,3\right]$ is the weight of edges $ZZ$. Unlike above cases,
it is not easy to find the ground state at first glance. Among all $128$ basis
of the $7$-qubit system, we find the product state
$\left|1010101\right\rangle$ makes Eq. $\left(\ref{eq:H-line-hard}\right)$
take the minimal mean value.

Figure 4: The comparison between success rates for $p$-layer QAOA to compute
$\left\langle H^{\prime}_{linear}\right\rangle_{min}$ and information
scrambling in the circuit for different layers with number of qubits $N=7$ for
the _linear_ model with $Z+ZZ$-type Hamiltonians. Here $v\in\left[2,3\right]$,
we randomly choose $15$ $v$s, and we take $10^{2}$ loops as well. (a). The
orange lines are success rates of QAOA of different layers to compute
$\left\langle H^{\prime}_{linear}\right\rangle_{min}$ with different $v$s,
with the condition $\alpha\geq 0.96$, and entanglement entropy of $C$ and $D$
in final state $\leq 0.25$. The dark green lines are $\left|I_{3}\right|$ in
these QAOA circuits corresponding to the orange lines. (b). Using the data
from (a), we show a correlation plot for $R$ and $\left|I_{3}\right|$ from the
same circuit.

As is shown in Fig. 4, success rate (we set $\alpha>0.96$) are $\sim 0$ before
$p=15$, even when $p>15$ the probabilities are much smaller than above cases.
Compared with Fig. 2, it is much harder to obtain a good result of ground
state energy, and it seems more tripartite information is generated in the
circuit. We note that, density of the graph $D$ of Eq. $\left(\ref{eq:H-line-
hard}\right)$ is the same as Eq. $\left(\ref{eq:H-line-exact}\right)$, however
different weights seem have a large contribution to complexity of the
problems. With $D$ fixed, we propose the complexity $\mathcal{C}$ can be
expressed as

$\mathcal{C}\propto g\left(w_{ij},h_{k}\right)\,,$ (18)

where $g\left(w_{ij},h_{k}\right)$ only depends on weights of the graph. For
the correlation between success rate and information scrambling, we get the
Pearson correlation coefficient between tripartite information and success
rate of Eq. $\left(\ref{eq:H-line-hard}\right)$ is $\rho_{I_{3}R}\approx
0.4461$. The correlation strength is similar to the first linear graph case.

To summarize, in this section we compare information scrambling in QAOA
circuits with their corresponding success rates, which reflect the complexity
of solving three different kinds of QUBO problems via QAOA. By comparing
success rates $R$ in the three cases, we find it is sensitive to both factors
of QUBO complexity $\mathcal{C}$, i.e. density of the graph $D$ and weights of
the graph $\left\\{w_{ij},h_{k}\right\\}$. From those results, an overall
positive correlation between tripartite information and complexity of the
problems can be observed in the three kinds of graphs. Additionally, the forth
case, complete graph with $Z+ZZ$-type Hamiltonians, should also be considered
naturally. However, it’s hard to find a non-degenerate solution, which cannot
be mapped to a product ground state like above three cases. This could imply
that for particular weights, it’s difficult to avoid degeneracy in solutions,
especially when the graph density is high.

###  III.2 Comparison between different edges of graphs

In this subsection, we explore a more direct way to characterize the
complexity of problems. If we fix weights of the graphs, the complexity Eq.
$\left(\ref{eq:def-complexity}\right)$ has only one variable, density of the
graphs $D$. Since in this work we only discuss $N=7$, thus $D$ can be
expressed by the number of edges $E$ according to Eq.
$\left(\ref{eq:density}\right)$. Then we can propose a relation between
complexity and number of edges:

$\mathcal{C}\propto E\;,$ (19)

when $\left\\{w_{ij},h_{k}\right\\}$ are fixed. To verify this correlation,
next we focus on a set of graphs with fixed weights and different number of
edges, whose corresponding Ising Hamiltonians are $Z-ZZ$-type:

$H_{1}=+\sum_{i=1}^{N}Z_{i}-\sum_{i=1}^{N-1}Z_{i}Z_{i+1}\;,$ (20a)
$H_{2}=+\sum_{i=1}^{N}Z_{i}-\sum_{i=1}^{N-1}Z_{i}Z_{i+1}-\sum_{i=1}^{N-2}Z_{i}Z_{i+2}\;,$
(20b)
$H_{3}=+\sum_{i=1}^{N}Z_{i}-\sum_{i=1}^{N-1}Z_{i}Z_{i+1}-\sum_{i=1}^{N-2}Z_{i}Z_{i+2}-\sum_{i=1}^{N-3}Z_{i}Z_{i+3}\;,$
(20c) $\displaystyle
H_{4}=+\sum_{i=1}^{N}Z_{i}-\sum_{i=1}^{N-1}Z_{i}Z_{i+1}-\sum_{i=1}^{N-2}Z_{i}Z_{i+2}-\sum_{i=1}^{N-3}Z_{i}Z_{i+3}$
$\displaystyle-\sum_{i=1}^{N-4}Z_{i}Z_{i+4}\;,$ (20d)
$H_{5}=+\sum_{i=1}^{N}Z_{i}-\sum_{i,j=1,i\neq j}^{N}Z_{i}Z_{j}\;.$ (20e)

All the Hamiltonians in Eq. $\left(\ref{eq:set-of-Hs}\right)$ have the ground
state $\left|1\right\rangle^{\otimes N}$. The relation between number of edges
of these graphs $E$, success rates $R$ and tripartite information $I_{3}$ in
QAOA circuit is depicted in Fig. 5.

From Fig. 5(a) we see, generally speaking, the success rates $R$ is positively
correlated with the number of edges $E$, which is in agreement with Eq.
$\left(\ref{eq:prop-edge}\right)$. However, as depth of the circuit goes
deeper, the success rates seem stop increasing or even decrease, which is
inconsistent with our ideal prediction.

$p$ | 4 | 6 | 8 | 10
---|---|---|---|---
$\rho_{EI_{3}}$ | 0.8357 | 0.8624 | 0.8512 | 0.8761
Table 1: The Pearson correlation coefficient of number of edges $E$ of the set
of graphs in Eq. $\left(\ref{eq:set-of-Hs}\right)$ and tripartite information
$I_{3}$ in the corresponding QAOA circuits for different layers $p=4,6,8,10$.
These parameters reflect the positive correlation between $E$ and $I_{3}$.

We have mentioned the local minima problem for QAOA in Sec. III.1. A deeper
circuit depth means a more complex process of variational optimization, and
one more layer takes a pair of new parameters. Therefore, the algorithm faces
more local minima and most of them have low $\alpha$ values. Another
interesting phenomenon in Fig. 5(a) is, as the success rates of computing
$\left\langle H_{1}\right\rangle_{min}$ to $\left\langle
H_{4}\right\rangle_{min}$ stops increasing, computing $\left\langle
H_{5}\right\rangle_{min}$ don’t have to suffer from the problem. This may be
explained that the complete graph is the most complex and needs more
parameters for a good optimization, so when the layer is larger, relatively it
has more possibility to reach a high success rate.

Because here $R$ isn’t the best characterization of complexity, we evaluate
the correlation between number of edges $E$ of the graphs in Eq.
$\left(\ref{eq:set-of-Hs}\right)$ and tripartite information $I_{3}$, instead
of former $R$ and $I_{3}$. The tripartite information in QAOA circuits versus
different $E$ is depicted in Fig. 5(b), where we can observe a noticeable
positive correlation between $E$ and $I_{3}$. Thus, in Table. 1 we show the
Pearson correlation coefficient of $E$ and $I_{3}$ calculated using Eq.
$\left(\ref{eq:correlator}\right)$ for different layers. As is shown in Table.
1, we find the correlation between number of edges $E$ and information
scrambling characterized by tripartite information $I_{3}$ is strong, and the
correlation strengths for four different layers are very similar to each
other.

Figure 5: The comparison between success rates for computing minimal mean values of Eq. $\left(\ref{eq:set-of-Hs}\right)$ via $p$-layer QAOA and information scrambling in the circuit with number of qubits $N=7$, in $Z-ZZ$-type Hamiltonians with different edges $E$ and the same weights. (a). The success rates of QAOA of different layers when $\alpha\geq 0.996$ and $10^{2}$ loops. (b). Average tripartite information of QAOA circuits corresponding to the success rates. $p$ | 4 | 6 | 8 | 10
---|---|---|---|---
$\rho_{ES^{p}_{max}}$ | 0.8982 | 0.9446 | 0.9033 | 0.9255
Table 2: The Pearson correlation coefficients of number of edges $E$ of the
set of graphs in Eq. $\left(\ref{eq:set-of-Hs}\right)$ and the maximal one-
qubit entanglement entropy $S^{p}_{max}$ in every layers $l\leq p$ of the
corresponding QAOA circuits for $p=4,6,8,10$.

##  IV Entanglement in QAOA circuit versus complexity of the problems

$p$ | 4 | 6 | 8 | 10
---|---|---|---|---
$\rho_{E\bar{\mathcal{A}}}$ | 0.9755 | 0.8444 | 0.8487 | 0.6827
Table 3: The Pearson correlation coefficients of number of edges $E$ of the
set of graphs in Eq. $\left(\ref{eq:set-of-Hs}\right)$ and average areas of
entanglement accumulation $\bar{\mathcal{A}}$ in the corresponding QAOA
circuits for $p=4,6,8,10$.

As we have discussed in previous sections, information scrambling is a global
entanglement feature in QAOA circuits. Next, we turn to more details for
entanglement properties. We still take Eq. $\left(\ref{eq:set-of-Hs}\right)$
as the set of our interested QUBO problems with non-degenerate solutions, and
their corresponding Ising Hamiltonians have the ground state
$\left|1\right\rangle^{\otimes N}$. As have introduced in Sec. I, since both
the initial and final state are separable, entanglement is only generated
during the computing process. Therefore in this section, we explore how to
quantify the entanglement generated in the circuit, and its correlation with
complexity of QUBO problems characterized by number of graph edges $E$ like
Sec. III.2.

Figure 6: One-qubit maximal entanglement entropy in $p$-layer QAOA circuits
during the process of computing minimal mean values of Ising Hamiltonians in
Eq. $\left(\ref{eq:set-of-Hs}\right)$. Here we choose four different layers:
$p=4,6,8,10$, and take an average of $10^{2}$ data.

We first define a coarse-grained quantity for a QAOA circuit with a given
layer $p$:

$S^{p}_{max}=\mathrm{max}_{l\leqslant
p,l\in\mathbb{Z}}\left\\{\bar{S}^{p}_{l}\right\\}\,,$ (21)

where $\bar{S}^{p}_{l}$ has the form of Eq. $\left(\ref{eq:avg-
entropy}\right)$, which is the average one-qubit entanglement entropy of every
layer $l\leq p$ in the $p$-layer circuit. Eq. $\left(\ref{eq:Smax}\right)$
means the maximum of average one-qubit entanglement entropy among all
$\bar{S}^{p}_{l}$. After that, we present the maximal entanglement entropy
generated in the circuits during the process of computing minimal mean values
of Hamiltonians of Eq. $\left(\ref{eq:set-of-Hs}\right)$ in Fig. 6. From this
figure, we can see the tendency that the more number of edges $E$ the graph
has, the more entanglement is generated in the circuit. Similar to Sec. III,
we quantify the correlation via Pearson coefficients with number of edges $E$
and maximal one-qubit entanglement entropy $S^{p}_{max}$ in Table. 2, where a
strong positive correlation is easy to be observed.

To this point, a question raises naturally: What about the entanglement
properties inside one layer? As previous studies of entanglement in QAOA
circuit only take one “layer” as a unit, what happens inside one layer has not
been investigated yet. According to the layer of QAOA circuit shown in Fig. 1,
the two-qubit gates represent the terms $e^{-i\gamma_{i}Z_{j}Z_{k}}$ in Eq.
$\left(\ref{eq:QAOA-cir}\right)$, all of them can generate entanglement.
Therefore, in the following we step into each layer and focus on total
entanglement accumulated in QAOA circuits.

We now introduce a proper characterization of entanglement accumulation in
$p$-layer QAOA circuit in the form of

$\mathcal{A}=Area\left(\bar{S}*p\right)\,,$ (22)

which is the area of $S-p$ plot for average one-qubit entanglement entropy
$\bar{S}$ generated during the evolution of $p$-layer QAOA circuit. Ideally,
we expect the accumulation $\mathcal{A}$ is always positively correlated with
number of edges $E$. However, due to the randomness of initial parameters
$\left\\{\vec{\beta}_{0},\vec{\gamma}_{0}\right\\}$, entanglement accumulation
of the same layer in the same computing process can be very different from
each other. For example, two different typical structures of entanglement
accumulation in the process of computing $\left\langle
H_{5}\right\rangle_{min}$ when $p=6$ is shown in Fig. 7. The structure in Fig.
7(a) only demands large entanglement at first two layers, whereas entanglement
in Fig. 7(b) is always large until the final step. Thus, to obtain a practical
quantity describing entanglement accumulation, we still need a number of
samplings and consider average values.

Figure 7: Two examples of $S-p$ plots for entanglement entropy accumulation
when $p=6$, edges of $ZZ=21$. Here we calculate $\bar{S}$ after each two-qubit
gate in the circuit, and the caption “depth” means the layers $l\leq p$ of one
$p$-layer QAOA circuit.

Here, we present the distribution of $\mathcal{A}$ for $50$ samplings per
layer and per problem in Fig. 9. We can find for harder problems, the “tails”
of probability density become larger, which means the proportion of
entanglement structures like Fig. 7(b) increases, and indicates a requirement
for more entanglement accumulation. Moreover, by taking average values of
these samplings, we obtain a relation between average areas of entanglement
accumulation $\bar{\mathcal{A}}$ and number of edges $E$ of the graphs of Eq.
$\left(\ref{eq:set-of-Hs}\right)$, which is shown in Fig. 8 and Pearson
correlation coefficients in Table. 3. Based on all these settings, we can
observe a glaring positive correlation between complexity of these problems
and entanglement accumulation in corresponding QAOA circuits.

##  V Conclusions and outlook

Figure 8: Average entanglement accumulation $\bar{\mathcal{A}}$ to reach
$\alpha\geqslant 0.996$ during the process of computing minimal mean values of
Hamiltonians in Eq. $\left(\ref{eq:set-of-Hs}\right)$with four fixed layers
$p=4,6,8,10$. We take an average of $50$ samplings for each case. Figure 9:
The distributions and probability density of areas of $S-p$ plots with
different QAOA layers and problems for $50$ samplings. Figures from up to down
are distributions of the same problems for layers $p=4,6,8,10$. Figures from
left to right are distributions of the same layers for the problems
$\left\langle H_{1}\right\rangle_{min}$ to $\left\langle
H_{5}\right\rangle_{min}$.

In this work, we have addressed the question of how much quantum resource is
consumed for solving QUBO problems with different complexity in QAOA circuits.
More precisely, we characterize quantum resource in QAOA circuits by two
concepts in quantum information, information scrambling and entanglement, and
characterize complexity of problems by success rates and number of edges of
graphs. By taking QAOA circuits as unitary quantum channels, we use tripartite
mutual information to quantify information scrambling. Next, we use the
maximal entanglement entropy among every layers in QAOA circuits to present
how much entanglement is needed in the whole computing process. After that, we
study entanglement accumulation caused by two-qubit gates inside every layers
in QAOA circuits, where we define an effective quantity to describe this
process, namely an average area of entanglement entropy generated in the
circuits and depth of the circuits.

Our main contribution is to present a positive correlation between complexity
of QUBO problems and quantum resources including information scrambling and
entanglement in QAOA circuits, which is expressed by Pearson correlation
coefficients. Apart from this contribution, we make some clarifications of
complexity of QUBO problems and define some quantities for entanglement
accumulation in QAOA circuits, which can be useful in further studies.
Firstly, we clarify the concepts of “quantum resource” and “complexity of QUBO
problems” in our study, and propose the factors related to the complexity
$\mathcal{C}$: graph weights $\left\\{w_{ij},h_{k}\right\\}$ and graph density
$D$. Then, we introduce success rate $R$ to quantify the complexity in
practical case, and find that with weights of the graphs fixed, we can take
number of edges $E$ to characterize the complexity. Secondly, we offer two
quantities to describe how much entanglement, i.e. the maximal entanglement
entropy Eq. $\left(\ref{eq:Smax}\right)$ and the area of entanglement
accumulation Eq. $\left(\ref{eq:area}\right)$, is required in QAOA circuits
for solving QUBO problems with non-degenerate solutions.

Moreover, several remarks and outlooks including both scrambling and
entanglement are discussed as follows.

In the part of information scrambling, as we have discussed in Sec. III, the
circuits are more scrambled when the problem is more complex. However, there
is a question: How to compare the complexity of case Eq.
$\left(\ref{eq:H-complete-exact}\right)$ and case Eq. $\left(\ref{eq:H-line-
hard}\right)$? Obviously the success rates of Eq. $\left(\ref{eq:H-line-
hard}\right)$ is much lower, but its tripartite information is smaller than
that of Eq. $\left(\ref{eq:H-complete-exact}\right)$. To this extent, we need
further studies to well-define the relation between complexity $\mathcal{C}$,
success rate $R$, and tripartite information $I_{3}$ in a general context.
Nevertheless, for very complex QUBO problems we don’t know the graph weights
and densities exactly, $I_{3}$ may be a useful quantity to characterize its
complexity roughly.

It should be pointed out that the resource of information scrambling includes
two aspects: entanglement scrambling and magic scrambling [21, 8]. Among these
aspects, magic is said to be a complete quantum resource as it cannot be
simulated by classical computers, and it is used to quantify complexity of
fidelity estimation [7, 41]. Therefore, an interesting future work is to
characterize how much magic generated in QAOA circuits, which can be an
important direction for demonstrating quantum advantages beyond classical
computation.

In the part of entanglement, the average area of entanglement accumulation
$\bar{\mathcal{A}}$ can be viewed as an overall entanglement resource required
in the process of solving target problems, which can be a general quantity not
only for a certain kind of problems like Eq. $\left(\ref{eq:set-of-
Hs}\right)$. We can apply this quantity to all QUBO problems with non-
degenerate solutions, and generalizing the quantity to include problems with
degenerate solutions is also a promising topic be discussed in the future.
Moreover, as is shown in Fig. 7 and Fig. 9, $\mathcal{A}$ for the same problem
can be very different due to random choices of
$\left\\{\beta_{0},\gamma_{0}\right\\}$. It is interesting to consider the
entanglement accumulation as a special feature of QAOA optimization process.
Then, we can improve the algorithm by selecting the output that requires the
least amount of entanglement accumulation among outputs with the same $\alpha$
value.

In summary, our results try to build a connection between the complexity of
the problems and quantum information processing of their corresponding QAOA
circuits. It should be noticed that our discussion is so far limited to small
number of qubits and easy problems. In further studies, a generalization of
our results may has a wide application in areas of not only quantum
computation but also quantum many-body physics, such as many-body localization
and scars [42], quantum phase transitions [43], and so on.

## Acknowledgments

We thank Ya-Nan Pu, Yunheng Ma and Yanwu Gu for useful discussions. This work
is supported by Beijing Natural Science Foundation (No.Z220002).

## References

  * Chitambar and Gour [2019] E. Chitambar and G. Gour, Quantum resource theories, Rev. Mod. Phys. 91, 025001 (2019).
  * Horodecki  _et al._ [2009] R. Horodecki, P. Horodecki, M. Horodecki, and K. Horodecki, Quantum entanglement, Rev. Mod. Phys. 81, 865 (2009).
  * Preskill [2018] J. Preskill, Quantum computing in the nisq era and beyond, Quantum 2, 79 (2018).
  * Hosur  _et al._ [2022] P. Hosur, X.-L. Qi, D. A. Robertsb, and B. Yoshidac, Chaos in quantum channels, J. High Ener. Phys. 2016, 4 (2022).
  * Landsman  _et al._ [2019] K. A. Landsman, C. Figgatt, T. Schuster, N. M. Linke, B. Yoshida, N. Y. Yao, and C. Monroe, Verified quantum information scrambling, Nature 567, 61 (2019).
  * Xu and Swingle [2022] S. Xu and B. Swingle, Scrambling dynamics and out-of-time ordered correlators in quantum many-body systems: a tutorial, arXiv:2202.07060 (2022).
  * Ahmadi and Greplova [2022] A. Ahmadi and E. Greplova, Quantifying quantum computational complexity via information scrambling, arXiv:2204.11236 (2022).
  * Garcia  _et al._ [2022a] R. J. Garcia, K. Bu, and A. Jaffe, Resource theory of quantum scrambling, arXiv:2208.10477 (2022a).
  * Hayden and Preskill [2007] P. Hayden and J. Preskill, Black holes as mirrors: quantum information in random subsystems, J. High Ener. Phys. 2007, 120 (2007).
  * Harlow [2016] D. Harlow, Jerusalem lectures on black holes and quantum information, Rev. Mod. Phys. 88, 015002 (2016).
  * Yoshida [2019] B. Yoshida, Firewalls vs. scrambling, J. High Ener. Phys. 2019, 132 (2019).
  * Harris  _et al._ [2022] J. Harris, B. Yan, and N. A. Sinitsyn, Benchmarking information scrambling, Phys. Rev. Lett. 129, 050602 (2022).
  * Yan and Sinitsyn [2020] B. Yan and N. A. Sinitsyn, Recovery of damaged information and the out-of-time-ordered correlators, Phys. Rev. Lett. 125, 040605 (2020).
  * Shen  _et al._ [2020] H. Shen, P. Zhang, Y.-Z. You, and H. Zhai, Information scrambling in quantum neural networks, Phys. Rev. Lett. 124, 200504 (2020).
  * Wu  _et al._ [2021] Y. Wu, P. Zhang, and H. Zhai, Scrambling ability of quantum neural network architectures, Phys. Rev. Research 3, L032057 (2021).
  * Garcia  _et al._ [2022b] R. J. Garcia, K. Bu, and A. Jaffe, Quantifying scrambling in quantum neural networks, J. High Ener. Phys. 2022, 27 (2022b).
  * Cotler  _et al._ [2017] J. Cotler, N. Hunter-Jones, J. Liub, and B. Yoshidac, Chaos, complexity, and random matrices, J. High Ener. Phys. 2017, 48 (2017).
  * Roberts and Yoshidac [2017] D. A. Roberts and B. Yoshidac, Chaos and complexity by design, J. High Ener. Phys. 2017, 121 (2017).
  * Bhattacharyya  _et al._ [2022] A. Bhattacharyya, L. K. Joshib, and B. Sundar, Quantum information scrambling: from holography to quantum simulators, Eur. Phys. J. C 82, 458 (2022).
  * Iyoda and Sagawa [2018] E. Iyoda and T. Sagawa, Scrambling of quantum information in quantum many-body systems, Phys. Rev. A 97, 042330 (2018).
  * Mi  _et al._ [2021] X. Mi, P. Roushan, C. Quintana, S. Mandrà, J. Marshall, C. Neill, and et al., Information scrambling in quantum circuits, Science 374, 1479 (2021).
  * Zhu  _et al._ [2022] Q. Zhu, Z. H. Sun, M. Gong, F. Chen, Y. R. Zhang, Y. Wu, and et al., Observation of thermalization and information scrambling in a superconducting quantum processor, Phys. Rev. Lett. 128, 160502 (2022).
  * Kandala  _et al._ [2017] A. Kandala, A. Mezzacapo, K. Temme, M. Takita, M. Brink, J. M. Chow, and J. M. Gambetta, Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets, Nature 549, 242 (2017).
  * Biamonte  _et al._ [2017] J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd, Quantum machine learning, Nature 549, 195 (2017).
  * Farhi and Goldstone [2014] E. Farhi and J. Goldstone, A quantum approximate optimization algorithm, arXiv:1411.4028 (2014).
  * Punnen [2022] A. P. Punnen,  _The Quadratic Unconstrained Binary Optimization Problem_ (Springer Nature, 2022).
  * Wu and Hsieh [2019] J. Wu and T. H. Hsieh, Variational thermal quantum simulation via thermofield double states, Phys. Rev. Lett. 123, 220502 (2019).
  * Fitzek  _et al._ [2021] D. Fitzek, T. Ghandriz, L. Laine, M. Granath, and A. F. Kockum, Applying quantum approximate optimization to the heterogeneous vehicle routing problem, arXiv:2110.06799 (2021).
  * Wiersema  _et al._ [2020] R. Wiersema, C. Zhou, Y. deSereville, J. F. Carrasquilla, Y. B. Kim, and H. Yuen, Exploring entanglement and optimization within the hamiltonian variational ansatz, Phys. Rev. X Quantum 1, 020319 (2020).
  * Díez-Valle  _et al._ [2021] P. Díez-Valle, D. Porras, and J. J. García-Ripoll, Quantum variational optimization: The role of entanglement and problem hardness, Phys. Rev. A 104, 062426 (2021).
  * Chen  _et al._ [2022] Y. Chen, L. Zhu, C. Liu, N. J. Mayhall, E. Barnes, and S. E. Economou, How much entanglement do quantum optimization algorithms require?, arXiv:2205.12283 (2022).
  * Dupont  _et al._ [2022] M. Dupont, N. Didier, M. J. Hodson, J. E. Moore, and M. J. Reagor, Entanglement perspective on the quantum approximate optimization algorithm, Phys. Rev. A 106, 022423 (2022).
  * Sreedhar  _et al._ [2022] R. Sreedhar, P. Vikstål, M. Svensson, A. Ask, G. Johansson, and L. García-Álvarez, The quantum approximate optimization algorithm performance with low entanglement and high circuit depth, arXiv:2207.03404 (2022).
  * Kitaev and Preskill [2006] A. Kitaev and J. Preskill, Topological entanglement entropy, Phys. Rev. Lett. 96, 110404 (2006).
  * Zhuang  _et al._ [2021] W.-F. Zhuang, Y.-N. Pu, H.-Z. Xu, X. Chai, Y. Gu, Y. Ma, S. Qamar, C. Qian, P. Qian, X. Xiao, and D. E. L. M.-J. Hu, Efficient classical computation of quantum mean values for shallow qaoa circuits, arXiv:2112.11151 (2021).
  * Zhou  _et al._ [2020] L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin, Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices, Phys. Rev. X 10, 021067 (2020).
  * Zhang  _et al._ [2022] B. Zhang, A. Sone, and Q. Zhuang, Quantum computational phase transition in combinatorial problems, npj Quantum Information 8, 87 (2022).
  * Håstad [2001] J. Håstad, Some optimal inapproximability results, Journal of the ACM 48, 4 (2001).
  * Sakai  _et al._ [2003] S. Sakai, M. Togasaki, and K. Yamazaki, A note on greedy algorithms for the maximum weighted independent set problem, Discrete Applied Mathematics 126, 313 (2003).
  * Bittel and Kliesch [2021] L. Bittel and M. Kliesch, Training variational quantum algorithms is np-hard, Phys. Rev. Lett. 127, 120502 (2021).
  * Leone  _et al._ [2022] L. Leone, S. F. Oliviero, and A. Hamma, Magic determines the hardness of direct fidelity estimation, arXiv:2204.02995 (2022).
  * Abanin  _et al._ [2019] D. A. Abanin, E. Altman, I. Bloch, and M. Serbyn, Colloquium: Many-body localization, thermalization, and entanglement, Rev. Mod. Phys. 91, 021001 (2019).
  * Dziarmaga [2010] J. Dziarmaga, Dynamics of a quantum phase transition and relaxation to a steady state, Adv. in Phys. 59, 1063 (2010).