# Adiabatic-Passage-Based Parameter Setting for Quantum Approximate
Optimization Algorithm

Mingyou Wu  School of Computer Science and Engineering, Southeast University,
Nanjing 211189, China  Hanwu Chen<EMAIL_ADDRESS>School of Computer
Science and Engineering, Southeast University, Nanjing 211189, China  Key
Laboratory of Computer Network and Information Integration (Southeast
University), Ministry of Education, Nanjing 211189, China

###### Abstract

The Quantum Approximate Optimization Algorithm (QAOA) exhibits significant
potential for tackling combinatorial optimization problems. Despite its
promise for near-term quantum devices, a major challenge in applying QAOA lies
in the cost of circuit runs associated with parameter optimization. Existing
methods for parameter setting generally incur at least a superlinear cost
concerning the depth p of QAOA. In this study, we propose a novel adiabatic-
passage-based parameter setting method that remarkably reduces the
optimization cost, specifically when applied to the 3-SAT problem, to a
sublinear level. Beginning with an analysis of the random model of the
specific problem, this method applies a problem-dependent preprocessing on the
problem Hamiltonian analytically, effectively segregating the magnitude of
parameters from the scale of the problem. Consequently, a problem-independent
initialization is achieved without incurring any optimization cost or pre-
computation. Furthermore, the parameter space is adjusted based on the
continuity of the optimal adiabatic passage, resulting in a reduction in the
disparity of parameters between adjacent layers of QAOA. By leveraging this
continuity, the cost to find quasi-optimal parameters is significantly reduced
to a sublinear level.

##  I Introduction

Quantum computation Nielsen2000  is an emerging computational model rooted in
quantum mechanics that has demonstrated remarkable speedup in various
computational problems. Algorithms such as the prime factorization algorithm
Shor1994 , the Grover search Grover1997 , and the HHL algorithm Harrow2009
show provable exponential or polynomial accelerations compared to classical
algorithms. Notably, despite the theoretical advantages inherent in quantum
algorithms, the present computational landscape is constrained by the
availability of only noisy intermediate-scale quantum (NISQ) devices
Preskill2018 . The intrinsic noise in these devices limits their capacity to
manifest a quantum advantage over classical computers when applying such
algorithms. In the NISQ era, the imperative to develop noise-tolerant quantum
algorithms becomes paramount. A focal point of concern revolves around the
development of hybrid quantum-classical algorithms, which leverage the
parameterized quantum circuits and adjust these parameters through classical
optimization techniques Cerezo2021VQA . Prominent instances of such approaches
include Quantum Neural Networks (QNN) Farhi2018QNN ; Biamonte2017  tailored
for machine learning tasks, the Variational Quantum Eigensolver (VQE)
Peruzzo2014VQE ; Kandala2017VQE  designed for quantum chemistry calculations,
and the Quantum Approximate Optimization Algorithm (QAOA) farhi2014QAOA .

QAOA is a promising approach for implementation on NISQ devices Moll2018 ;
Harrigan2021 , showcasing significant computational potential in the domain of
combinatorial optimization and receiving extensive attention in various
aspects. In 2017, a near-optimal quantum circuit for the unstructured search
was introduced by employing the Grover Hamiltonian as the problem Hamiltonian
within the QAOA framework PRA2017 . This reveals that QAOA is, at a minimum,
as efficient as the Grover search algorithm Grover1997 . Theoretical
investigations into QAOA’s computational capabilities have produced noteworthy
results for specific instances PRA2018 ; Brandao2018 ; basso2021quantum ;
farhi2021QAOA . Moreover, a spectrum of theoretical analyses have been
conducted to elucidate the inherent computational power of QAOA farhi2019QAOA
; barak2021 ; Streif2021 . The versatility of QAOA is exemplified by the
proposal of several variants tailored to different problem classes Wang2020 ;
bako2022 ; RUAN2023 . However, an intrinsic challenge arises in the form of
the curse of dimensionality, particularly regarding the optimization cost
associated with parameter setting.

The optimization cost of QAOA primarily arises from adjusting parameters for
the $p$-layered parameterized quantum circuit. Analogous to quantum adiabatic
algorithm (QAA) farhi2000QAA ; farhi2001QAA  and VQE, QAOA defines the problem
Hamiltonian $H_{C}$ and evolve the quantum state to the eigenstate with the
maximal (or minimal) eigenvalue of $H_{C}$. Notably, QAOA diverges by
alternately applying the problem Hamiltonian $H_{C}$ and mix Hamiltonian
$H_{B}$ for $p$ iterations, with the evolution time parameterized by
${\bm{\gamma}}=\left(\gamma_{1},\gamma_{2},\cdots,\gamma_{p}\right)$ and
${\bm{\beta}}=\left(\beta_{1},\beta_{2},\cdots,\beta_{p}\right)$. In the
context of an NP-complete combinatorial optimization problem with $n$
variables, it is hard to maintain the depth of QAOA to be a constant or
logarithm of $n$ farhi2020QAOA . Specifically, when the depth $p={\rm
Poly}(n)$, the polynomial number of parameters leads to an exponential
optimization cost for parameters setting. Various techniques are employed to
mitigate the optimization cost of parameter setting in QAOA, including
classical optimization crooks2018performance , machine learning algorithm
verdon2019learning ; Streif2020 ; Jain2022 ; Moussa2022  and other heuristic
strategies PRX2020 ; boulebnane2021predicting ; Wurtz2021Setting ;
Wurtz2021Warm ; Sack2021 ; Tate2023 . Among these, the heuristic strategy in
PRX2020  is notably representative, reducing the optimization cost to
approximately polynomial on $p$, albeit remaining superlinear. This paper
proposes an adiabatic-passage-based parameter setting method that further
diminishes the cost, specifically when applied to 3-SAT problem, to sublinear
concerning the depth $p$. Concretely, the cost exhibits logarithmic growth in
limited simulation, showcasing the potential efficiency of the proposed
method. Here, the optimization cost refers to the number of circuit runs
required to find quasi-optimal parameters.

This method commences with a rigorous analysis of the statistical property
inherent in the given problem. Specifically, for the $k$-SAT decision problem,
a reduction is applied to transform it into a max-$k$-SAT optimization
concentrated exclusively on satisfiable instances. Subsequently, random
$k$-SAT models on satisfiable instances are constructed, aligning with the
random $k$-SAT model Achioptas2006 . The Hamiltonian for this random model is
conceived as random variable, facilitating the acquisition of statistical
properties pertaining to the problem Hamiltonian for random instances.
Following this characterization, a problem-dependent preprocessing step is
executed on the Hamiltonian, effectively decoupling the magnitude of
parameters from the scale of the specific problem. Consequently, a problem-
independent initialization is formulated. Drawing inspiration from QAA, this
initialization method provides judicious initial parameters for QAOA of full
depth $p$ without incurring any optimization cost or pre-computation. This
initialization method shares a similar form with the Trotterized Quantum
Annealing (TQA) initialization Sack2021 , with the only difference lying in
whether pre-computation is involved. Furthermore, this initialization can be
adapted into a QAA-inspired parameter setting method with linear-varying
parameters, akin to the INTERP heuristic strategy in PRX2020 , thus
representing an intermediate iteration of the proposed method.

Furthermore, to better illustrate the landscape of the parameter space, the
adiabatic passage (AP) is introduced SAP2016 ; STIRAP2017 . QAOA can be
conceptualized as a parameterized adiabatic passage, wherein the optimization
of the parameters represents the search for the optimal adiabatic passage. By
leveraging the inherent continuity in the optimal adiabatic passage, an
alternative parameter space is introduced to augment the smoothness of
parameters, thereby mitigating the differences in parameters between adjacent
layers. The adiabatic-passage-based (AP-based) parameter setting method
effectively capitalizes on this parameter continuity, resulting in a
substantial reduction in optimization costs. To provide a comparative
analysis, evaluations are conducted with the TQA initialization in Sack2021
and the heuristic strategies in PRX2020 . In simulations of the 3-SAT problem,
the optimization costs required for obtaining optimally linear-varying
parameters for the INTERP is on the order of ${\mathcal{O}}(p)$, while the
QAA-inspired and TQA method maintains constant costs despite the increasing in
depth $p$. RRegarding the quasi-optimal parameters, the optimization cost of
FOURIER exhibits a growth rate slightly exceeding ${\mathcal{O}}(p^{2})$,
while the TQA method experiences an increase slightly faster than linear.
Notably, the AP-based method further diminishes this cost, manifesting a
sublinear level. Specifically, it exhibits an approximately logarithmic
relationship with depth $p$ in limited simulations. This reduction in
optimization costs is attributed to the inherent continuity of the optimal
adiabatic passage, resulting in only a logarithmic outer loop in the AP-based
method which provides the potential for exponential acceleration.

The subsequent sections of this paper are organized as follows. Section II
introduces some preliminaries to establish foundational concepts. In Section
III, we delve into the statistical properties of the random $k$-SAT model.
Based on this analysis, the Hamiltonian of QAOA undergoes preprocessing.
Within Section III, according to the preprocessing, we initially introduce a
QAA-inspired parameter initialization, which can be further adapted into a
QAA-inspired parameter setting method with linear parameters. Additionally, we
explore parameter continuity through an analysis of the optimal adiabatic
passage, introducing an alternative parameter space with improved continuity.
Building upon this analysis, we propose the AP-based parameter setting method.
Section V compares the methods with the TQA initialization Sack2021  and
heuristic strategies proposed in PRX2020  by simulations on 3-SAT, providing
an experimental result about the potential exponential speed-up in parameter
adjusting. In Section VI, we conduct a discussion on the universal
applicability of this method to general combinatorial optimization problems.
Finally, Section VII concludes this paper and suggests avenues for further
research.

##  II Preliminaries

###  II.1 Random $k$-SAT problem

The Boolean satisfiability (SAT) is a well-known NP-complete problem of
determining whether there exists an interpretation that satisfies a given
Boolean formula. In the context of the $k$-SAT problem, the Boolean formula is
confined to conjunctive normal form, where each clause is constrained to at
most $k$ literals. In this paper, we further impose a restriction to exactly
$k$ literals for each clause. The NP-completeness would be maintained as long
as $k\geq 3$. This $k$-SAT decision problem can be reformulated to an
optimization version, max-$k$-SAT, by defining the goal function as
$C(x)=\sum_{\alpha}C_{\alpha}(x)$, where $\alpha$ denotes a clause, and
$C_{\alpha}(x)$ represents the characteristic function of $\alpha$.
Specifically, $C_{\alpha}(x)=1$ if $\alpha$ is satisfied by assignment $x$,
and $C_{\alpha}(x)=0$ otherwise. max-$k$-SAT seeks to identify an assignment
$t$ that maximizes $C(x)$. It is noteworthy that for max-$k$-SAT, the NP-
completeness persists for $k\geq 2$.

Figure 1: The process of selecting a clause when generating a random $k$-SAT
instance. Let $I\in U_{s}$ and has interpretation set $\\{t\\}$. In the case
of $F(n,m,k)$, when selecting the next clause, it randomly chooses any clause
from $S_{1}+S_{2}+S_{3}$. In contrast, $F_{s}(n,m,k)$ selectively picks
clauses that are satisfiable for any $t\in\\{t\\}$, specifically from
$S_{1}+S_{2}$. Meanwhile, $F_{f}(n,m,k)$ exclusively selects clauses from
$S_{1}$. When $\\{t\\}=\\{t_{0}\\}$, $F_{s}(n,m,k)$ coincides with
$F_{f}(n,m,k)$, and with an increase in $m$, it converges to $F_{f}(n,m,k)$.
Figure 2: An illustrative example of quantum circuit for $e^{i\theta
H_{\alpha}}$, where $\alpha=\lnot x_{1}\lor x_{2}\lor\lnot x_{4}$. This clause
is represented as $\alpha=(-1,2,-4)$, corresponding to the Hamiltonian term
$H_{\alpha}=-p_{\bar{\alpha}}$, where $\bar{\alpha}=(1,-2,4)$. This implies
that the 1st, 2nd, and 4th qubits (from top to bottom in the figure) are
occupied, and an additional pair of $X$ gate is applied to the 2nd qubit. In
this circuit, the 4th qubit serves as the controlled qubit; however, it is
notable that the controlled qubit can be any of the involved qubits, with the
rest qubits acting as the control qubits.

The $k$-SAT decision problem can be reduced to max-$k$-SAT focusing
exclusively on Satisfiable instances, denoted as max-$k$-SSAT in this paper.
The k-SAT problem is polynomially solvable if max-$k$-SSAT exhibits polynomial
solvability. A concise proof is presented as follows: The complete set $U$ of
$k$-SAT is divided into two subset, $U_{s}$ comprising all satisfiable
instances and $U_{u}$ containing the unsatisfiable ones. Assuming an algorithm
$A$ can solve max-$k$-SSAT in ${\mathcal{O}}(f(n))$ time, another algorithm
$A^{\prime}$ tailored for $k$-SAT can be devised. Algorithm $A^{\prime}$
accepts all instance $I\in U$ and processes $I$ by $A$. If running time
exceeds ${\mathcal{O}}(f(n))$, the algorithm terminates and outputs a random
result. For any $I$, $A^{\prime}$ halts within ${\mathcal{O}}(f(n))$ time,
yielding result $x$. In case when $I\in U_{s}$, $x$ serves as the
interpretation $t$ and satisfies the Boolean formula; otherwise, $x$ is a
random value and necessarily unsatisfiable. Through verification, the
satisfiability can be determined. The verification cost dose not surpass
${\mathcal{O}}(f(n))$, maintaining an overall complexity of
${\mathcal{O}}(f(n))$.

The random $k$-SAT model, denoted as $F(n,m,k)$, is widely employed in SAT
problem research Achioptas2006 . Given the reduction of $k$-SAT to
max-$k$-SSAT, random models exclusively on $U_{s}$ can be designed. $F(n,m,k)$
generates a $k$-SAT instance on $n$ variables by uniformly, independently, and
with replacement selecting $m$ clauses from the entire set of $2^{k}C_{n}^{k}$
possible clauses. Building upon this foundation, two types of random models on
$U_{s}$ are introduced. $F_{s}(n,m,k)$ serves as a direct extension from
$F(n,m,k)$ by selectively choosing clauses while maintaining satisfiability.
However, $F_{s}(n,m,k)$ presents theoretical challenges for analysis due to
the varying optional clause set with $m$. An alternative random model,
$F_{f}(n,m,k)$, is proposed as an approximation of $F_{s}(n,m,k)$. In this
model, a pre-fix interpretation $t_{0}$ is randomly provided, and only clauses
satisfied by $t_{0}$ are selected. If the generating process is conceptualized
as a tree, the distinctions among these three random models are visually
presented in Figure 2. In this paper, the focus lies primarily on
$F_{s}(n,m,k)$ and $F_{f}(n,m,k)$.

###  II.2 Quantum adiabatic computation

In the quantum system, the evolution of the state $\left|\psi(t)\right>$ is
dictated by the Schrödinger equation

$i\frac{{\rm d}}{{\rm d}t}\left|\psi(t)\right>=H(t)\left|\psi(t)\right>,$ (1)

where $H(t)$ represents the system Hamiltonian. If $H(t)$ is time-dependent
and $\left|\varphi(t)\right>$ is initially in the ground state of $H(0)$, the
adiabatic theorem asserts that $\left|\psi(t)\right>$ will persist in the
ground state of $H(t)$ as long as $H(t)$ varies sufficiently slowly.

Quantum adiabatic computation RMP2018AQC  leverages the adiabatic theorem to
solve for the ground state of a given problem Hamiltonian $H_{C}$. By
designing the system Hamiltonian as

$H(s)=sH_{C}+(1-s)H_{B},$ (2)

and preparing the initial state $\left|\psi(0)\right>$ in the ground state of
$H_{B}$, the state evolves to the ground state of $H_{C}$ as $s$ slowly varies
$s$ from 0 to 1. The evolution time $T$ for $H(s)$ should satisfies

$T\gg\frac{\varepsilon_{0}}{g^{2}_{0}},$ (3)

where $g_{0}$ is the minimum of energy gap between the ground state
$\psi_{1}(s)$ and the first excited state $\psi_{2}(s)$ of $H(s)$. Denoting
$g(s)$ as the gap between $\psi_{1}(s)$ and $\psi_{2}(s)$,
$g_{0}=\min_{s}{g(s)}$. Additionally, $\varepsilon_{0}$ is determined by the
maximum of the derivative of $H(s)$, given by

$\varepsilon_{0}=\max_{s}{\left<\psi_{1}(s)\left|\frac{\rm d}{{\rm
d}s}H(s)\right|\psi_{2}(s)\right>}.$ (4)

In simulation, the mapping from $s\in\left[0,1\right]$ to
$t\in\left[0,T\right]$ must be determined. The Quantum Adiabatic Algorithm
(QAA) farhi2000QAA ; farhi2001QAA  employs a straightforward approach by
utilizing a linearly varying system Hamiltonian

$H(t)=(1-\frac{t}{T})H_{B}+\frac{t}{T}H_{C},$ (5)

where $0\leq t\leq T$. Here $H_{B}$ represents the transverse field
$\sum_{j}\sigma_{x}^{(j)}$ and the initial state is the superposition state
$\left|+\right>^{\otimes n}$, where $\sigma_{x}^{(j)}$ denotes $\sigma_{x}$ on
the $j$-th qubit. Consequently, $\frac{\rm d}{{\rm d}t}H(t)$ is invariant and
the required evolution time of QAA is $\mathcal{O}(g_{0}^{-2})$.

###  II.3 Quantum approximate optimization algorithm

Combinatorial optimization is a pervasive problem with applications across
various domains COP2021 . Such problems typically involve a specific goal
function $C(x)$, where the aim is to find an optimal target $t$ from a finite
set $\\{x\\}$ that maximizes $C(x)$. The quantum approximate optimization
algorithm is designed to address these combinatorial optimization problems. It
formulates the problem Hamiltonian as
${{H}_{C}}\left|x\right>=C(x)\left|x\right>$, and seeks the target state
$\left|t\right>$ with maximal energy using a layered variational quantum
circuit expressed as

$\left|\bm{\gamma},\bm{\beta}\right>=\prod_{d=1}^{p}\left(e^{-i\beta_{d}H_{B}}e^{-i\gamma_{d}H_{C}}\right){{\left|+\right>}^{\otimes
n}}.$ (6)

Here mix Hamiltonian $H_{B}$ is transverse field $\sum_{j}\sigma_{x}^{(j)}$,
and $p$ represents the layer depth. The variational parameter
$(\bm{\gamma},\bm{\beta})$ are optimized to maximize the expectation
$\left\langle{{H}_{C}}\right>=\left\langle\bm{\gamma},\bm{\beta}\right|{{H}_{C}}\left|\bm{\gamma},\bm{\beta}\right\rangle$.

QAOA is inspired by the Trotterization of adiabatic quantum computation,
thereby sharing a similar framework with QAA. In simulation, the time-
dependent Hamiltonians $H(t)$ can be Trotterized as a sequence of time-
independent Hamiltonians using a sufficiently small $\Delta t$. Denoting
$p=T/\Delta t$, the Trotter formula enables the approximate simulation of
$H(t)$ for time $T$ through iterations of evolutions

$e^{iH(d\Delta t)}\approx e^{-i(1-\frac{d\Delta t}{T})H_{B}\Delta
t}e^{-i\frac{d\Delta t}{T}H_{C}\Delta t},$ (7)

where $1\leq d\leq p$. This approximate simulation mirrors the framework of
QAOA, differing only in the evolution time of Hamiltonians that are adopted as
parameters in QAOA.

Generally, the diagonal $H_{C}$ can always be decomposed by the Walsh operator
Welch2014 , and for $k$-SAT, it can be further decomposed into the form of the
Ising model Lucas2014 . To analyze the statistical properties of $H_{C}$,
another problem-oriented operator for $H_{C}$ of $k$-SAT is provided. A
Boolean conjunctive
$c=(\lnot)x_{c_{1}}\land(\lnot)x_{c_{2}}\land\cdots(\lnot)x_{c_{k}}$ can be
denoted as $(\pm c_{1},\pm c_{2},\cdots,\pm c_{k})$, where $+c_{t}$ stands for
$x_{c_{t}}$ and $-c_{t}$ for $\lnot x_{c_{t}}$. The corresponding problem
Hamiltonian of $c$ is written as

${{p}_{c}}=\sigma_{z^{\mp}}^{(c_{1})}\otimes\sigma_{z^{\mp}}^{(c_{2})}\otimes\cdots\otimes\sigma_{z^{\mp}}^{(c_{k})},$
(8)

where $\pm c_{j}$ corresponds to $\sigma_{z^{\mp}}^{(c_{j})}$.
$\sigma_{z^{\pm}}^{(c_{j})}$ is $\sigma_{z^{\pm}}$ on the $c_{j}$-th bit,
where $\sigma_{z^{\pm}}=\frac{1}{2}(I\pm\sigma_{z})$ are the corresponding
components of $\sigma_{z}$ on $\left|0\right>$ and $\left|1\right>$, in matrix
form as

$\sigma_{z^{+}}=\begin{bmatrix}1&0\\\
0&0\end{bmatrix},\quad\sigma_{z^{-}}=\begin{bmatrix}0&0\\\ 0&1\end{bmatrix}.$
(9)

For $k$-SAT, every clause $\alpha$ is a Boolean disjunctive, presented as
$\alpha=(\lnot)a_{c_{1}}\lor(\lnot)a_{c_{2}}\lor\cdots(\lnot)a_{c_{k}}$.
Denoting $\bar{\alpha}=(\mp a_{1},\mp a_{2},\ldots,\mp a_{k})$,
$H_{\alpha}=-p_{\bar{\alpha}}$. Consequently, the problem Hamiltonian of
$k$-SAT is written as

${{H}_{C}}=-\sum\limits_{\alpha}{p}_{\bar{\alpha}}.$ (10)

This Hamiltonian reduces to the Ising model by bringing in
$\sigma_{z^{\pm}}=\frac{1}{2}(I\pm\sigma_{z})$ Lucas2014 . The evolution
$e^{i\theta H_{\alpha}}$ is a $(k-1)$-control phase gate, with a circuit
complexity of ${\mathcal{O}}(k)$ Barenco1995 ; Saeedi2013 . Here the phase
gate refers to the gate $e^{i\theta\sigma_{z^{-}}}$, denoted as $P_{\theta}$
in this paper, in matrix form as

$P_{\theta}=\begin{bmatrix}1&0\\\ 0&e^{i\theta}\end{bmatrix}.$ (11)

In Figure 2, an example is presented.

##  III Hamiltonian preprocessing of QAOA based on random $k$-SAT model

Based on the random $k$-SAT model $F_{f}(n,m,k)$ and the Hamiltonian
decomposition with $P$ operator, as presented in Section II, an analysis of
the statistical properties of problem Hamiltonian $H_{C}$ for $k$-SAT can be
conducted. Examining the process of $F_{f}(n,m,k)$ in clauses selection, since
every $\alpha$ is randomly chosen, the diagonal Hamiltonian $H_{\alpha}$ can
be viewed as a random vector, and its eigenvalues $E_{\alpha,x}$ at
$\left|x\right>$ also become random variables. Due to the property that
$F_{f}(n,m,k)$ selectively picks clauses satisfiable by $t$, the mean of
${{E}_{\alpha,x}}$ can be determined as

${{\mu}_{k,x}}=\frac{{{2}^{k}}-2}{{{2}^{k}}-1}+\frac{C_{l}^{k}}{\left({{2}^{k}}-1\right)C_{n}^{k}}\leq
1,$ (12)

and the variance is

$\sigma_{k,x}^{2}={{\left(1-{{\mu}_{k,x}}\right)}^{2}}{{\mu}_{k,x}}+\frac{\mu_{k,x}^{2}\left(C_{n}^{k}-C_{l}^{k}\right)}{\left({{2}^{k}}-1\right)C_{n}^{k}}\leq\frac{1}{{{2}^{k}}-1},$
(13)

where $l=n-{{d}_{H}}(x,t)$ and $d_{H}(x,t)$ is the Hamming distance between
binary strings $x$ and $t$. For the eigenvalue of $H_{C}$,
${\mathcal{E}}_{k,x}=\sum_{\alpha}E_{\alpha,x}$. It is notable that each
$\alpha$ is independently selected from the same clause set. Consequently,
$E_{\alpha,x}$ forms a sequence of independent and identically distributed
(i.i.d.) random variables. According to the central limit theorem,
${\mathcal{E}}_{k,x}/m$ approximately follows the normal distribution such
that

$\sqrt{m}\left(\frac{1}{m}{\mathcal{E}}_{k,x}-{{\mu}_{k,x}}\right)\sim
N(0,\sigma_{k,x}^{2}).$ (14)

Evidently, the eigenvalue magnitude of $H_{C}$ is on the order of
${\mathcal{O}}(m)$, while for the mix Hamiltonian
$H_{B}=\sum_{j}\sigma_{x}^{(j)}$, the eigenvalue magnitude is on the order of
${\mathcal{O}}(n)$. In the context of the $k$-SAT problem, the number of
clauses $m$ can reach ${\mathcal{O}}(n^{k})$ at most. This disparity results
in a substantial energy difference between $H_{C}$ and $H_{B}$. Although this
difference can be mitigated by adjusting ${\bm{\gamma}}$ and ${\bm{\beta}}$,
the disparate magnitudes of parameters result in unnecessary difficulty during
parameter adjusting. To address this, a preprocessing step can be employed to
(approximately) normalize these two Hamiltonians, thereby reducing the maximal
energy difference (the gap between the maximal and minimal energy) to 1.

The maximal energy difference of $H_{B}$ is determined as $2n$, while $H_{C}$
poses a challenge due to the exponential length of Hamiltonian in matrix form.
However, leveraging the analysis of the problem Hamiltonian of random $k$-SAT,
an estimate for $G_{0}$ can be derived. Referring to Eq. (14), it is
anticipated that the majority of eigenvalues ${{\mathcal{E}}_{k,x}}$ should
satisfy

${{\mu}_{k,x}}-\frac{{{c}_{0}}}{\sqrt{m({{2}^{k}}-1)}}\leq\frac{1}{m}{{\mathcal{E}}_{k,x}}\leq{{\mu}_{k,x}}+\frac{{{c}_{0}}}{\sqrt{m({{2}^{k}}-1)}},$
(15)

where ${{c}_{0}}$ is a constant not less than 3. Noting that
$\max\\{{{u}_{k,x}}\\}=1$ and
${{\mu}_{k,x}}+{{{c}_{0}}}/{\sqrt{m({{2}^{k}}-1)}}$ cannot exceed 1, an
estimation of lower bound of $G_{0}$ can be obtained by the maximal difference
of the majority of eigenvalues as

$\frac{1}{m}{{G}_{0}}\approx
1-\min\left\\{{{\mu}_{k,x}}-\frac{{{c}_{0}}}{\sqrt{m({{2}^{k}}-1)}}\right\\}.$
(16)

Therefore, the estimation $G_{E}$ can be determined as

$\frac{1}{m}{{G}_{E}}=\frac{1}{{{2}^{k}}-1}+\frac{{{c}_{0}}}{\sqrt{m({{2}^{k}}-1)}},$
(17)

This estimation, grounded in $F_{f}(n,m,k)$, can also be applied to
$F_{s}(n,m,k)$ due to the similarity between these two models. An experimental
comparison between this estimation $G_{E}$ and the actual $G_{0}$ of
$F_{s}(n,m,k)$ is conducted, with the results presented in Figure 3. The
simulation outcome demonstrates the effectiveness of this estimation for
$F_{s}(n,m,k)$, thereby normalizing the Hamiltonians as

$\bar{H}_{B}=\frac{H_{B}}{2n},\bar{H}_{C}=\frac{H_{C}}{G_{E}}.$ (18)

Figure 3: The comparative results of $G_{0}$ between the estimation $G_{E}$
and the statistical results obtained from 1000 random instances in
$F_{s}(20,m,3)$ with varying values of $m$. The blue round points represent
the estimation, while the red square points depict the statistical values,
with different shades indicating the frequency of occurrence. The estimation
serves as an approximate lower bound and closely aligns with the darkest
square points in the figure.

##  IV Parameter setting method

###  IV.1 QAA-inspired parameter initialization

Due to the similarity between the Trotterization of QAA and QAOA, a natural
consideration is to initialize the parameters by a linearly varying $H(t)$,
akin to the TQA initialization Sack2021 . Combined with the normalization of
the Hamiltonian in Eq. (18), the parameterized system Hamiltonian should take
the form of

$\bar{H}(t)=\frac{t}{T}f_{\gamma}\bar{H}_{C}+\frac{T-t}{T}f_{\beta}\bar{H}_{B}$
(19)

with considerations for the degrees of freedom. Here, $f_{\gamma}$ and
$f_{\beta}$ describe the intensities of the problem Hamiltonian and mix
Hamiltonian in the evolution, respectively. After normalization, the energy of
$\bar{H}_{B}$ and $\bar{H}_{C}$ should be in the same order of magnitude.
Heuristically, the magnitudes of $f_{\gamma}$ and $f_{\beta}$ should also be
similar. Therefore, by treating the intensities of $f_{\gamma}$ and
$f_{\beta}$ as a single parameter $\rho$, the evolution of QAOA with linear-
varying parameters can be viewed as the Trotterization of the evolution of the
Hamiltonian

$\bar{H}(\theta,t)=\frac{t}{T}\sin{\theta}\bar{H}_{C}+\frac{(T-t)}{T}\cos{\theta}\bar{H}_{B},$
(20)

with $T=2p\rho\pi$ and a discretization interval $\Delta t=2\rho\pi$. In the
context of QAOA with depth $p$, the parameters $(\gamma,\beta)$ can be
expressed as

$\gamma_{d}=\frac{2d\pi}{(p+1)}\rho\sin{\theta},\beta_{d}=\frac{2(p-d+1)\pi}{(p+1)}\rho\cos{\theta},$
(21)

where $1\leq d\leq p$. The choice of $p+1$ is made to avoid boundary
situations where $\gamma_{d}$ or $\beta_{d}$ become 0 or $2\pi$.

The initialization of the $2p$ parameters of QAOA is simplified by setting the
values for $\theta$ and $\rho$. $\theta$ parameterizes the relative intensity
ratio between $\bar{H}_{C}$ and $\bar{H}_{B}$. Due to the normalization of the
Hamiltonian, it is natural to set $\theta=\pi/4$. The parameter $\rho$
describes the discretization width of QAA and also the evolution time of each
layer of QAOA. Although there is no prior knowledge about the expected value
of $\rho$, it has a natural initialization without drawbacks, specifically
$\rho=\sqrt{2}$. The rationale behind this choice is as follows: In QAOA, the
only problem-dependent operator is $H_{C}$, that is, the evolution
$e^{-i\gamma H_{C}}$, which essentially induces phase shifts $e^{-i\gamma
C(x)}$ on every computational basis $\left|x\right>$. Consequently, the target
is distinguished by the phase shifts. To best distinguish the target $t$,
$e^{-i\gamma C(t)}$ should be different from the others. Due to the
periodicity of the phase, a fundamental consideration is to restrict the range
of $\gamma C(x)$ to $\left[0,2\pi\right)$. With the normalized $\bar{H}_{C}$,
$f_{\gamma}$ can be initialized as 1, and $\rho=\sqrt{2}$.

Figure 4: The distribution of the count when obtaining the target state upon
measurement. For each pair of $(f_{\gamma},f_{\beta})$, the final state is
measured 10,000 times. This simulation is conducted on a random instance in
$F_{s}(12,m,3)$. To emphasize the effect of normalization, $H_{C}$ is
normalized by its real $G_{0}$. Furthermore, for application on NISQ devices,
the depth $p$ of QAOA is fixed as $n$.

A simulation has been conducted to validate the proposed initialization. For a
random instance in $F_{s}(12,m,3)$, Figure 4 depicts the probability of the
target state $\left|t\right>$ across various values of $f_{\gamma}$ and
$f_{\beta}$. The simulation results reveal that the probability increases most
rapidly around the axis $f_{\gamma}=f_{\beta}$ and soon reaches the optimum.
Notably, in the vicinity of $(f_{\gamma}=1,f_{\beta}=1)$, a pronounced
gradient is observed toward the optimum. Deviation from this axis results in a
diminished gradient and an increased distance from the optimum. Additionally,
when $(f_{\gamma},f_{\beta})$ crosses a certain threshold, a notable decrease
in probability occurs, with gradient nearly disappearing. This observation
underscores the effectiveness of Hamiltonian normalization in setting the
parameters.

Notably, a larger $\rho$ implies more evolution time within the specific
interval of evolution. Given the generally insufficient depth in QAOA, a
reasonably larger $\rho$ corresponds to extended evolution time and tends to
yield better performance. Consequently, as $n$ increases, while the optimal
$\theta^{*}$ persists around $\pi/4$, the optimal $\rho^{*}$ should gradually
increase with $n$, as illustrated in Figure 4. In this context, the
statistical optimum $(\bar{\theta^{*}},\bar{\rho^{*}})$ for general instance
can be approximately estimated from this distribution.

Figure 5: The distribution of optimal $(\theta^{*},\rho^{*})$ for 100 random
instances of $F_{s}(n,m,3)$ presented in a polar coordinate system. Different
values of $n$, specifically $n=8,12,16,20$, are distinguished by different
colors and shapes: red circles, green triangles, blue squares, and purple
crosses, respectively. In the inner figure, the optimal $\theta^{*}$ generally
centers around $\pi/4$, while $\rho^{*}$ exhibits a linear increase with $n$.
Three idealized conditions are considered: first, the problem Hamiltonian
$H_{C}$ is normalized by its accurate $G_{0}$; second, the probability of the
target state is set as the optimization objective to maximize the fidelity;
third, an exhaustive search is employed to identify the optimal parameters.

The TQA initialization seeks to identify the statistical optimum
$(\bar{\theta^{*}},\bar{\rho^{*}})$ in the pre-computation stage. This
consideration holds merit, particularly when adopting our normalized
Hamiltonian, as it contributes to a substantial reduction in pre-computation
costs owing to the direct guidance regarding the optimal region. However, for
situations where optimal parameters $(\theta^{*},\rho^{*})$ significantly
deviate from the estimates $(\bar{\theta^{*}},\bar{\rho^{*}})$, initialization
with a larger gradient is preferable, other than the overfitted parameters.
Consequently, the QAA-inspired parameter initialization method is formulated
as presented in Algorithm 1. Moreover, this initialization method can be
adapted into a QAA-inspired parameter setting method by optimizing
$\left<H_{C}\right>$ through adjustments in $\theta$ and $\rho$. This
modification is suitable for scenarios with strictly limited optimization
costs.

###  IV.2 Alternative parameter space based on continuity of adiabatic passage

The QAA-inspired initialization method enables the setting of $2p$ parameters
without incurring any optimization cost or pre-computation, but it cannot
fully exploit the computational potential of the circuit. The inefficiency of
QAA in utilizing the quantum circuit can be demonstrated by a simple
modification, namely, segmented QAA. In segmented QAA, the entire evolution is
divided into several segments as ${H(s_{0}),H(s_{1}),...,H(s_{p})}$, and each
segment $\left(H(s_{d-1}),H(s_{d})\right]$ applies QAA with a system
Hamiltonian presented in Eq. (20) independently. In this approach, the minimal
gap of each segment is only determined by $g(s)$ with
$s\in\left(s_{d-1},s_{d}\right]$, rather than the global minimum $g_{0}$. As
not every segment has a minimal gap as $g_{0}$, the required evolution time in
each segment is reduced. Consequently, the overall required time is decreased,
leading to a reduction in the depth of the circuit.

Algorithm 1 QAA-inspired initialization for QAOA

Random model of problem $F$, QAOA’s depth $p$;

Initial parameters $(\bm{\gamma},\bm{\beta})$, normalized $\bar{H}_{C}$ and
$\bar{H}_{B}$;

1:Estimate the maximal energy difference $G_{E}$ of $H_{C}$ based on $F$, and
set $\bar{H}_{C}\leftarrow H_{C}/G_{E}$ and $\bar{H}_{B}\leftarrow H_{B}/2n$;
$\triangleright$ Normalize Hamiltonians.

2:$\gamma_{d}\leftarrow\frac{2d\pi}{p+1}$,
$\beta_{d}\leftarrow\frac{2(p+1-d)\pi}{p+1}$, and the evolution is
$\prod_{d=1}^{p}e^{-i\beta_{d}\bar{H}_{B}}e^{-i\gamma_{d}\bar{H}_{C}}$.
$\triangleright$ Set initial parameters.

If the number of segments is large, each segment can be made small enough. For
a small segment $\left(s_{d}-\Delta s,s_{d}\right]$, the minimal required
evolution time should satisfy $T_{d}\sim\varepsilon(s_{d})g^{-2}(s_{d})$. As
the segment size $\Delta s\to 0$, the required time for the optimal evolution
in the entire interval $\left[0,1\right]$ should satisfy

$T\sim\int_{0}^{1}{\varepsilon(s)g^{-2}(s){\rm d}s}.$ (22)

To characterize this optimal evolution, the concept of adiabatic passage is
introduced. According to the adiabatic theorem outlined in Section II.2,
$H(s)$ can be fixed to a certain extent for a specific problem. However, the
mapping from $s$ to $t$ can vary, resulting in different possible system
Hamiltonians $H(t)$. Regardless, $H(t)$ always adheres to the form

$H(t)=f_{C}(t)H_{C}+f_{B}(t)H_{B},$ (23)

where $f_{C}(0)=0$, $f_{B}(0)>0$, $f_{C}(T)>0$, $f_{B}(T)=0$, and $0\leq t\leq
T$. As $t$ increases, $H(t)$ gradually transitions from $H_{B}$ to $H_{C}$,
and the pair $(f_{C}(t),f_{B}(t))$ completely describes the precise evolution
process, denoted as $\bm{f}(t)$, termed adiabatic passage (AP) in this paper.
The optimal adiabatic passage achieves the minimal evolution time $T^{*}$
while ensuring sufficient fidelity. Importantly, the optimal adiabatic passage
$\bm{f}^{*}(t)$ is always continuous with respect to $t$. A straightforward
proof can be offered by counter-evidence: if the optimal adiabatic passage are
not continuous, a better adiabatic passage can be found by linear
interpolation, resulting in a reduction in the evolution time by a smaller
$\frac{{\rm d}H(t)}{{\rm d}t}$ in the discontinuous intervals.

To simulate the optimal evolution, the optimal adiabatic passage is
discretized into $p$ intervals. For the $d$-th interval
$\left(t_{d-1},t_{d}\right]$, the evolution is approximated as

$e^{iH(t_{d})\Delta t}\approx e^{if^{*}_{C}(t_{d})\Delta
t_{d}H_{C}}e^{if^{*}_{B}(t_{d})\Delta t_{d}H_{B}},$ (24)

where $\Delta t_{d}=t_{d}-t_{d-1}$. QAOA parameterizes the unknown time in the
evolution with parameters $\gamma_{d}=f^{*}_{C}(t_{d})\Delta t_{d}$ and
$\beta_{d}=f^{*}_{B}(t_{d})\Delta t_{d}$, aiming to approximate the optimal
adiabatic passage $\bm{f}^{*}(t)$ through adjustments in parameters. If there
is no information about $\bm{f}^{*}(t)$, this straightforward parameterization
is optimal. However, $\bm{f}^{*}(t)$ is known to be continuous, providing an
opportunity for a more refined parameterization of $\bm{f}(t)$.

In the evolution described by Eq. (24), three explicit factors are involved:
$\Delta t_{d}$, $f^{*}_{C}(t_{d})$, and $f^{*}_{B}(t_{d})$. The relationship
among these three factors is determined by the optimality of $f^{*}_{C}(t)$
and $f^{*}_{B}(t)$. Consequently, according to the adiabatic approximation,
the evolution time $\Delta t$ follows

$\Delta t_{d}\sim\varepsilon(t_{d})g^{-2}(t_{d}).$ (25)

Based on Eq. (4), the main factors influencing $\varepsilon(t_{d})$ are
$\frac{{\rm d}H(t)}{{\rm d}t}$. Therefore, it is $(\Delta
f^{*}_{C}(t_{d}),\Delta f^{*}_{B}(t_{d}))$ that directly affects $\Delta
t_{d}$, rather than $(f^{*}_{C}(t_{d}),f^{*}_{B}(t_{d}))$. In reality, four
internally related factors are involved in the evolution, namely, $\Delta
t_{d}$, $g(t_{d})$, $\Delta f^{*}_{C}(t_{d})$, and $\Delta f^{*}_{B}(t_{d})$.
Here for convenience, denote $\Delta
f^{*}_{C}(t_{d})=f^{*}_{C}(t_{d})-f^{*}_{C}(t_{d-1})$ and $\Delta
f^{*}_{B}(t_{d})=f^{*}_{B}(t_{d-1})-f^{*}_{B}(t_{d})$.

Because the gap $g(t)$ is an inherent property of the Hamiltonian that cannot
be adjusted by parameters, it can be regarded as an independent variable. The
other three factors depend on $g(t_{d})$ and correspondingly exhibit different
levels of continuity. In fact, discrete variables have no continuity in the
strict sense, and better continuity here refers to a smaller difference in the
corresponding factors between adjacent intervals. Based on Eq. (25), $\Delta
f^{*}_{C}(t_{d})$ and $\Delta f^{*}_{B}(t_{d})$ should be quadratically
positively correlated with $g(t_{d})$, while $\Delta t_{d}$ is quadratically
inversely related to $g(t_{d}).$ Besides, these factors are also restricted by
the Trotterization constraint, thus the magnitude of the factors cannot be too
large. Specifically, when $g(t_{d})$ becomes small, $\Delta f^{*}_{C}(t_{d})$
and $\Delta f^{*}_{B}(t_{d})$ mainly reduce, rather than quadratically
increasing $\Delta t_{d}$.

The continuity of parameters is crucial in parameter setting; therefore, the
parameterization of the adiabatic passage should maintain the best continuity
of these factors. Obviously, $\Delta f^{*}_{C}(t_{d})$ exhibits better
continuity compared to the summation $f^{*}_{C}(t_{d})=\sum_{j=1}^{d}\Delta
f^{*}_{C}(t_{j})$. Besides, according to the analysis of the normalized
Hamiltonian in Section III and IV.1, $\Delta f^{*}_{C}(t_{d})$ and $\Delta
f^{*}_{C}(t_{d})$ should exhibit similar properties to $f_{\gamma}$ and
$f_{\beta}$. Consequently, $(\Delta f^{*}_{C}(t_{d}),\Delta f^{*}_{C}(t_{d}))$
can be mapped as $(\rho_{d}\sin{\theta_{d}},\rho_{d}\cos{\theta_{d}})$. A
straightforward consideration is to directly parameterize these three
dependent factors and its mapping to $({\bm{\gamma}},{\bm{\beta}})$ can be
expressed as

$\gamma_{d}=\sum_{j=1}^{d}\rho_{j}\sin{\theta_{j}}\Delta
t_{d},\beta_{d}=\sum_{j=d}^{p}\rho_{j}\cos{\theta_{j}}\Delta t_{d}.$ (26)

Here, $\theta_{d}$ represents the intensity ratio between the increments of
$H_{C}$ and $H_{B}$ in the $d$-th interval and has an approximate expectation
of $\pi/4$ if the Hamiltonian is properly normalized. It certainly exhibits
good continuity. On the other hand, $\rho_{d}$ describes the intensity of
${\rm d}H(t)$ and is positively correlated with $g(t_{d})$. Comparing it to
the individual components $\Delta f^{*}_{C}(t_{d})$ or $\Delta
f^{*}_{C}(t_{d})$ alone, $\rho_{d}$ exhibits better continuity.

This ternary parameterization provides good continuity and interpretability in
parameters. However, the presence of $3p$ parameters introduces higher
optimization costs. To reduce the number of parameters, an approximation can
be made by extracting the increasing (or decreasing) factor in the summation
alone, specifically for $H_{C}$ as an example, denoted as

$\kappa_{d}=\frac{1}{p\rho_{d}\sin{\theta_{d}}}\sum_{j=1}^{d}\rho_{j}\sin{\theta_{j}}.$
(27)

The term $\rho_{j}\sin{\theta_{j}}$ for each layer can be approximately
regarded as i.i.d. random variables. As $d$ increases, a linear increase would
gradually dominate, and this factor should take a form as
$\kappa_{d}=\frac{d}{p}+\Delta\kappa_{d}$.

In Eq. (26), $\gamma_{d}$ can be rewritten as $p\kappa_{d}\rho_{d}\Delta
t_{d}\sin{\theta_{d}}$. Since $\rho_{d}$ and $\Delta t_{d}$ exhibit opposite
correlations with $g(t_{d})$, $\rho_{d}\Delta t_{d}$ demonstrates better
continuity. On the other hand, $\sum_{d=1}^{p}\Delta t_{d}=T$, so $\Delta
t_{d}$ is approximately inversely proportional to $p$. Consequently,
$p\rho_{d}\Delta t_{d}$ can be combined into a single parameter $\tau_{d}$
with improved continuity. Regarding $\kappa_{d}$, the lower-order term
$\Delta\kappa$ can be divided into intensity effects and angle effects,
merging into $\tau_{d}$ and $\theta_{d}$, respectively. As a result, the
parameter space is reduced to $({\bm{\theta},\bm{\tau}})$, and its mapping
with the original $({\bm{\gamma}},{\bm{\beta}})$ is

$\gamma_{d}=\frac{d}{p+1}\tau_{d}\sin{\theta_{d}},\beta_{d}=\frac{p+1-d}{p+1}\tau_{d}\cos{\theta_{d}},$
(28)

where the choice of $p+1$ is made to avoid boundary situations.

###  IV.3 Adiabatic-passage-based parameter setting method

By employing a specific initialization, the resulting parameters can be
conceptualized as an estimate of the optimal adiabatic passage
$\bm{f}^{*}(t)$. The parameter setting process aims to minimize the distance
from the estimation $\bm{f}(t)$ to the optimum $\bm{f}^{*}(t)$ through
parameter adjustment, specifically, minimizing
$\left\|\Delta\bm{f}(t)\right\|$, where
$\Delta\bm{f}(t)=\bm{f}_{C}(t)-\bm{f}^{*}(t)$. Given the continuity of the
function, the norm $\left\|f(x)\right\|=\max_{x}\\{\left|f(x)\right|\\}$ is
employed. According to the method in Section IV.1, a substantial gradient can
be anticipated around the initialization, guiding the optimization in
parameter adjustment. Consequently, apart from the precision $\epsilon$, the
primary factor influencing the optimization cost is the distance
$\left\|\Delta\bm{f}(t)\right\|$. When $\left\|\Delta\bm{f}(t)\right\|$ is
constant, constant gradient calculations are required, with each gradient
calculation necessitating $\mathcal{O}(p)$ circuit runs. Given the
distribution of optimal $(\theta^{*},\rho^{*})$ depicted in Figure 5, it is
anticipated that $\left|\Delta\bm{f}(t)\right|$ is generally bounded with the
normalized Hamiltonian. If further normalizing the magnitude of parameters to
be $\mathcal{O}(n)$, constant gradient calculations can be achieved.

As a result, the optimization cost is reduced to approximately linear with
respect to $p$ in the idealized situation. Actually, for this type of
parameter adjusting process, a kind of “synchronous adjustment” exhibits
better performance. The primary objective of the parameterized adiabatic
passage is to utilize $p$ “samplings” to simulate the optimal adiabatic
passage. Therefore, it is more practical to commence the process with a small
number of sampling points to adjust the main components. and then gradually
increase the number to $p$ to better align with the details of optimal
adiabatic passage, akin to the FOURIER strategy introduced in PRX2020 .

Specifically, FOURIER introduces an indicator $q$ to represent the current
number of sampling points. It decomposes $\bm{f}(t)$ into $q$ components using
the cos/sin Fourier transform. With a linear increase in $q$, the optimal
parameters from the previous iteration can be utilized as the initialization,
resulting in the distance $\left\|\Delta\bm{f}_{d}(t)\right\|$ for the $d$-th
component being approximately reduced to less than
$\left\|\Delta\bm{f}(t)\right\|/q$ on average. This reduction contributes to a
decrease in optimization cost in each iteration. However, with
$\mathcal{O}(n)$ iterations in the outer loop, the optimization cost persists
superlinear.

It is noteworthy that the approximate adiabatic passage with any number of
sampling points can serve as an initialization for another approximation with
more sampling points by interpolation. Consequently, we refine this approach
by doubling the sampling points for each iteration other than linear
increasing, aiming to mitigate the optimization cost from the iterations of
outer loop. In the $l$-th iteration, $2^{l}$ sampling points are employed, and
the initial parameters are obtained through interpolation of previous
$2^{l-1}$ parameters. Assuming sufficient continuity in the parameter space,
the distance $\left\|\Delta f_{j}(t)\right\|$ of the $j$-th interval, where
$1\leq j\leq 2^{l}$, can be approximately reduced to a level of $\left\|\Delta
f(t)\right\|/2^{l}$, resulting in only logarithmic iterations and potentially
an overall cost of $\mathcal{O}(\log(p))$. The corresponding parameter setting
method is presented in Algorithm 2.

Algorithm 2 AP-based parameter setting for QAOA

Normalized $\bar{H}_{C}$ and $\bar{H}_{B}$, routine $Interp(\bm{v},L)$ that
interpolates vector $\bm{v}$ to a length of $L$;

The quasi-optimal parameters $(\bm{\theta},\bm{\tau})$;

1:Initial $\theta_{0}=\pi/4,\tau_{0}=\sqrt{2}$, and optimize
$\theta_{0},\tau_{0}$ by the QAA-inspired setting to $\theta^{*}_{0}$ and
$\tau^{*}_{0}$;

2:$\bar{H}_{C}\leftarrow\sqrt{2}\tau^{*}_{0}\sin\theta^{*}_{0}\bar{H}_{C}$,
$\bar{H}_{B}\leftarrow\sqrt{2}\tau^{*}_{0}\cos\theta^{*}_{0}\bar{H}_{B}/$,
$T_{u}\leftarrow\left\lfloor\log_{2}{p}\right\rfloor$, and initialize
$\bm{\theta}\leftarrow(\pi/4)$, $\bm{\tau}\leftarrow(1)$;

3:If $T_{u}\leq 0$, finish; otherwise, $T_{u}\leftarrow T_{u}-1$,
$\bm{\theta}\leftarrow
Interp(\bm{\theta},\left\lceil{p/2^{T_{u}}}\right\rceil)$,
$\bm{\tau}\leftarrow Interp(\bm{\tau},\left\lceil{p/2^{T_{u}}}\right\rceil)$;

4:$\bm{\theta^{\prime}}\leftarrow Interp(\bm{\theta},p)$,
$\bm{\tau^{\prime}}\leftarrow Interp(\bm{\tau},p)$, adjust
$\bm{\theta},\bm{\tau}$ to optimize
$\left<\bm{\theta^{\prime}},\bm{\tau^{\prime}}\left|H_{C}\right|\bm{\theta^{\prime}},\bm{\tau^{\prime}}\right>$,
then jump to Step 3.

In Require, this algorithm inherits the normalized Hamiltonian in Algorithm 1.
Besides, the interpolation routine is flexible, and in this paper, cubic
spline interpolation is employed. The explanation of each step is as follows.
In Step1, the optimal parameters for ${\bm{f}}^{*}(t)$ with one sampling are
obtained. Due to the refined parameter space, the magnitude of parameters with
any number of sampling points remains consistent. Consequently, Step 2
normalizes the parameter magnitude by introducing the optimized
$\rho^{*}_{0},\tau^{*}_{0}$ as coefficients into the Hamiltonian. Step 3 and
Step 4 gradually double the number of sampling points until reaching $p$. For
each iteration, the parameters are optimized and utilized as initialization
for the next iteration.

##  V Comparison and performance analysis

This section conducts a comparative analysis between the methodologies
presented in this paper and those from previous works, specifically the TQA
initialization in Sack2021 , along with the INTERP heuristic and FOURIER
heuristic proposed in PRX2020 . Furthermore, an analysis is dedicated to the
performance of the AP-based method, elucidating the observed logarithmic
increase in optimization cost.

Some details of the simulation are outlined as follows. Firstly, the depth $p$
maintains fixed at $n$ for the application on NISQ devices. Secondly, the
performance of QAOA is evaluated by the probability of the target state, in
accordance with the problem reduction in Section II.1. Regarding the parameter
setting method, the performance is assessed based on the optimization cost,
specifically, the required circuit runs to achieve a quasi-optimum of
parameters. Noteworthily, this is distinct from the number of epochs, which
entails the calculation of the full gradient and consequently involves
$\mathcal{O}(p)$ circuit runs. In the simulation, the required times to
calculate the expectation $\left<H_{C}\right>$ are presented. Thirdly, the
number of clauses $m$ is given by an experimental value $m_{n}^{*}$, where the
average number of interpretations is approximately 1.3. In the simulation,
$m_{n}^{*}=\mu_{n}n$, with $\mu_{n}$ slightly increasing from 5.9 to 6.3 as
$n$ ranges from 10 to 20. This is indicated as a challenging situation in
Achioptas2006 ; Kirousis1998 ; Coja2016 . Finally, a gradient-based
optimization routine (BFGS) is employed for classical optimization,
corresponding to the approach in PRX2020  for the sake of comparison.

###  V.1 Comparison of performance under linear-varying parameters

The QAA-inspired initialization can be adapted into a parameter setting method
involving two parameters $(\theta,\rho)$, consequently resulting in linear-
varying parameters $({\bm{\gamma}},{\bm{\beta}})$. The TQA initialization has
a similar transformation, with the only distinction lying in the initial
$(\theta,\rho)$ to be the statistical optimum
$(\bar{\theta}^{*},\bar{\rho}^{*})$ obtained by pre-computation, other than
analytical values $(\pi/4,\sqrt{2})$. The INTERP heuristic also employs
linearly varying parameters, with the specific steps presented in Algorithm 3.
Notably, the INTERP heuristic circumvents the discussion of parameters
initialization by commencing with a small depth. Consequently, the
initialization of QAOA with a larger depth is obtained by the optimized
parameters of QAOA with a smaller depth. A comparative simulation is conducted
for these methods on random instances in $F_{s}(n,m_{n}^{*},3)$. The
performance in terms of optimization cost and probability is illustrated in
Figure 6 and 7.

Algorithm 3 INTERP heuristic for QAOA

1:Randomly initialize $\gamma_{0},\beta_{0}$ in range $\left[0,2\pi\right]$,
$q\leftarrow 1$;

2:$\gamma_{d}\leftarrow\frac{d\gamma_{0}}{q+1}$,
$\rho_{d}\leftarrow\frac{(q+1-d)\beta_{0}}{q+1}$, where $1\leq d\leq q$;
adjust $\gamma_{0},\beta_{0}$ to optimize
$\left<\bm{\gamma},\bm{\beta}\left|H_{C}\right|\bm{\gamma},\bm{\beta}\right>$;

3:If $q\geq p$, terminate; otherwise, set $q\leftarrow q+1$ and jump to Step
2.

The QAA-inspired parameter setting method demonstrates superior performance
compared to the INTERP heuristic. Additionally, the QAA-inspired method shows
comparable performance with the TQA method without incurring any pre-
computation. It is noteworthy that, in the absence of the normalized
Hamiltonian, the pre-computation cost for TQA initialization would
significantly increase with $n$ in the worst-case scenario.

The high probability achieved by the QAA-inspired method is primarily
attributed to the normalized Hamiltonian and the corresponding feasible
initialization. Without this normalization, the optimal $\gamma_{0}$ for
INTERP on 3-SAT diminishes with increasing $m$. Consequently, the performance
of INTERP exhibits a high dependence on the initial parameter, specifically,
whether $\gamma_{0}$ is initialized sufficiently small. When $\gamma_{0}$ is
initialized with a random value in the range $[0,2\pi]$, the optimization
process tends to get trapped in a suboptimal local minimum. In terms of
optimization cost, the INTERP method exhibits linear growth with $n$ due to
the outer loop with $p$ iterations. Conversely, the QAA-inspired method,
benefiting from the analytical initialization, involves optimization with two
parameters without an outer loop, naturally resulting in a constant cost.
Additionally, due to the optimum $(\theta^{*},\rho^{*})$ distributing around
the statistical optimum $(\bar{\theta}^{*},\bar{\rho}^{*})$, the TQA method
requires fewer circuit runs, although the improvement is marginal.

Figure 6: The distribution of the target state probability for 100 random
instances in $F_{s}(n,m_{n}^{*},3)$ with $10\leq n\leq 20$. The results of the
INTERP heuristic, the QAA-inspired method and the TQA method are respectively
represented in green on the left, red in the middle, and blue on the right.
Figure 7: The distribution of optimization costs for 100 random instances in
$F_{s}(n,m_{n}^{*},3)$ with $10\leq n\leq 20$. The outcomes of the INTERP
heuristic, the QAA-inspired method and the TQA method are respectively
represented in green on the left, red in the middle, and blue on the right.

###  V.2 Comparison of performance under quasi-optimal parameters

The AP-based method optimizes $2p$ parameters and exhibits similarities with
the FOURIER heuristic, aiming to reduce optimization costs by capitalizing on
parameter continuity. Specifically, FOURIER constrains the degree of freedom
in the parameter space to a value of $q$ and then derives the complete
parameters through Sin/Cos Fourier transform. Similarly, the AP-based method
introduces an indicator $T_{u}$ to control the degree of freedom and obtains
the full parameters through interpolation. Although both methods may terminate
with parameter spaces of insufficient degrees of freedom, for the purpose of
performance comparison, optimization is conducted with the full parameter
space. The steps of the FOURIER heuristic in this context are presented in
Algorithm 4.

Noteworthily, the FOURIER heuristic is primarily designed for situations
lacking proper initialization, leading to $\mathcal{O}(n)$ iterations in the
outer loop. In contrast, the AP-based method inherits the advantage of the
QAA-inspired method, initiating with a well-established QAOA initialization at
the full depth. Furthermore, the AP-based method transforms the parameter
space of $({\bm{\gamma}},{\bm{\beta}})$ into another with enhanced continuity.
The TQA method also achieves a good initialization through pre-computation and
can also be utilized to optimize the full parameters by directly employing the
initial parameters in the optimization process without additional strategy. A
comparative simulation is conducted for these three methods on 100 random
instances in $F_{s}(n,m_{n}^{*},3)$, and the performance is presented in
Figures 8 and 9.

Figure 8: This distribution of the target state probability for 100 random
instances in $F_{s}(n,m_{n}^{*},3)$ with $10\leq n\leq 20$. The results of the
FOURIER heuristic, the AP-based method and the TQA method are respectively
represented in green on the left, red in the middle, and blue on the right.
Figure 9:  The distribution of optimization costs for 100 random instances in
$F_{s}(n,m_{n}^{*},3)$ with $10\leq n\leq 20$. The results of the FOURIER
heuristic, the AP-based method and the TQA method are respectively represented
in green on the left, red in the middle, and blue on the right. Due to the
difference in the amplitude of these results, a dual y-axis is utilized to
provide a clearer representation of the cost. Algorithm 4 FOURIER heuristic
for QAOA

1:Randomly initialize $\bm{u}=(u_{1}),\bm{v}=(v_{1})$, $q\leftarrow 1$;

2:Obtain $(\bm{\gamma},\bm{\beta})$ of length $q$ by Sin/Cos transform
$\gamma_{j}=\sum_{k=1}^{q}u_{k}\sin{((k-\frac{1}{2})(j-\frac{1}{2})\pi/q)}$,
$\beta_{j}=\sum_{k=1}^{q}v_{k}\cos{((k-\frac{1}{2})(j-\frac{1}{2})\pi/q)}$;
adjust $(\bm{u},\bm{v})$ to optimize
$\left<\bm{\gamma},\bm{\beta}\left|H_{C}\right|\bm{\gamma},\bm{\beta}\right>$
using QAOA of a depth $q$;

3:If $q\geq p$, terminate; otherwise, expand parameters
$\bm{u}\leftarrow(u_{1},...,u_{q},0)$, $\bm{v}\leftarrow(v_{1},...,v_{q},0)$,
and set $q\leftarrow q+1$. Jump to Step 2.

Comparing with FOURIER, both the AP-based and TQA methods exhibits superior
performance in terms of the success probability. The noteworthy success of
FOURIER on max-cut problems in PRX2020  underscores the importance of
Hamiltonian normalization and parameter initialization for problems like
3-SAT, where the intensity of the problem Hamiltonian experiences rapid
growth. Additionally, in this paper, the parameters are initialized only once,
resulting in poor performance for these heuristic strategies, which might get
trapped in a local optimum due to the absence of a known feasible
initialization.

In terms of optimization cost, FOURIER exhibits growth slightly faster than
${\mathcal{O}}(n^{2})$, with an average of 4853.65 when $n=10$ and 26121.76
when $n=20$. This magnitude results from two factors: the linear increase in
depth $q$, similar to INTERP, and the expanded degree of freedom of parameters
from 1 to $q$. For the TQA method, due to the proper initialization obtained
through pre-computation, the outer loop is eliminated, resulting in reduced
optimization costs slightly larger than $\mathcal{O}(n)$, with an average of
1326.99 when $n=10$ and 3523.13 when $n=20$. Notably, the AP-based method
further reduces the cost to a sublinear level. Further details about the cost
will be discussed in Section V.3.

###  V.3 Performance analysis

The average optimization costs of the AP-based method within the range of
$4\leq n\leq 20$ are outlined in Table 1. With the increase in the number of
variables $n$, both the depth $p$ and the number of parameters $2p$ undergo
augmentation. Correspondingly, the optimization cost experiences growth,
demonstrating a sublinear increase in the overall trend, with values of 300.5
when $n=4$ and 546.3 when $n=20$. However, it is noteworthy that the cost does
not exhibit a strict increase in simulation. Instead, this growth appears to
be confined to specific intervals and exhibits fluctuations upon transitioning
between them.

Table 1: The average optimization cost of AP-based method for 1000 random instances in $F_{s}(n,m_{n}^{*},3)$ with $4\leq n\leq 20$. The range of $n$ is partitioned by the logarithmic indicator $\left\lfloor\log_{2}{p}\right\rfloor$, resulting in three intervals: $4\leq n\leq 7$, $8\leq n\leq 15$, and $16\leq n\leq 20$, respectively.  $n$ | [4 | 5 | 6 | 7] | [8 | 9 | 10 | 11
---|---|---|---|---|---|---|---|---
cost | $300.5$ | $342.9$ | $379.5$ | $410.6$ | $430.4$ | $440.3$ | $445.0$ | $446.4$
12 | 13 | 14 | 15] | [16 | 17 | 18 | 19 | 20]
$532.2$ | $544.3$ | $586.0$ | $612.2$ | $524.9$ | $535.7$ | $573.5$ | $531.7$ | $546.3$

The intervals are demarcated by the logarithmic indicator $T_{u}$ with a value
$l=\left\lfloor\log_{2}{p}\right\rfloor$, which controls the outer loop of AP-
based method for increasing parameters. Precisely, the range of $n$ is divided
into three intervals: $4\leq n\leq 7$, $8\leq n\leq 15$, and $16\leq n\leq
20$. Within each interval of $n$, $l$ remains constant, while the number of
parameters undergoes incremental changes. When $n=2^{l}$, this interpolation
method is best suited, ensuring an accurate doubling of the parameter space
with every iteration. With further increasing $n$, the efficiency diminishes
due to the reduced continuity between parameters by interpolation, leading to
an increase in cost. Thus, the most representative results are expected when
$n=2^{l}$. For cases where $n=4,8,16$, the average costs are 300.5, 430.4, and
524.9, respectively, indicating an approximate linear relationship with $l$.
This observation suggests the potential for the optimization cost to exhibit a
logarithmic relationship with the depth $p$.

Moreover, specifically considering the case of $n=16$, the optimization cost
gradually rises with the decrease in the indicator $T_{u}$, leading to a
corresponding doubling of the degree of freedom of the parameters for each
iteration. The accumulated costs for each iteration are 40.7, 123.1, 294.7,
448.6, and 524.9, respectively. This cost exhibits an approximately linear
increase concerning $l-T_{u}$. Notably, the last three results are nearly
identical to the full cost when $n=4,8,16$. This observation reveals that the
optimization cost of this method appears to have little correlation with $n$
or $p$ but rather with the degree of freedom of parameters. Consequently, to
achieve the best efficiency of this method, the degree of freedom for
parameters can be set as $2^{l}$ or $2^{l+1}$ in practical applications when
$p\neq 2^{l}$. In such scenarios, the performance in terms of success
probability would be nearly maintained due to the continuity of optimal
adiabatic passage.

The efficiency of the proposed method can be attributed to the continuity of
optimal adiabatic passage, illustrated by the optimized parameters presented
in Figure 10. These optimized parameters exhibit a smooth continuity
reminiscent of trigonometric functions, with $\theta_{d}$ and $\rho_{d}$
centered around $\pi/4$ and $1$, respectively. In simulation, the impact of
the variation in $g(s)$ is significantly reduced, leading to
$\max_{d}\\{\tau_{d}\\}$ being no more than twice as much as
$\min_{d}\\{\tau_{d}\\}$ . Conversely, for $g(s)$, the maximum generally
differs by several times from the minimum. This outcome aligns with the
analysis detailed in Section IV, emphasizing the significance of Hamiltonian
normalization and parameter continuity. Additionally, it reveals the potential
suitability of the Sin/Cos Fourier transform in leveraging the continuity of
parameters spaces $({\theta},{\tau})$. The interpolation routine is employed
in this paper primarily due to its simplicity.

Figure 10:  The distribution of the optimized parameters ${\bm{\theta}}^{*}$
and ${\bm{\tau}}^{*}$ for 100 random instances in $F_{s}(20,m_{n}^{*},3)$,
presented in red on the left and blue on the right, respectively. The
optimized parameters general present superior continuity reminiscent of
trigonometric functions, with even the outliers persisting very close to the
adjacent parameters.

In practical implementation, the expectation is obtained through multiple
repetitions of the circuit with the given parameters, typically involving 1000
circuit runs. The circuit complexity of a single circuit run depends on
$H_{C}$ and $p$, specifically ${\mathcal{O}}(mp)$. Although it seems to
suggest a large total cost, in reality, due to the preprocessing and the
initialization, the circuit of QAOA exhibits commendable performance initially
that requires only a few circuit runs, as revealed in Figure 6. Nonetheless,
the parameter setting method remains crucial due to the problem reduction in
Section II.1 when handling unsatisfiable instances. Given an acceptable time
$T={\mathcal{O}}({\rm Poly}(n))$ to terminate the optimization, an efficient
parameter setting method converges more rapidly to the quasi-optimum of
parameters, resulting in a smaller error rate. Consequently, the algorithm
also applies on general instances of 3-SAT.

##  VI Discussion

While the analyses and simulations in this paper are centered around 3-SAT
problem, the proposed framework is universally applicable. For other
combinatorial optimization problems, a random model can also be established.
Building on this, the random Hamiltonian of this model can be constructed,
where different techniques might be required, including problem reduction,
model approximation, etc. Subsequently, by analyzing the statistical
properties of the random Hamiltonian, it becomes possible to derive an
estimate for the maximum energy difference of $H_{C}$. Consequently, the
parameter setting method outlined in this paper remains applicable in this
broader context.

For combinatorial optimization problems related to graphs, such as max-cut and
max-clique, natural random models like the Erdős-Rényi model are available.
The distribution of eigenvalues for the given problem Hamiltonian can be
established accordingly. In PRX2020 , max-cut on 3-regular graph is mainly
discussed. It is noteworthy that the maximum eigenvalue of $H_{C}$ cannot
exceed the total number of edges, i.e., $1.5n$, remaining in the same
magnitude with that of $H_{B}$. Consequently, the INTERP and FOURIER heuristic
demonstrate a high probability of reaching the target state. However, when
regarding k-regular graph with a larger $k$ or random graphs $G(n,\rho)$, the
normalization of Hamiltonian becomes crucial for achieving a good
initialization. Besides, for constrained combinatorial optimization like max-
clique, the problem Hamiltonian varies with the specific design of goal
function $C(x)$, but the distribution can still be derived.

Certainly, there are combinatorial optimization problems that lack established
popular random models. Nevertheless, in the domain of combinatorial
optimization, a comprehensive set of problem instances always exists,
providing the opportunity to design specific random models. Taking the set
cover problem as an example, a random model can be constructed through problem
reduction by imposing constraints on the size of each subset to a fixed value
of $k$. In this context, for the full set $U$ with $n$ elements, each subset
$S_{j}\subset U$ is defined such that $\left|S_{j}\right|=k$. Consequently, by
uniformly, independently, and with replacement selecting $m$ subsets from the
possible $C_{n}^{k}$ subsets, a random model akin to $F(n,m,k)$ can be
formulated. Moreover, even in situations where constructing or analyzing the
random model proves challenging, experimental approaches can be employed to
obtain feasible approximations.

##  VII Conclusion

This paper presents an efficient method for parameter setting of QAOA. The
efficiency of the method is rooted in two primary aspects. Firstly, a
preprocessing step, guided by the statistical properties of the specific
problem’s random model, is employed for the normalization of the Hamiltonian.
Building on this, a robust initialization is obtained without incurring any
optimization cost or pre-computation. Secondly, leveraging the analysis of the
continuity of optimal adiabatic passage, the original parameter space
$(\gamma,\beta)$ is transformed into $(\theta,\tau)$ to enhance the smoothness
between parameters in adjacent layer of QAOA. Subsequently, an adiabatic-
passage-based parameter setting method grounded in the continuity between
optimal parameters is proposed, potentially exhibiting logarithmic
optimization cost concerning $p$. Specifically, this method is applied to
3-SAT with an analysis of the random $k$-SAT model. The performance on random
instances of 3-SAT aligns with the analysis, showcasing a superior advantage
in parameter adjustment for QAOA.

Opportunities for methodological enhancement exist, such as exploring
alternative parameterizations for optimal adiabatic passage and applying other
methods to utilize the continuity. Furthermore, additional avenues for
research beyond the scope of this method are identified as follows. Firstly, a
more comprehensive exploration of the complexity of random 3-SAT can be
undertaken, building upon the analyses and methodologies presented in this
work. Secondly, applications can be extended to problems beyond the realm of
combinatorial optimization.

## Acknowledgements

We acknowledge support by Innovation Program for Quantum Science and
Technology (Grant Nos. 2021ZD0302900) and Natural Science Foundation of
Jiangsu Province, China (Grant No.BK20220804).

## References

  * (1) M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press (2010).
  * (2) P. W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing 41, 303–332 (1997).
  * (3) L. K. Grover, Quantum Mechanics Helps in Searching for a Needle in a Haystack, Physical Review Letters 79, 325 (1997).
  * (4) A. W. Harrow, A. Hassidim and S. Lloyd, Quantum algorithm for linear systems of equations, Physical Review Letters 103, 150502 (2009).
  * (5) J. Preskill , Quantum Computing in the NISQ era and beyond, Quantum 2, 79 (2018).
  * (6) M. Cerezo, A. Arrasmith, R. Babbush, et al., Variational quantum algorithms, Nature Reviews Physics 3, 625–644 (2021).
  * (7) J. Biamonte, P. Wittek, N. Pancotti, et al., Quantum machine learning, Nature 549, 195–202 (2017).
  * (8) E. Farhi and H. Neven, Classification with quantum neural networks on near term processors, ArXiv:1802.06002 (2018).
  * (9) A. Peruzzo, M. Jarrod, P. Shadbolt, et al., A variational eigenvalue solver on a photonic quantum processor, Nature Communications 5, 4213 (2014).
  * (10) A. Kandala, A. Mezzacapo, K. Temme, et al., Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets, Nature 549, 242–246 (2017).
  * (11) E. Farhi, J. Goldstone and S.Gutmann, A Quantum Approximate Optimization Algorithm, ArXiv: 1411.4028 (2014).
  * (12) N. Moll, P. Barkoutsos, L. S. Bishop, et al., Quantum optimization using variational algorithms on near-term quantum devices, Quantum Science and Technology 3, 030503 (2018).
  * (13) M. P. Harrigan, K. J. Sung, M. Neeley, et al., Quantum approximate optimization of non-planar graph problems on a planar superconducting processor,  Nature Physics 17, 332–336 (2021).
  * (14) Z. Jiang, E. G. Rieffel and Z. Wang, Near-optimal quantum circuit for Grover’s unstructured search using a transverse field, Physical Review A 95, 062317 (2017).
  * (15) Z. Wang, S. Hadfield, Z. Jiang, et al., Quantum approximate optimization algorithm for MaxCut: A fermionic view, Physical Review A 97, 022304 (2018).
  * (16) F. G.S.L. Brandao, M. Broughton, E. Farhi, et al., For Fixed Control Parameters the Quantum Approximate Optimization Algorithm’s Objective Function Value Concentrates for Typical Instances, ArXiv: 1812.04170 (2018).
  * (17) J. Basso, E. Farhi, K. Marwaha, et al., The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model, In Proceedings of the 17th Conference on the Theory of Quantum Computation, Communication and Cryptography, 7:1–7:21 (2022).
  * (18) E. Farhi, J. Goldstone, S. Gutmann, et al., The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size, Quantum 6, 759 (2022).
  * (19) E. Farhi and A. W. Harrow, Quantum Supremacy through the Quantum Approximate Optimization Algorithm, ArXiv: 1602.07674 (2019).
  * (20) B. Barak and K. Marwaha, Classical algorithms and quantum limitations for maximum cut on high-girth graphs, In 13th Innovations in Theoretical Computer Science Conference, 14:1–14:21 (2022).
  * (21) M. Streif, S. Yarkoni, A. Skolik, et al., Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm, Physical Review A 104, 012403 (2018).
  * (22) Z. Wang, N. C. Rubin, J. M. Dominy, et al., XY mixers: Analytical and numerical results for the quantum alternating operator ansatz, Physical Review A 101, 012320 (2020).
  * (23) B. Bakó, A. Glos, Ö. Salehi and Z. Zimborás, Near-optimal circuit design for variational quantum optimization, ArXiv: 2209.03386 (2022).
  * (24) Y. Ruan, Z. Yuan, X. Xue, et al., Quantum approximate optimization for combinatorial problems with constraints, Information Sciences 619, 98-125 (2023).
  * (25) E. Farhi, J. Goldstone, S. Gutmann, et al., Quantum Computation by Adiabatic Evolution, ArXiv: 0001106 (2000).
  * (26) E. Farhi, J. Goldstone, S. Gutmann, et al., A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem, Science 292, 472–475 (2001).
  * (27) E. Farhi, D. Gamarnik and S. Gutmann, The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case, ArXiv: 2004.09002 (2020).
  * (28) G. E. Crooks, Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem, ArXiv: 1811.08419 (2018).
  * (29) G. Verdon, M. Broughton, J. R. McClean, et al., Learning to learn with quantum neural networks via classical neural networks, ArXiv: 1907.05415 (2019).
  * (30) M. Streif and M. Leib, Training the quantum approximate optimization algorithm without access to a quantum processing unit, Quantum Science and Technology 5, 034008 (2020).
  * (31) N. Jain, B. Coyle, E. Kashefi, et al., Graph neural network initialisation of quantum approximate optimisation, Quantum 6, 861 (2022).
  * (32) C. Moussa, H. Wang, T. Bac̈k and V. Dunjko, Unsupervised strategies for identifying optimal parameters in Quantum Approximate Optimization Algorithm, EPJ Quantum Technology 9, 11 (2022).
  * (33) L. Zhou, S. Wang, S. Choi, et al., Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices, Physical Review X 10, 021067 (2020).
  * (34) S. Boulebnane and A. Montanaro, Predicting parameters for the Quantum Approximate Optimization Algorithm for MAX-CUT from the infinite-size limit, ArXiv: 2110.10685 (2021).
  * (35) J. Wurtz and D. Lykov, Fixed-angle conjectures for the quantum approximate optimization algorithm on regular MaxCut graphs,  Physical Review A 104, 052419 (2021).
  * (36) D. J. Egger, J. Mareček and S. Woerner, Warm-starting quantum optimization, Quantum 5, 479 (2021).
  * (37) S. H. Sack and M. Serbyn, Quantum annealing initialization of the quantum approximate optimization algorithm, Quantum 5, 491 (2021).
  * (38) R. Tate, M. Farhadi, C. Herold, et al., Bridging Classical and Quantum with SDP initialized warm-starts for QAOA, ACM Transactions on Quantum Computing 4, 2 (2023).
  * (39) D. Achlioptas and C. Moore, Random $k$-SAT: Two Moments Suffice to Cross a Sharp Threshold, SIAM Journal on Computing 36, 740–762 (2006).
  * (40) R. Menchon-Enrich, A. Benseny, V. Ahufinger, et al., Spatial adiabatic passage: a review of recent progress, Reports on Progress in Physics 79, 074401 (2016).
  * (41) N. V. Vitanov, A. A. Rangelov, B. W. Shore, et al., Stimulated Raman adiabatic passage in physics, chemistry, and beyond, Review of Modern Physics 89, 015006 (2017).
  * (42) T. Albash and D. A. Lidar, Adiabatic quantum computation, Review of Modern Physics 90, 015002 (2018).
  * (43) B. Korte and J. Vygen, Combinatorial optimization: Theory and Algorithms, Springer Vol. 2 (2012).
  * (44) J. Welch, D. Greenbaum, S. Mostame, et al., Efficient quantum circuits for diagonal unitaries without ancillas, New Journal of Physics 16, 033040 (2014).
  * (45) A. Lucas, Ising formulations of many NP problems, Frontiers in Physics 2, 5 (2014).
  * (46) A. Barenco, C. H. Bennett, R. Cleve, et al., Elementary gates for quantum computation, Physical Review A 52, 3457 (1995).
  * (47) M. Saeedi and M. Pedram, Linear-depth quantum circuits for n-qubit Toffoli gates with no ancilla, Physical Review A 87, 062318 (2013).
  * (48) L. M. Kirousis, E. Kranakis, D. Krizanc, et al., Approximating the Unsatisfiability Threshold of Random Formulas, Random Structures & Algorithms 12, 253–269 (1998).
  * (49) A. Coja-Oghlan, K. Panagiotou, The asymptotic $k$-SAT threshold, Advances in Mathematics 288, 985–1068 (2016).