\textbf{Model Definition.} From the ground up, it needs to be well understood within which environment we are attempting to construct an asset allocation problem. For instance, we obviously cannot comprehend all the markets with interactions between millions of traders with each a different investment style, behavior, risk limits or trading frequency. But rather than accepting the entire universe of possibly feasible portfolios $𝒮$, a preliminary \emph{steering of the downstream complexity} for all other levels can help build up and realistically frame the use case. The field of investing is found with very different business domains, expectations and requirements that yield various degrees of complexity to start with. For example, a wealth manager for retail, affluent or high-net-worth individuals may have different requirements for composing or rebalancing investment portfolios than say, a large asset manager. While this seems rather obvious, it is key to formulate the model purpose, and thus, its expected performance. In particular, an informed pre-selection of diversified asset classes, industry exposures, risk profiles or expected dynamics for a given investment time horizon helps build a more robust starting point, $t_0$, for the optimization problem.

\textbf{Level 1.} At this stage we begin with the simplest problem formulation based on Harry Markowitz's introduction of modern portfolio theory in $1952$~\cite{Markowitz1952}, by formalizing portfolio diversification and optimal return-risk trade-offs with a mean-variance framework. It assumes a risk-averse myopic investor in a frictionless, one-period financial market with exact knowledge of parameters capturing asset price dynamics. The aim is to find an optimal portfolio $x = (x_1,...,x_N) ∈R^N$ from permissible portfolios $𝒮$ with fractions $x_i$ of a fixed budget to be fully invested into $N$ pre-selected, non-redundant assets at time $t_0$, based on estimates of expected returns $μ∈^N$ and their positive semi-definite covariance matrix $Σ∈^N ×N$ at the end of one investment period $t_1$. This can be formulated in three equivalent variants as \emph{quadratic programming problems} with linear constraints and without uncertainty in the parameters:
\begin{mini}|s|[0]
{x \in \R^N}{ \frac{1}{2} x^\top \Sigma x }{}{}\label{eq:finance_level1}
\addConstraint{}{\mu^\top x \geq r_{\text{min}}}
\addConstraint{}{\mathbbm{1}^\top x = 1}
\addConstraint{}{x \in \mathcal{S}},
\end{mini}
where the convex quadratic objective minimizes the portfolio risk $x^T Σx$ with an expected minimal portfolio return $r_min$. Instead, one can also maximize the expected return $μ^T x$ while bounding the risk $x^T Σx ≤γ^2$ as a quadratic constraint, which can be transformed into conic form~\cite{BenTalNemirovski2001}. Another alternative is to maximize a concave quadratic utility function $μ^T x - λ/2 x^T Σx$ with the risk-aversion factor $λ$ for steering the return-risk trade-off and variable focus on tail risk. However, all of these formulations are relatively trivial to solve, especially in the continuous setting, where a closed-form solution may be derived using Lagrangian multipliers~\cite{Heston1972} considering equality constraints~\cite{Gould2001} and with Karush-Kuhn-Tucker conditions considering also inequality constraints~\cite{Karush1939}. Notably, realistic market conditions are not captured by this model formulation. Nevertheless, this simple model offers excellent benchmarking opportunities to evaluate advances in quantum technology. In fact, the model complexity can also be increased in a controlled manner by adding additional constraints that might match a pre-defined investment strategy and, as the term $x ∈𝒮$ is meant to reflect, to further constrain the universe of portfolio configurations and test with an increasing number of additional linear constraints that match a pre-defined investment strategy. In practice, for a sufficiently large number of constraints one often has to rely on numerical approaches. As discussed in Sec.~\ref{sec:applications_finance_refs}, so far, most quantum approaches to this use case employ QUBO formulations with binary or integer encodings, which result in an \textbf{NPO}-hard combinatorial problem and constraints that are converted into penalty terms~\cite{Glover2019} of the objective function. Since these penalty terms only facilitate approximate encoding of the constraints, additional substantial post-processing would be required to achieve reliable results.

\textbf{Level 2.} A severe limitation of Level~1 is the ignorance of uncertainty in the inputs and instability of the optimization~\cite{Michaud2015}. Thus, it is of limited practical value to derive actual investment decisions. In fact, the optimization is highly sensitive to \emph{small changes} in the estimated expected returns $μ$ and covariance matrix $Σ$, leading to \emph{large differences} in the resulting optimal portfolio $x$. At this stage, the problem formulation is extended to take the stochastic nature of underlying observables into account. The root challenge comes from the portfolio-specific operating regime of the observation ratio $q = N/T$ given the prior number of empirical (sample) realizations $T$ for the $N$ considered assets at $t_0$. In the large limit with $q →0$, the sample estimators $μ$ and $Σ$ would converge to the \emph{true} realized (population) $μ_true$ and $Σ_true$, respectively. But in reality most asset allocation problems suffer from a lack of data (except maybe in high-frequency trading) with $q > 0$. For example, a realistic scenario for stocks could be $N = 600$ with $T = 2500$ of about 10~years of daily returns and, thus, $q = 0.24$. In case of a few thousand stocks, the issue of stock lifetime and structural evolution of markets over time becomes relevant, shifting the problem into the large dimensional limit regime with $q ∼1$ and fast diverging estimators with $q > 1$. If one would aim to increase the $T$ statistics with intra-day observations, one may not capture the dynamics for lower frequency trading strategies anymore and possibly introduce biases in the resulting optimal $x$. This makes the problem very complex, even for a small number of assets, and usually forces the industry to simplify $𝒮$ at the level of model definition.
In the following, we are going to present several approaches to address this challenge, ordered by increasing levels of complexity: first we de-bias and reduce the estimation error of $μ$ and $Σ$ prior to the optimization, then adding regularizing techniques to the optimization itself, before combing both.
Among various methods, the Black-Litterman model~\cite{BlackLitterman1992} could be leveraged to create an expected return prediction by combining actual market returns with independent expert beliefs about their future, taking into account, for instance, recent news, economic forecasts, analyst ratings, or financial statements~\cite{AvramovZhou2010, CorPeTue2018}.
Alternatively, a robust optimization problem can be formulated to achieve a stabilizing effect on $μ$ during the optimization itself. For this purpose, we define the ellipsoidal uncertainty set $𝒰_μ= { μ | (μ- μ_0)^⊤Q_μ^-1 (μ- μ_0) ≤κ^2 }$, where $Q_μ$ is the covariance matrix of estimation errors in $μ$, and $κ$ is the uncertainty aversion defining the width of the uncertainty. This induces a new optimization problem by replacing $μ$ with:
\begin{eqnarray}
\tilde\mu(x) &\coloneqq& \argmin_{\mu \in \mathcal{U}_\mu} \mu_0^\top x - \kappa \sqrt{ x^\top Q x }.
\end{eqnarray}
Even if the resulting improved estimate of $μ$, denoted by $μ̃$, still substantially deviates from $μ_true$, finding the minimal out-of-sample risk portfolio for it may still be valuable in practice.
The sample covariance matrix $Σ$ for $q ∈(0,1]$ can suffer from small eigenvalues near zero, leading to a potential underestimation of the realized (out-of-sample) risk exposure at $t_1$. To address this issue, Random Matrix Theory~\cite{Mehta2004, Wigner1955, NeumannGoldstine1947} provides efficient tools to de-bias the eigenvalues of $Σ$ such that the resulting $Σ$ is closer to $Σ_true$~\cite{Ledoit2011, RIE2016, BenaychGeorges2021, BunBouchaudPotters2017, LedoitWolf2017}.
A factor modeling method to represent the portfolio returns with a small number $M$ of common factors~\cite{ChamberlainRothschild1983} can additionally help to circumvent the curse of dimensionality if $M ≪N, T$.
Furthermore, one may want to further regularize $Σ$ by adding $L_1$- or $L_2$-norm constraints to the optimization.
Arguably one of the most important ones is the consideration of a transaction cost function $𝒞(x |x_0)$ that estimates the cost for rebalancing the portfolio $x_0$ at $t_0$ towards the optimal portfolio $x$ at $t_1$, taking for instance broker fees and implementation shortfall into account. This results in the following problem formulation:
\begin{maxi}|s|[0]
{x \in \R^N}{ \tilde{\mu}^\top x - \mathcal{C}(x \mid x_0) - \frac{\lambda}{2} x^\top \widetilde{\Sigma} x }{}{}\label{eq:finance_level2_trx}
\addConstraint{}{\mathbbm{1}^\top x + \mathcal{C}(x \mid x_0) = 1}
\addConstraint{}{x \in \mathcal{S}},
\end{maxi}
where $𝒞$ determines the complexity of the problem and depends on how realistic transaction costs should be represented.
For example, a piecewise linear non-convex function capturing transaction volume and fixed costs for buying and selling an asset can be formulated, or
a more realistic variant with stronger penalization on turnover considers costs proportional to the $L_1$-norm of rebalancing with $𝒞(x |x_0) = β x - x_0 _1$, where $β> 0$ denotes a cost parameter.
While formulations of this problem that are based on $𝒞$ employ strong regularization on $Σ$, depending on the respective $q$ regime set out in the model definition, the resulting $x$ may still be biased and sensitive to estimation errors.
This can be further addressed with two methods. The first one uses a non-parametric bootstrap resampling approach~\cite{MichaudR2008}
and the second one uses a nested clustering approach~\cite{Prado2019} that partitions $Σ$ by forming clusters of highly-correlated assets.
The latter approach can help to prevent error propagation of intra-cluster noise across clusters. Due to a reduction of dimensionality and better control of noise isolation with smaller sample sizes, the exploration of near-term variational quantum algorithms with realistic stock portfolio sizes may become possible in this setting.

\textbf{Level 3.} Until this point we have restricted ourselves to a static one-period market environment. At this level, we introduce the next complexity layer by considering market dynamics and temporal dependency. For example, similar to volatility, correlations fluctuate, evolve with time and jump or even flip signs~\cite{REIGNERON20113026, CCorr2021}. However, our understanding of correlation dynamics is nowhere near our understanding of volatility, which creates an interesting domain to explore with quantum computing. Similarly, this is the case for multi-period optimization, which could help capture inter-temporal effects, such as accounting for time-varying constraints, return forecasts, cost-favorable positions for trading in following periods, or foreseeable events impacting risk, trading volume or liquidity. Although there is a lot of research interest, given the computational hardness of the multi-period domain, most practitioners, as well as classical enterprise solver suites, cannot effectively tackle these use cases~\cite{Kolm2014}. Essentially, the $h$-period optimization problem can be \emph{generally} formulated as follows:
\begin{maxi}|s|[0]
{x_{t + 1},\ldots, x_{t + h}}{ \mathbbm{E} \left[ \mathcal{X}(x_{t+1},\ldots,x_{t+h}) \mid \mathcal{F}_t \right] }{}{}\label{eq:finance_level3_general}
\addConstraint{}{x \in \Theta},
\end{maxi}
where $𝒳$ is the inter-temporal utility function given the filtration $ℱ$ associated to the probability space at the $t^th$ period with a set $Θ$ of constraints. If we can assume that $𝒳$ is separable in time, then the objective function can be written as $min_x { a(x) + b(x) }$ with a static (forward-looking) part $a(x) = ∑_τa_τ(x_τ)$ and a dynamic (coupling) part $b(x) = ∑_τb_τ(x_τ-1, x_τ)$ with $τ= t+1,…,t+h$, and their respective separation of constraints becomes $x ∈Θ^(a) ∩Θ^(b)$. Here, $a_τ$ represents a one-period optimization program such as the mean-variance terms discussed in Levels~1 and 2, while $b_τ$ serves as an intra-period regularization penalty such as the $𝒞(x_τ| x_τ- 1)$ transaction cost functions discussed in Level~2.
Problem formulations of this form and other multi-objective settings are gaining substantial interest in the financial industry, and will play a key role in the coming years. Thus, it is interesting to investigate new approaches for this use case with quantum technology and inspire the development of new quantum algorithms.

This concludes our short deep-dive illustration with increasing levels of complexity and selected examples within the mean-variance framework. But notably, this can be extended as our exploration of quantum solutions evolve. In particular, the development of new quantum optimization solutions should transition from current Level~1 investigations to Level~2 and 3 challenges, and with that drive research towards handling optimization problems under uncertainty in order to aim for valuable contributions to the financial industry.

\subsubsection{Outlook}\label{sec:applications_finance_outlook}
% Author(s): Manuel
The financial industry offers a broad spectrum of hard optimization problems and demands the exploration of new solution approaches to tackle many of today's trade-offs. This short condensed review provides a satellite view of open optimization challenges relevant to the financial industry. A selection of use cases are discussed along with their classical challenges and how optimization problems can be constructed with increasing complexity levels. The main challenge remains to effectively combine both the modeling and optimization of problems to achieve practically relevant results for industry use cases. However, there are many more directions to investigate, such as handling skewed, non-Gaussian heavy tailed probability distributions, Bayesian approaches and industry sector or subgroup specific priors, or non-Markovian decision processes. All of these aim to inspire and guide the exploration of research, development and benchmarking of potential industry-specific quantum optimization applications.

\subsection{Sustainable Energy Transition}
\label{sec:applications_sustainability}

Sustainability describes the goal of a responsible use of resources to guarantee a long-term existence of humanity on earth in a healthy environment. While sustainability has multiple dimensions, a common focus is put on environmental problems, such as countering climate change. For this paper, we focus on a subsection of sustainability, that of sustainable transition of the energy sector. It is a particularly relevant area as it is rich with optimization problems with societal benefit.
We discuss multiple problems in this domain that can serve as illustrative test cases with different challenges to benchmark optimization algorithms. The use cases described here serve as an interesting playground to generate examples derived from real-world data to study corresponding quantum optimization algorithms. While they might not necessarily be candidates for a practical quantum advantage in near future, they can help to improve our understanding about problem characteristics where quantum optimization may have some potential over classical algorithms and where not.

\subsubsection{Power Grid Overview}
\label{sec:future_energy_systems}

For decades, society has relied on carbon-intense and centralized energy sources \cite{Smi19}. Few powerful generation sites were responsible for meeting energy demands, and adjusting energy generation was relatively simple with fossil fuels. However, the energy sector is changing rapidly. Technological advancements and climate-change awareness have led to an increase in renewable energy sources. Power grid digitization  \cite{en13020494, BVS+18} has resulted in greater connectivity and interactions between customers, producers, utilities, and grid operators. This has revolutionized how we manage and optimize energy resources by enabling real-time monitoring, data-driven decision-making, and enhanced control over energy consumption and distribution.

However, the transition to renewable energy sources and the digitization of the power grid are not without challenges.
Renewable energy sources such as solar and wind are intermittent and probabilistic in nature, and, they require the coordination of a large number of assets; for example, to match energy supply with demand. Energy storage solutions are essential for managing the variability associated with renewable energy production, but they present their own set of challenges, including cost and scalability. Additionally, power grid digitization introduces multiple challenges including cybersecurity and data privacy. Adapting grid systems to this new paradigm will necessitate substantial investment and innovative solutions, potentially surpassing the capabilities of classical computer systems.

In this section, we discuss three types of optimization problems in power grid. We start with a brief overview of the area in Sec.~\ref{sec:future_energy_systems} and related quantum optimization work, in Sec.~\ref{sec:sustainability_related_work}. In Sec.~\ref{sec:e_mobility}, we introduce \emph{electric mobility} (e-Mobility) and present three families of e-Mobility use cases and how they connect to the problem classes and algorithms in Sec.~\ref{sec:problem_classes}.
Finally, Sec.~\ref{sec:sustainability_outlook} concludes and outlines potential research directions.

\subsubsection{Related Work} \label{sec:sustainability_related_work}
Research in quantum optimization for power grids is currently in its early stages, with a predominant focus on the unit commitment problem (UCP) \cite{1295033,van2018large}.
Koretsky \emph{et al.}~\cite{koretsky21} consider the UCP for power networks by combining quantum and classical methods: QAOA handles the binary on-off variables for each unit and a classical optimizer handles the continuous variables for how much power each unit should provide. Takahashi \emph{et al.}~\cite{takahashi23} writes the UCP as a QUBO problem for network switches equal to 0 or 1 if open or closed, subject to connection, voltage, and maximum current constraints.
They model the constraints as penalties in the objective function and solve the problem with annealing. Similarly, Halffmann \emph{et al.}~\cite{halffmann22} and Braun \emph{et al.}~\cite{braun23b} formulate the UCP as a QUBO with penalty terms. Mahroo and Kargarian \cite{mahroo22} decompose the UCP into a sequence of quadratic continuous and binary (unconstrained) subproblems, similarly to ADMM~\cite{gambella2020mixed, gambella2020multiblock}, cf.~Sec.~\ref{sec:milp-miqp}.
All of the works mentioned above have in common that they focus on small, illustrative problems and that they explore simple mathematical models (mostly QUBOs) that do not capture the complexity of real-world use cases. Although these works may not have a direct practical impact yet, they could help to pave the way for advancing the corresponding theory, problem formulations, algorithms, and to understand practical requirements on optimization solutions to have practical impact.

\subsubsection{Leveraging the Flexibility of e-Mobility}\label{sec:e_mobility}
As outlined in Sec.~\ref{sec:future_energy_systems}, the world is progressively adopting carbon-neutral energy generation methods \cite{EU-report23-05,france-nuclear}. While renewable sources like wind and solar power play a vital role, they often produce energy when demand is low. To address this disparity, it is crucial to invest in energy storage solutions, such as batteries, and the optimized coordination thereof.

Electric vehicles (EVs) are an energy storage solution of increasing importance. In 2022, the number of EVs on the road exceeded 26 million \cite[pp.\ 14]{ev-outlook-2023}, and the global fleet of EVs is expected to grow to about 240 million in 2030 --- 10\% of the road vehicle fleet \cite[pp.\ 109]{ev-outlook-2023}.
To put this opportunity in perspective, EV batteries can typically store  20 to 100 kWh and can have an output power of 10 kWh when connected to a Type 2 charger. Thus, 400 EVs, in principle, can deliver 4 MWh of energy to the grid, which is approximately the same output power of an energy storage substation \cite{substation-3.8MWh}.

To leverage e-Mobility's potential to stabilize the energy network and balance supply and demand, it is crucial to address three challenges: The first challenge is to increase the EVs' penetration, for example, by facilitating access to charging infrastructure \cite{en12142739}. This is particularly important in densely populated areas where overnight charging may only be available for some EVs. The second challenge is to effectively control how EVs store energy \cite{LUND20083578}. Unlike conventional energy storage systems, EVs consume energy from the grid, and their batteries must be sufficiently charged by strict deadlines. The final challenge is to integrate EVs into the power grid infrastructure \cite{LUND20083578}, enabling energy retailers to store energy in EVs that they can then inject back into the grid, i.e., an EV acts as a ``virtual power plant.''

Next, we discuss three optimization-related e-Mobility use cases, each addressing one of the challenges mentioned earlier.
We start with a ``core'' mathematical problem and then extend this to a family of problems with increasing practical relevance, linking it to the problem classes discussed in Sec.~\ref{sec:problem_classes}.

\textbf{Use case 1: Scheduling EVs in a parking site.}
This use case consists of allocating EVs to parking spaces in a parking site \cite{SZL+21, SYH+22}. In short, consider a parking site that has two types of parking spaces: regular parking spaces and parking spaces where EVs can be plugged in. EVs arrive at the parking site indicating the kWh they want to replenish at each time, e.g., in each hour. With that information, the parking site administrator decides where to allocate the EVs to maximize the charging volumes and thereby profit. To simplify the problem formulation even further, let us assume that the EVs arrival and departure times are known in advance. Figure \ref{fig:EV_scheduling} shows the problem schematically, where the $y$-axis in the figure represents the EVs. The goal is to select EVs such that the number of EVs at a given time does not exceed the number of chargers and the input power of the site.

% Mathematical formulation
\begin{figure}
\includegraphics[width=0.85\columnwidth]{figs/ev_offline_b.eps}
\caption{Illustrating a possible instance for the problem of scheduling the charging of EVs in a parking site (use case 1).}
\label{fig:EV_scheduling}
\end{figure}

We can formalize the problem as follows. Let $N$ be the number of EVs and $K$ the total number of intervals (e.g., 24 intervals, where each interval corresponds to an hour). Next, let $u_n ∈{0,1}^K$ be a vector that indicates the (known) presence of EV $n ∈{1,…,N}$ at time $k ∈{0,…,K-1}$, and $v_n ∈^K$ be the value that the parking site will obtain by admitting EV $n$ (e.g., dollars). Thus, the inner product $v_n^T u_n$ denotes the total value for the parking site if admitting EV $n$.
Also, let $d_n ∈^K$, where the $k$-th entry indicates the energy requested by EV $n$ at time $k$. The parking site has a maximum input power of $E$ kWh and has a maximum capacity of $M$ EVs.
Then, the optimization problem is the following:
\begin{maxi}|s|[0]
{x\in \{0, 1\}^N}{ \sum_{n=1}^N x_n ( v_n^T  u_n)\hspace{1.75cm}}
{}{} \label{eq:mult-dimensional-knapsack}
\addConstraint{\sum_{n=1}^N x_n u_{n,k} \le M, \, \forall k}
\addConstraint{ \sum_{n=1}^N x_n d_{n,k} u_{n,k} \le E, \, \forall k,}
\end{maxi}
where $x_n$ denotes the decision variable of whether to accept EV $n$ to a parking space where it can be plugged in or not.
That is, Eq.~\eqref{eq:mult-dimensional-knapsack} is a binary optimization with $2K$ knapsack constraints; $K$ knapsacks for the parking spaces, and $K$ knapsacks for the energy available in the parking site.

Some instances of the multi-dimensional knapsack problems can be challenging to solve, even when the problem instances are relatively small, cf.~Sec.~\ref{sec:benchmarking_problems}.
Thus, studying problems of the form in Eq.~\eqref{eq:mult-dimensional-knapsack} can be of interest for near-term quantum optimization algorithms with a potential practical application. Of course, we need to benchmark specific practically relevant problem instances to assess whether they are difficult classically. If the instances prove difficult, we can proceed to explore whether there is an opportunity for a practically relevant quantum advantage. Since reality and real world scenarios are often more delicate, there will likely be additional constraints and cost function adjustments to Eq.~\eqref{eq:mult-dimensional-knapsack} thereby increasing its general difficulty for classical solvers.
Some interesting problem extensions for Eq.~\eqref{eq:mult-dimensional-knapsack} towards practically relevant applications are the following:
\begin{enumerate}
\item The power available in a parking site may vary over time; for example, when the parking site shares its connection to the grid with another infrastructure or a local renewable energy source is considered, such as a solar power plant.
\item The decision of admitting/rejecting EVs is carried out via a pricing policy that affects the willingness of the drivers to use the parking site.
\item Increase the EV charging flexibility. EVs can have a desired state of charge at one or multiple points in time (e.g., at least 60 kWh by 6 am).
\item The EV arrivals and departure times may not be known in advance, as described at the beginning of the section. Additionally, the forecast of renewable energies includes uncertainties if considered in (1).
\end{enumerate}

The original problem in Eq.~\eqref{eq:mult-dimensional-knapsack} can be modeled as a QUBO. The original objective function is linear, i.e., the corresponding cost matrix will be a diagonal matrix, cf.~Sec.~\ref{sec:unconstrained_discrete_optimization}, and the constraints can, for instance, be encoded as penalties into the objective, cf.~Sec.~\ref{sec:unconstrained_discrete_optimization}, which, however, will immediately imply a dense cost matrix.
The extensions (1)-(4) affect the difficulty of Eq.~\eqref{eq:mult-dimensional-knapsack} in different ways:
(1) imposes additional constraints that may result in an increasing problems size, which may result in more qubits or having to encode more binary variables per qubit.
(2) will imply adding continuous variables and results in a MIP.
(3) adds flexibility to how EVs charge and discharge, which may further increase the number of decision variables.
Finally, (4) introduces uncertainty to the optimization problem, potentially necessitating a shift in the formulation from offline optimization to online or stochastic optimization such as MDP, cf.~Sec.~\ref{sec:optimal_control}.

\textbf{Use case 2: Charging and discharging EVs.}
Consider the scenario where a fleet of EVs are plugged in from 6pm to 6am the next day, e.g., delivery vehicles. The fleet owner allows the energy supplier to use the EVs as energy storage subject to the constraint that the EVs are fully charged at departure time (i.e., by 6am the next day). The goal of the energy supplier is to provide electricity to the end customers at minimum cost. In particular, the energy supplier would like to store energy in the EVs when this is cheap, and use the energy in the EVs to power the grid when energy production is low or expensive to buy from the energy markets. The problem is challenging because the energy demand and energy prices may vary over time.

We can formulate the problem above as a \emph{deterministic} discrete-time control problem, cf.~Sec.~\ref{sec:optimal_control}. In short, we divide time in slots $k ∈{0,…,K-1}$ of equal duration, where $K$ defines the total considered time horizon. The duration of a slot can be, for example, 1 hour, and the horizon 12 hours.
Next, let $N$ be the number of EVs and $x_k ∈^N_≥0$ represent the state of charge of the EVs at time $k$. In each time slot $k$, the controller selects an action from the action set $A(x_k) ⊂^N$ containing the possible input/output powers of each EV, e.g., $±10$ kWh. The action set at time $k$ depends on the state $x_k$ since, for example, it is not possible to discharge an EV if its battery is empty. The choice of action $a_k ∈A(x_k)$ affects the EVs' state of charge in the next time slot $k+1$. In particular, $x_k+1 = F(x_k, a_k)$ where $F$ is a function that deterministically maps a state $x_k$ given an action $a_k$ to the next state $x_k+1$.
Next, let  $T_k(x_k, a_k)$ be the cost obtained by selecting action $a_k$ in state $x_k$ at time $k$.
The resulting optimization problem is given as following:
\begin{mini}
{a_k \in A(x_k)}{\sum_{k=0}^{K-1} T_k(x_k,a_k)\hspace{0.5cm}}
{}{} \label{eq:EV_control}
\addConstraint{x_K = x'}
\addConstraint{x_{k+1} = F(x_k, a_k),}
\end{mini}
where $x_0 ∈^N_≥0$ denotes the EVs' initial state of charge and $x'$ the state that all EVs are fully charged.
Thus, the goal is to select actions $a_k ∈A(x_k)$ to minimize the sum of the costs given that $x_k+1 = F(x_k, a_k)$ and the final state, $x_K$, is equal to $x'$.
We have modeled the problem as a discrete optimal control problem, cf.~Sec.~\ref{sec:optimal_control}, but other formulations are possible as well. For instance, we can formulate it as a MIP with $K+1$ constraints for the dynamics, plus the constraints for enforcing feasibility of actions.
However, unlike the previous use case, Eq.~\eqref{eq:EV_control} is a less promising problem candidate for demonstrating industrial quantum advantage in the short term.
The problem formulation can be mapped to a UCP (via DP) \cite{1295033}, which commercial solvers can solve efficiently with hundreds of units \cite[Sec.~6]{doi:10.1287/ijoc.2019.0944}. Nonetheless, we can add features to Eq.~\eqref{eq:EV_control} to make it more difficult to solve classically, and at the same time, closer to real-world scenarios:
\begin{enumerate}
\item Energy constraints that affect how an EV or group of EVs can charge or discharge at a given time.
\item EVs arriving and departing at different (stochastic) times instead of being parked overnight.
\item Stochastic cost function that captures, for example, the uncertainty in the electricity demand.
\end{enumerate}

We can approach the problem in Eq.~\eqref{eq:EV_control}, for instance, with DP.
As mentioned in Sec.~\ref{sec:dynamic_programming}, DP requires searching over all possible states and actions, which is often exponential in size. One approach to speedup DP is using Grover’s search algorithm as a subroutine. Similar to \cite{ABIKPV19} for the TSP, the quantum algorithm could first use DP to compute multiple paths from state $x_0$ to $x_K=s'$ and then use Grover's search to find a combination of those paths that yields lower cost. Nonetheless, such an approach is unlikely to yield practical speedups in the short term since Grover's search requires FTQC and a quadratic speedup might not be sufficient for the considered problems and scales.
An alternative is to model the problem as a MIP, and try algorithms discussed in Sec.~\ref{sec:milp-miqp}.

The extensions (1)-(3) add different complications to Eq.~\eqref{eq:EV_control}:
(1-2) add constraints to enforce certain target states at given times or feasible actions, e.g., minimum constant charge or discharge times, which affects both, DP and MIP formulations as shown for uni-directional charging by Federer \emph{et al.}~\cite{Federer2022}.
In case of stochastic arrival/departure times, (2) will require more complex approaches, e.g. MDP, to handle the uncertainty.
Similar to the stochastic case in (2), (3) will require approaches like MDP to compute a policy that minimizes the costs under uncertainty.
MDPs quickly become very difficult to solve due to the curse of dimensionality, cf.~Sec.~\ref{sec:optimal_control}.
Thus, this might be an interesting domain for first small test cases to analyze the potential of corresponding quantum approaches.
Since the result of MDP is a policy, the optimization and inference are split, which may allow to relax requirements on the time-to-solution.

\textbf{Use case 3: Energy retailing with storage.}
Consider an energy retailer that delivers energy to end customers. The energy supplier buys energy from energy producers in advance, e.g., on the day-ahead energy trading market, in one-hour time intervals, where the electricity price depends on several factors such as energy demand, renewable energy generation, etc. Additionally, the energy supplier has access to an energy storage system, e.g., a fleet of EVs that act as a \emph{virtual power plant}, that can accumulate energy when this is cheap, to later use it when energy demand is high. The energy supplier's goal is to deliver energy to its customers at the lowest possible cost. Thus, it is incentivized to leverage the flexibility provided by its energy storage assets. The problem is challenging because the electricity demand and the energy available in storage are not exactly known in advance. Furthermore, if the energy demand is not met, the energy supplier has to buy energy from other retailers that often sell energy at a higher price.

We can formulate the problem mathematically as follows. Let $e_k ∈_≥0$ be the decision variable indicating the MWh the energy supplier buys in each hour $k ∈{0,1, …, K-1}$ in advance, usually with $K=24$, and $p^low_k ∈$ the price of the \emph{cheap} energy (which sometimes might even be negative!). Similarly, let $D_k$, $B_k$, $P_k^high$ be random variables that capture, respectively, the electricity demand at time $k$ in MWh, the energy available in storage at time $k$ in MWh, and the price of the \emph{expensive} energy at time $k$. The optimization problem is the following:
\begin{mini}
{e_k \ge 0}{\sum_{k=0}^{K-1}  \left(p^{\text{low}}_k e_k   +  \mathbf E \left[ P^{\text{high}}_k [D_k - e_k - B _k ]^+  \right]   \right)}
{}{} \label{eq:energy_sell}
\end{mini}
where $[·]^+:= max{0,·}$ and  the expectation is with respect to $D_k$, $B_k$, and $P_k^high$. That is, we have a stochastic unconstrained optimization where the objective function at time $k$ consists of two terms: the cost of buying cheap energy, and the expected cost of buying expensive energy. Note that $[D_k - e_k - B_k]^+$ captures the energy demand that cannot be met with the energy bought (i.e., $e_k$) and the energy in storage (i.e., $B_k$).

The optimization in Eq.~\eqref{eq:energy_sell} is convex since the objective function is piece-wise linear and convex.
Thus, if $D_k$, $B_k$, and $P_k^high$ are random variables \emph{independent} of the decision variables, we can efficiently solve the problem with conventional convex optimization tools, in fact, by solving $K$ separate problems --- one for every term in the sum in Eq.~\eqref{eq:energy_sell}. Hence, Eq.~\eqref{eq:energy_sell}, in its current form, is \emph{not} a promising problem candidate for demonstrating quantum advantage. Yet, we can make it more challenging and closer to real-world problems with the following three extensions:

\begin{enumerate}
\item The energy available in storage at time $k$ depends on the previous decisions taken; for example, on how EVs charge and discharge, as in the previous use case 2.
\item Convex or concave cost functions, i.e., the cost to buy energy might depend on the quantity ordered.
\item The energy supply has to meet the energy demand.
\end{enumerate}

The extensions add different layers of complexity. In particular, (1) \emph{couples} the random variables with the decision variables and ``links'' the $K$ time steps, i.e., terms in the objective function Eq.~\eqref{eq:energy_sell}.
This is similar to the system dynamics function in optimal control, cf.~Sec.~\ref{sec:optimal_control}.
This extension is important since assuming that the energy in storage (i.e., $B_k$) is independent of the decision variables does not allow us to capture, for example, that the energy retailer buys energy in advance to keep in storage for later use, i.e., the decisions in the past affect the events in the future.  We can recast Eq.~\eqref{eq:energy_sell} as an optimal control problem where the system dynamics is given by the algorithm in the second use case, i.e., the energy available by how EVs charge and discharge. That is, we are coupling this use case with the previous one, and, indirectly, inheriting the quantum challenges already discussed. In other words, we are adding the complications of use case 2 on top of use case 3.
(2) adds a constraint of the form $g(D_k - e_k - B_k) ≤0$, where $g$ is a function such as CVaR that measures risk. The problem falls within the realm of robust optimization, see Sec. \ref{sec:robust_optimization}, or chance constraints \cite{nemirovski_2007_chance_constraints}.
In case of (3), depending on the exact properties of cost functions, the problem may remain convex or not. In case of a non-convex problem, this can quickly become very challenging to be solved.

\subsubsection{Outlook}\label{sec:sustainability_outlook}
Quantum computing has the potential to significantly advance optimization problems related to the sustainable energy transition.
However, identifying the most promising applications is an ongoing challenge.
Here, we have introduced illustrative examples of optimization problems that may serve as test cases derived from real-world data.
Under certain assumptions on the problem data, some instances may prove to be classically challenging even with few variables.
We have shown how the problem classes introduced in Sec.~\ref{sec:problem_classes} relate to these families of use cases with increasing complexity and of increasing relevance to real-world applications.
The discussion underlines the need for additional research on quantum optimization algorithms to approach the complications required for practical impact. It further shows that it is crucial to benchmark the problem instances to identify which ones are truly difficult classically and where there is room for a potential quantum advantage.

\section{Conclusion \& Outlook}\label{sec:conclusion}

In this paper, we provided a comprehensive overview of the potential, challenges, and emerging research areas in quantum optimization. We observed that, while complexity theory is useful to guide towards provable performance guarantees, it may not always be useful for finding practical quantum advantage. This underscores the need to develop and analyze quantum (optimization) heuristics to better understand their effectiveness. We highlighted key problem classes in optimization, reviewed existing algorithms and suggested new research directions. Further, we discussed the challenges of executing and scaling these algorithms on noisy hardware and the importance of benchmarking for identifying quantum advantages. Lastly, we explored two illustrative application domains, emphasizing the need to expand our focus beyond problem classes like QUBO to truly impact these fields.

As quantum hardware evolves with more qubits, reduced errors, faster circuit execution, a new era is emerging, where progress in quantum algorithms comes from both, theoretical analysis and empirical methods. While there is the strong need to continue discovering new algorithms with provable performance guarantees,
we also have to increase the development of novel quantum algorithms, even if we do not have guarantees for those, and benchmark their performance on real quantum computers. If the algorithms prove successful, it would surely be possible to analyze their properties in detail.
The improving abilities to test ideas in practice unlocks unprecedented opportunities for the advancement of quantum optimization. Even if it will not immediately imply a practical quantum advantage, the intuition gained from running experiments on real hardware will allow us to quickly validate proposals.

% Responsible Quantum Optimization
In addition to technical advances in quantum optimization, there is also the question of responsible research and use of this new technology. There are a variety of causes, arising from different applications. Thus, further research should be done with the awareness that optimization use cases occur in a multitude of contexts --- from those with positive societal impact, to those with nefarious intent. We hope that open scientific discussions encourage advancement in quantum optimization and advocate responsible use of the insights presented in this work. While we showcase where benefits for optimization algorithms may lie, it is important not to overstate or misinterpret the results of this paper and its \textit{potential} applications. Hence the need to establish clear benchmarks, cf.~Sec.~\ref{sec:benchmarks}, to enable a reliable interpretation of the scientific insights by a broader audience. Moreover, where use case applications of quantum optimization algorithms are chosen and funded, we encourage the prioritization of those with positive social impact, for example, sustainable energy transition as discussed in Sec.~\ref{sec:applications_sustainability}.

In conclusion, quantum optimization holds vast potential for various applications, but significant challenges remain in demonstrating a practical quantum advantage. Once a tangible quantum advantage is demonstrated, we expect that quantum optimization would rapidly influence many domains given the widespread relevance of optimization. This paper has provided a blueprint to define and measure progress in quantum optimization, which unquestionably has exciting prospects.

\vspace{3mm}

% \noindent\textbf{Data Availability.}
% A collection of suitable benchmarking problems for quantum optimization can be found at
% \url{https://github.com/qiskit-community/quantum-algorithms-benchmarks}. \OUF{To be added in an updated version--once problems have been added}

\noindent\textbf{Acknowledgments.}
Andris Ambainis acknowledges the suppoer of the Latvian Quantum Initiative under European Union Recovery and Resilience Facility Project No.~2.3.1.1.i.0/1/22/I/CFLA/001 and the QuantERA II ERA-NET Cofund project QOPT.
Brandon Augustino and Swati Gupta acknowledge support from the US Defense Advanced Research Projects Agency (DARPA) Contract No.~HR001120C0046.
Stuart Hadfield was supported by NASA Academic Mission Services Contract No.~NNA16BD14C, and by DARPA under interagency agreement IAA 8839, Annex 114.
Steve Lenk was funded by Free State of Thuringia (Th\"uringer Aufbaubank) through project Quantum Hub Th\"uringen (2021 FGI 0047), by
Bundesministerium für Wirtschaft und Energie, Germany through the project “EnerQuant” (Project No.~03EI1025C), and  by the European Union under Horizon Europe Programme. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or European Climate, Infrastructure and Environment Executive Agency (CINEA). Neither the European Union nor the granting authority can be held responsible for them. Grant Agreement 101080086 - NeQST.
Jakub Marecek acknowledges the support of the Czech Science Foundation (23-07947S). Giacomo Nannicini acknowledges support by ONR (N000142312585).
Patrick Rebentrost acknowledges support by the National Research Foundation, Singapore.
The work of Jon Yard was supported in part by the NSERC Discovery under Grant No.~RGPIN-2018-04742, the NSERC project FoQaCiA under Grant No.~ALLRP-569582-21 and the Perimeter Institute for Theoretical Physics. Research at Perimeter Institute is supported by the Government of Canada through Innovation, Science and Economic Development Canada and by the Province of Ontario through the Ministry of Research, Innovation and Science.
Los Alamos unlimited release LA-UR-23-33327.

%merlin.mbs apsrev4-1.bst 2010-07-25 4.21a (PWD, AO, DPC) hacked
%Control: key (0)
%Control: author (0) dotless jnrlst
%Control: editor formatted (1) identically to author
%Control: production of article title (0) allowed
%Control: page (1) range
%Control: year (0) verbatim
%Control: production of eprint (0) enabled
\providecommand{\noopsort}[1]{}
\begin{thebibliography}{598}%
\makeatletter
\providecommand \@ifxundefined [1]{%
\@ifx{#1\undefined}
\providecommand \@ifnum [1]{%
\ifnum #1\expandafter \@firstoftwo
\else \expandafter \@secondoftwo
\fi
\providecommand \@ifx [1]{%
\ifx #1\expandafter \@firstoftwo
\else \expandafter \@secondoftwo
\fi
\providecommand \natexlab [1]{#1}%
\providecommand \enquote  [1]{``#1''}%
\providecommand \bibnamefont  [1]{#1}%
\providecommand \bibfnamefont [1]{#1}%
\providecommand \citenamefont [1]{#1}%
\providecommand \href@noop [0]{\@secondoftwo}%
\providecommand \href [0]{\begingroup \@sanitize@url \@href}%
\providecommand \@href[1]{\@@startlink{#1}\@@href}%
\providecommand \@@href[1]{\endgroup#1\@@endlink}%
\providecommand \@sanitize@url [0]{\catcode `\\12\catcode `\$12\catcode `\&12\catcode `\#12\catcode `\^12\catcode `\_12\catcode `\%12\relax}%
\providecommand \@@startlink[1]{}%
\providecommand \@@endlink[0]{}%
\providecommand \url  [0]{\begingroup\@sanitize@url \@url }%
\providecommand \@url [1]{\endgroup\@href {#1}{\urlprefix }}%
\providecommand \urlprefix  [0]{URL }%
\providecommand \Eprint [0]{\href }%
\providecommand \doibase [0]{http://dx.doi.org/}%
\providecommand \selectlanguage [0]{\@gobble}%
\providecommand \bibinfo  [0]{\@secondoftwo}%
\providecommand \bibfield  [0]{\@secondoftwo}%
\providecommand \translation [1]{[#1]}%
\providecommand \BibitemOpen [0]{}%
\providecommand \bibitemStop [0]{}%
\providecommand \bibitemNoStop [0]{.\EOS\space}%
\providecommand \EOS [0]{\spacefactor3000\relax}%
\providecommand \BibitemShut  [1]{\csname bibitem#1\endcsname}%
\let\auto@bib@innerbib\@empty
\bibitem [{\citenamefont {Grover}(1996)}]{grover}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Lov~K.}\ \bibnamefont {Grover}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {A fast quantum mechanical algorithm for database search},}\ }in\ \href {\doibase 10.1145/237814.237866} {\emph {\bibinfo {booktitle} {Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing}}},\ \bibinfo {series and number} {STOC '96}\ (\bibinfo  {publisher} {Association for Computing Machinery},\ \bibinfo {address} {New York, NY, USA},\ \bibinfo {year} {1996})\ p.\ \bibinfo {pages} {212–219}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Farhi}\ \emph {et~al.}(2000)\citenamefont {Farhi}, \citenamefont {Goldstone}, \citenamefont {Gutmann},\ and\ \citenamefont {Sipser}}]{farhi2000quantumAdiabatic}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Edward}\ \bibnamefont {Farhi}}, \bibinfo {author} {\bibfnamefont {Jeffrey}\ \bibnamefont {Goldstone}}, \bibinfo {author} {\bibfnamefont {Sam}\ \bibnamefont {Gutmann}}, \ and\ \bibinfo {author} {\bibfnamefont {Michael}\ \bibnamefont {Sipser}},\ }\href@noop {} {\enquote {\bibinfo {title} {Quantum computation by adiabatic evolution},}\ } (\bibinfo {year} {2000}),\ \Eprint {http://arxiv.org/abs/quant-ph/0001106} {arXiv:quant-ph/0001106} \BibitemShut {NoStop}%
\bibitem [{\citenamefont {Applegate}\ \emph {et~al.}(1998)\citenamefont {Applegate}, \citenamefont {Bixby}, \citenamefont {Chv\'atal},\ and\ \citenamefont {Cook}}]{applegate1998solution}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {David~L.}\ \bibnamefont {Applegate}}, \bibinfo {author} {\bibfnamefont {Robert~E.}\ \bibnamefont {Bixby}}, \bibinfo {author} {\bibfnamefont {Vašek}\ \bibnamefont {Chv\'atal}}, \ and\ \bibinfo {author} {\bibfnamefont {William~J.}\ \bibnamefont {Cook}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {On the solution of traveling salesman problems.}}\ }\href {http://eudml.org/doc/233207} {\bibfield  {journal} {\bibinfo  {journal} {Documenta Mathematica}\ ,\ \bibinfo {pages} {645--656}} (\bibinfo {year} {1998})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Applegate}\ \emph {et~al.}(1999)\citenamefont {Applegate}, \citenamefont {Bixby}, \citenamefont {Chv{\'a}tal},\ and\ \citenamefont {Cook}}]{applegate1999finding}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {David~L.}\ \bibnamefont {Applegate}}, \bibinfo {author} {\bibfnamefont {Robert~E.}\ \bibnamefont {Bixby}}, \bibinfo {author} {\bibfnamefont {Vasek}\ \bibnamefont {Chv{\'a}tal}}, \ and\ \bibinfo {author} {\bibfnamefont {William~J.}\ \bibnamefont {Cook}},\ }\href {https://www.math.uwaterloo.ca/tsp/methods/papers/lk_report.pdf} {\enquote {\bibinfo {title} {{Finding Tours in the TSP}},}\ } (\bibinfo {year} {1999})\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Cook}\ \emph {et~al.}(1997)\citenamefont {Cook}, \citenamefont {Cunningham}, \citenamefont {Pulleyblank},\ and\ \citenamefont {Schrijver}}]{cook1998combinatorial}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {William~J}\ \bibnamefont {Cook}}, \bibinfo {author} {\bibfnamefont {William~H}\ \bibnamefont {Cunningham}}, \bibinfo {author} {\bibfnamefont {William~R}\ \bibnamefont {Pulleyblank}}, \ and\ \bibinfo {author} {\bibfnamefont {Alexander}\ \bibnamefont {Schrijver}},\ }\enquote {\bibinfo {title} {Wiley-interscience series in discrete mathematics and optimization},}\ in\ \href {\doibase https://doi.org/10.1002/9781118033142.scard} {\emph {\bibinfo {booktitle} {Combinatorial Optimization}}}\ (\bibinfo  {publisher} {John Wiley \& Sons, Ltd},\ \bibinfo {year} {1997})\ pp.\ \bibinfo {pages} {356--356}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Cook}\ \emph {et~al.}(2011)\citenamefont {Cook}, \citenamefont {Applegate}, \citenamefont {Bixby},\ and\ \citenamefont {Chvatal}}]{cook2011traveling}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {William~J}\ \bibnamefont {Cook}}, \bibinfo {author} {\bibfnamefont {David~L}\ \bibnamefont {Applegate}}, \bibinfo {author} {\bibfnamefont {Robert~E}\ \bibnamefont {Bixby}}, \ and\ \bibinfo {author} {\bibfnamefont {Vasek}\ \bibnamefont {Chvatal}},\ }\href@noop {} {\emph {\bibinfo {title} {The traveling salesman problem: a computational study}}}\ (\bibinfo  {publisher} {Princeton university press},\ \bibinfo {year} {2011})\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Cook}(2012)}]{cook2012pursuit}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {William~J}\ \bibnamefont {Cook}},\ }\href@noop {} {\emph {\bibinfo {title} {{In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation}}}}\ (\bibinfo  {publisher} {Princeton university press},\ \bibinfo {year} {2012})\BibitemShut {NoStop}%
\bibitem [{coo(2023)}]{cook2024startsp}%
\BibitemOpen
\href {https://www.math.uwaterloo.ca/tsp/star/about.html} {\enquote {\bibinfo {title} {{3D Star TSPs}},}\ } (\bibinfo {year} {2023}),\ \bibinfo {note} {{accessed Dec 3, 2023}}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Puchinger}\ \emph {et~al.}(2010)\citenamefont {Puchinger}, \citenamefont {Raidl},\ and\ \citenamefont {Pferschy}}]{puchinger2010multidimensional}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Jakob}\ \bibnamefont {Puchinger}}, \bibinfo {author} {\bibfnamefont {G\"{u}nther~R.}\ \bibnamefont {Raidl}}, \ and\ \bibinfo {author} {\bibfnamefont {Ulrich}\ \bibnamefont {Pferschy}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {{The Multidimensional Knapsack Problem: Structure and Algorithms}},}\ }\href {\doibase 10.1287/ijoc.1090.0344} {\bibfield  {journal} {\bibinfo  {journal} {INFORMS J. on Computing}\ }\textbf {\bibinfo {volume} {22}},\ \bibinfo {pages} {250–265} (\bibinfo {year} {2010})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Packebusch}\ and\ \citenamefont {Mertens}(2016)}]{Packebusch_2016}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Tom}\ \bibnamefont {Packebusch}}\ and\ \bibinfo {author} {\bibfnamefont {Stephan}\ \bibnamefont {Mertens}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Low autocorrelation binary sequences},}\ }\href {\doibase 10.1088/1751-8113/49/16/165001} {\bibfield  {journal} {\bibinfo  {journal} {Journal of Physics A: Mathematical and Theoretical}\ }\textbf {\bibinfo {volume} {49}},\ \bibinfo {pages} {165001} (\bibinfo {year} {2016})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Bravyi}\ \emph {et~al.}(2023{\natexlab{a}})\citenamefont {Bravyi}, \citenamefont {Cross}, \citenamefont {Gambetta}, \citenamefont {Maslov}, \citenamefont {Rall},\ and\ \citenamefont {Yoder}}]{bravyi2023highthreshold}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Sergey}\ \bibnamefont {Bravyi}}, \bibinfo {author} {\bibfnamefont {Andrew~W.}\ \bibnamefont {Cross}}, \bibinfo {author} {\bibfnamefont {Jay~M.}\ \bibnamefont {Gambetta}}, \bibinfo {author} {\bibfnamefont {Dmitri}\ \bibnamefont {Maslov}}, \bibinfo {author} {\bibfnamefont {Patrick}\ \bibnamefont {Rall}}, \ and\ \bibinfo {author} {\bibfnamefont {Theodore~J.}\ \bibnamefont {Yoder}},\ }\href@noop {} {\enquote {\bibinfo {title} {High-threshold and low-overhead fault-tolerant quantum memory},}\ } (\bibinfo {year} {2023}{\natexlab{a}}),\ \Eprint {http://arxiv.org/abs/2308.07915} {arXiv:2308.07915 [quant-ph]} \BibitemShut {NoStop}%
\bibitem [{\citenamefont {Temme}\ \emph {et~al.}(2017)\citenamefont {Temme}, \citenamefont {Bravyi},\ and\ \citenamefont {Gambetta}}]{Temme2017}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Kristan}\ \bibnamefont {Temme}}, \bibinfo {author} {\bibfnamefont {Sergey}\ \bibnamefont {Bravyi}}, \ and\ \bibinfo {author} {\bibfnamefont {Jay~M.}\ \bibnamefont {Gambetta}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Error mitigation for short-depth quantum circuits},}\ }\href {https://doi.org/10.1103/physrevlett.119.180509} {\bibfield  {journal} {\bibinfo  {journal} {Physical Review Letters}\ }\textbf {\bibinfo {volume} {119}} (\bibinfo {year} {2017})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {van~den Berg}\ \emph {et~al.}(2023)\citenamefont {van~den Berg}, \citenamefont {Minev}, \citenamefont {Kandala},\ and\ \citenamefont {Temme}}]{VandenBerg2023}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Ewout}\ \bibnamefont {van~den Berg}}, \bibinfo {author} {\bibfnamefont {Zlatko~K.}\ \bibnamefont {Minev}}, \bibinfo {author} {\bibfnamefont {Abhinav}\ \bibnamefont {Kandala}}, \ and\ \bibinfo {author} {\bibfnamefont {Kristan}\ \bibnamefont {Temme}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Probabilistic error cancellation with sparse pauli--lindblad models on noisy quantum processors},}\ }\href {\doibase 10.1038/s41567-023-02042-2} {\bibfield  {journal} {\bibinfo  {journal} {Nature Physics}\ }\textbf {\bibinfo {volume} {19}},\ \bibinfo {pages} {1116--1121} (\bibinfo {year} {2023})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Kim}\ \emph {et~al.}(2023)\citenamefont {Kim}, \citenamefont {Eddins}, \citenamefont {Anand}, \citenamefont {Wei}, \citenamefont {van~den Berg}, \citenamefont {Rosenblatt}, \citenamefont {Nayfeh}, \citenamefont {Wu}, \citenamefont {Zaletel}, \citenamefont {Temme},\ and\ \citenamefont {Kandala}}]{Kim2023}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Youngseok}\ \bibnamefont {Kim}}, \bibinfo {author} {\bibfnamefont {Andrew}\ \bibnamefont {Eddins}}, \bibinfo {author} {\bibfnamefont {Sajant}\ \bibnamefont {Anand}}, \bibinfo {author} {\bibfnamefont {Ken~Xuan}\ \bibnamefont {Wei}}, \bibinfo {author} {\bibfnamefont {Ewout}\ \bibnamefont {van~den Berg}}, \bibinfo {author} {\bibfnamefont {Sami}\ \bibnamefont {Rosenblatt}}, \bibinfo {author} {\bibfnamefont {Hasan}\ \bibnamefont {Nayfeh}}, \bibinfo {author} {\bibfnamefont {Yantao}\ \bibnamefont {Wu}}, \bibinfo {author} {\bibfnamefont {Michael}\ \bibnamefont {Zaletel}}, \bibinfo {author} {\bibfnamefont {Kristan}\ \bibnamefont {Temme}}, \ and\ \bibinfo {author} {\bibfnamefont {Abhinav}\ \bibnamefont {Kandala}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Evidence for the utility of quantum computing before fault tolerance},}\ }\href {\doibase 10.1038/s41586-023-06096-3} {\bibfield  {journal} {\bibinfo  {journal} {Nature}\ }\textbf {\bibinfo {volume} {618}},\ \bibinfo {pages} {500--505} (\bibinfo {year} {2023})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Shor}(1994{\natexlab{a}})}]{shor_1994_factoring}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {P.W.}\ \bibnamefont {Shor}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Algorithms for quantum computation: discrete logarithms and factoring},}\ }in\ \href {\doibase 10.1109/SFCS.1994.365700} {\emph {\bibinfo {booktitle} {Proceedings 35th Annual Symposium on Foundations of Computer Science}}}\ (\bibinfo {year} {1994})\ pp.\ \bibinfo {pages} {124--134}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Gidney}\ and\ \citenamefont {Eker{\aa{}}}(2021)}]{Gidney2021howtofactorbit}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Craig}\ \bibnamefont {Gidney}}\ and\ \bibinfo {author} {\bibfnamefont {Martin}\ \bibnamefont {Eker{\aa{}}}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {How to factor 2048 bit {RSA} integers in 8 hours using 20 million noisy qubits},}\ }\href {\doibase 10.22331/q-2021-04-15-433} {\bibfield  {journal} {\bibinfo  {journal} {{Quantum}}\ }\textbf {\bibinfo {volume} {5}},\ \bibinfo {pages} {433} (\bibinfo {year} {2021})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Arora}\ and\ \citenamefont {Barak}(2009{\natexlab{a}})}]{arora2009computational}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Sanjeev}\ \bibnamefont {Arora}}\ and\ \bibinfo {author} {\bibfnamefont {Boaz}\ \bibnamefont {Barak}},\ }\href {\doibase 10.1017/CBO9780511804090} {\emph {\bibinfo {title} {{Computational Complexity: A Modern Approach}}}}\ (\bibinfo  {publisher} {Cambridge University Press},\ \bibinfo {year} {2009})\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Watrous}(2009)}]{watrous2008quantum}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {John}\ \bibnamefont {Watrous}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Quantum {Computational} {Complexity}},}\ }in\ \href {\doibase 10.1007/978-0-387-30440-3_428} {\emph {\bibinfo {booktitle} {Encyclopedia of {Complexity} and {Systems} {Science}}}},\ \bibinfo {editor} {edited by\ \bibinfo {editor} {\bibfnamefont {Robert~A.}\ \bibnamefont {Meyers}}}\ (\bibinfo  {publisher} {Springer New York},\ \bibinfo {address} {New York, NY},\ \bibinfo {year} {2009})\ pp.\ \bibinfo {pages} {7174--7201}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {de~Wolf}(2023)}]{de2019quantum}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Ronald}\ \bibnamefont {de~Wolf}},\ }\href@noop {} {\enquote {\bibinfo {title} {Quantum computing: Lecture notes},}\ } (\bibinfo {year} {2023}),\ \Eprint {http://arxiv.org/abs/1907.09415} {arXiv:1907.09415 [quant-ph]} \BibitemShut {NoStop}%
\bibitem [{\citenamefont {Bellman}(1962)}]{bellman1962dynamic}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Richard}\ \bibnamefont {Bellman}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Dynamic programming treatment of the travelling salesman problem},}\ }\href {\doibase 10.1145/321105.321111} {\bibfield  {journal} {\bibinfo  {journal} {J. ACM}\ }\textbf {\bibinfo {volume} {9}},\ \bibinfo {pages} {61–63} (\bibinfo {year} {1962})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Held}\ and\ \citenamefont {Karp}(1962)}]{held1962dynamic}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Michael}\ \bibnamefont {Held}}\ and\ \bibinfo {author} {\bibfnamefont {Richard~M.}\ \bibnamefont {Karp}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {{A Dynamic Programming Approach to Sequencing Problems}},}\ }\href {\doibase 10.1137/0110015} {\bibfield  {journal} {\bibinfo  {journal} {Journal of the Society for Industrial and Applied Mathematics}\ }\textbf {\bibinfo {volume} {10}},\ \bibinfo {pages} {196--210} (\bibinfo {year} {1962})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Björklund}\ \emph {et~al.}(2014)\citenamefont {Björklund}, \citenamefont {Kaski},\ and\ \citenamefont {Kowalik}}]{bjoerklund2015fast}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Andreas}\ \bibnamefont {Björklund}}, \bibinfo {author} {\bibfnamefont {Petteri}\ \bibnamefont {Kaski}}, \ and\ \bibinfo {author} {\bibfnamefont {Lukasz}\ \bibnamefont {Kowalik}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {{Fast Witness Extraction using a Decision Oracle}},}\ }in\ \href {\doibase 10.1007/978-3-662-44777-2_13} {\emph {\bibinfo {booktitle} {Algorithms - ESA 2014/Lecture notes in computer science}}},\ Vol.\ \bibinfo {volume} {8737},\ \bibinfo {editor} {edited by\ \bibinfo {editor} {\bibfnamefont {Andreas}\ \bibnamefont {Schulz}}\ and\ \bibinfo {editor} {\bibfnamefont {Dorothea}\ \bibnamefont {Wagner}}}\ (\bibinfo  {publisher} {Springer},\ \bibinfo {year} {2014})\ pp.\ \bibinfo {pages} {149--160}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Ausiello}\ \emph {et~al.}(2012)\citenamefont {Ausiello}, \citenamefont {Crescenzi}, \citenamefont {Gambosi}, \citenamefont {Kann}, \citenamefont {Marchetti-Spaccamela},\ and\ \citenamefont {Protasi}}]{ausiello2012complexity}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Giorgio}\ \bibnamefont {Ausiello}}, \bibinfo {author} {\bibfnamefont {Pierluigi}\ \bibnamefont {Crescenzi}}, \bibinfo {author} {\bibfnamefont {Giorgio}\ \bibnamefont {Gambosi}}, \bibinfo {author} {\bibfnamefont {Viggo}\ \bibnamefont {Kann}}, \bibinfo {author} {\bibfnamefont {Alberto}\ \bibnamefont {Marchetti-Spaccamela}}, \ and\ \bibinfo {author} {\bibfnamefont {Marco}\ \bibnamefont {Protasi}},\ }\href {https://dl.acm.org/doi/10.5555/554706} {\emph {\bibinfo {title} {Complexity and approximation: Combinatorial optimization problems and their approximability properties}}}\ (\bibinfo  {publisher} {Springer Science \& Business Media},\ \bibinfo {year} {2012})\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Bernstein}\ and\ \citenamefont {Vazirani}(1997)}]{Bernstein1997}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Ethan}\ \bibnamefont {Bernstein}}\ and\ \bibinfo {author} {\bibfnamefont {Umesh}\ \bibnamefont {Vazirani}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Quantum complexity theory},}\ }\href {\doibase 10.1137/s0097539796300921} {\bibfield  {journal} {\bibinfo  {journal} {{SIAM} Journal on Computing}\ }\textbf {\bibinfo {volume} {26}},\ \bibinfo {pages} {1411--1473} (\bibinfo {year} {1997})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Yamakawa}\ and\ \citenamefont {Zhandry}(2022)}]{yamakawa2022verifiable}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Takashi}\ \bibnamefont {Yamakawa}}\ and\ \bibinfo {author} {\bibfnamefont {Mark}\ \bibnamefont {Zhandry}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Verifiable quantum advantage without structure},}\ }in\ \href {https://ieeexplore.ieee.org/document/9996892} {\emph {\bibinfo {booktitle} {2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)}}}\ (\bibinfo {organization} {IEEE},\ \bibinfo {year} {2022})\ pp.\ \bibinfo {pages} {69--74}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Arora}\ \emph {et~al.}(2023)\citenamefont {Arora}, \citenamefont {Coladangelo}, \citenamefont {Coudron}, \citenamefont {Gheorghiu}, \citenamefont {Singh},\ and\ \citenamefont {Waldner}}]{arora2023quantum}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Atul~Singh}\ \bibnamefont {Arora}}, \bibinfo {author} {\bibfnamefont {Andrea}\ \bibnamefont {Coladangelo}}, \bibinfo {author} {\bibfnamefont {Matthew}\ \bibnamefont {Coudron}}, \bibinfo {author} {\bibfnamefont {Alexandru}\ \bibnamefont {Gheorghiu}}, \bibinfo {author} {\bibfnamefont {Uttam}\ \bibnamefont {Singh}}, \ and\ \bibinfo {author} {\bibfnamefont {Hendrik}\ \bibnamefont {Waldner}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Quantum depth in the random oracle model},}\ }in\ \href@noop {} {\emph {\bibinfo {booktitle} {Proceedings of the 55th Annual ACM Symposium on Theory of Computing}}}\ (\bibinfo {year} {2023})\ pp.\ \bibinfo {pages} {1111--1124}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Karp}(1972)}]{Karp1972}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Richard~M.}\ \bibnamefont {Karp}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Reducibility among combinatorial problems},}\ }in\ \href {\doibase 10.1007/978-1-4684-2001-2_9} {\emph {\bibinfo {booktitle} {Complexity of Computer Computations}}}\ (\bibinfo  {publisher} {Springer {US}},\ \bibinfo {year} {1972})\ pp.\ \bibinfo {pages} {85--103}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Beals}\ \emph {et~al.}(2001)\citenamefont {Beals}, \citenamefont {Buhrman}, \citenamefont {Cleve}, \citenamefont {Mosca},\ and\ \citenamefont {De~Wolf}}]{beals2001quantum}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Robert}\ \bibnamefont {Beals}}, \bibinfo {author} {\bibfnamefont {Harry}\ \bibnamefont {Buhrman}}, \bibinfo {author} {\bibfnamefont {Richard}\ \bibnamefont {Cleve}}, \bibinfo {author} {\bibfnamefont {Michele}\ \bibnamefont {Mosca}}, \ and\ \bibinfo {author} {\bibfnamefont {Ronald}\ \bibnamefont {De~Wolf}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Quantum lower bounds by polynomials},}\ }\href@noop {} {\bibfield  {journal} {\bibinfo  {journal} {Journal of the ACM (JACM)}\ }\textbf {\bibinfo {volume} {48}},\ \bibinfo {pages} {778--797} (\bibinfo {year} {2001})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Bennett}\ \emph {et~al.}(1997{\natexlab{a}})\citenamefont {Bennett}, \citenamefont {Bernstein}, \citenamefont {Brassard},\ and\ \citenamefont {Vazirani}}]{bennett1997strengths}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Charles~H}\ \bibnamefont {Bennett}}, \bibinfo {author} {\bibfnamefont {Ethan}\ \bibnamefont {Bernstein}}, \bibinfo {author} {\bibfnamefont {Gilles}\ \bibnamefont {Brassard}}, \ and\ \bibinfo {author} {\bibfnamefont {Umesh}\ \bibnamefont {Vazirani}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Strengths and weaknesses of quantum computing},}\ }\href@noop {} {\bibfield  {journal} {\bibinfo  {journal} {SIAM journal on Computing}\ }\textbf {\bibinfo {volume} {26}},\ \bibinfo {pages} {1510--1523} (\bibinfo {year} {1997}{\natexlab{a}})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Aaronson}(2022)}]{aaronson2022much}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Scott}\ \bibnamefont {Aaronson}},\ }\href@noop {} {\enquote {\bibinfo {title} {How much structure is needed for huge quantum speedups?}}\ } (\bibinfo {year} {2022}),\ \bibinfo {note} {talk delivered at the 28th Solvay Physics Conference},\ \Eprint {http://arxiv.org/abs/2209.06930} {arXiv:2209.06930 [quant-ph]} \BibitemShut {NoStop}%
\bibitem [{\citenamefont {Gharibian}(2023)}]{gharibian20237}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Sevag}\ \bibnamefont {Gharibian}},\ }\href@noop {} {\enquote {\bibinfo {title} {{The 7 faces of quantum NP}},}\ } (\bibinfo {year} {2023}),\ \Eprint {http://arxiv.org/abs/2310.18010} {arXiv:2310.18010 [quant-ph]} \BibitemShut {NoStop}%
\bibitem [{Note1()}]{Note1}%
\BibitemOpen
\bibinfo {note} {There is a slight technical complication here, because we deal with a class that has a promise: either there exists a quantum proof that makes the quantum verifier accept with high probability or for every proof the verifier rejects with high probability. In the strict sense such a promise class is not known to contain complete problems. In order to still use the notion of completeness a framework of promise problems is introduced~\cite {goldreich2005promise} for additional technical details}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Madsen}\ \emph {et~al.}(2022)\citenamefont {Madsen}, \citenamefont {Laudenbach}, \citenamefont {Askarani}, \citenamefont {Rortais}, \citenamefont {Vincent}, \citenamefont {Bulmer}, \citenamefont {Miatto}, \citenamefont {Neuhaus}, \citenamefont {Helt}, \citenamefont {Collins}, \citenamefont {Lita}, \citenamefont {Gerrits}, \citenamefont {Nam}, \citenamefont {Vaidya}, \citenamefont {Menotti}, \citenamefont {Dhand}, \citenamefont {Vernon}, \citenamefont {Quesada},\ and\ \citenamefont {Lavoie}}]{Madsen2022}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Lars~S.}\ \bibnamefont {Madsen}}, \bibinfo {author} {\bibfnamefont {Fabian}\ \bibnamefont {Laudenbach}}, \bibinfo {author} {\bibfnamefont {Mohsen~Falamarzi.}\ \bibnamefont {Askarani}}, \bibinfo {author} {\bibfnamefont {Fabien}\ \bibnamefont {Rortais}}, \bibinfo {author} {\bibfnamefont {Trevor}\ \bibnamefont {Vincent}}, \bibinfo {author} {\bibfnamefont {Jacob F.~F.}\ \bibnamefont {Bulmer}}, \bibinfo {author} {\bibfnamefont {Filippo~M.}\ \bibnamefont {Miatto}}, \bibinfo {author} {\bibfnamefont {Leonhard}\ \bibnamefont {Neuhaus}}, \bibinfo {author} {\bibfnamefont {Lukas~G.}\ \bibnamefont {Helt}}, \bibinfo {author} {\bibfnamefont {Matthew~J.}\ \bibnamefont {Collins}}, \bibinfo {author} {\bibfnamefont {Adriana~E.}\ \bibnamefont {Lita}}, \bibinfo {author} {\bibfnamefont {Thomas}\ \bibnamefont {Gerrits}}, \bibinfo {author} {\bibfnamefont {Sae~Woo}\ \bibnamefont {Nam}}, \bibinfo {author} {\bibfnamefont {Varun~D.}\ \bibnamefont {Vaidya}}, \bibinfo {author} {\bibfnamefont {Matteo}\ \bibnamefont {Menotti}}, \bibinfo {author} {\bibfnamefont {Ish}\ \bibnamefont {Dhand}}, \bibinfo {author} {\bibfnamefont {Zachary}\ \bibnamefont {Vernon}}, \bibinfo {author} {\bibfnamefont {Nicol{\'{a}}s}\ \bibnamefont {Quesada}}, \ and\ \bibinfo {author} {\bibfnamefont {Jonathan}\ \bibnamefont {Lavoie}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Quantum computational advantage with a programmable photonic processor},}\ }\href {\doibase 10.1038/s41586-022-04725-x} {\bibfield  {journal} {\bibinfo  {journal} {Nature}\ }\textbf {\bibinfo {volume} {606}},\ \bibinfo {pages} {75--81} (\bibinfo {year} {2022})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Marriott}\ and\ \citenamefont {Watrous}(2005)}]{Marriott2005}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Chris}\ \bibnamefont {Marriott}}\ and\ \bibinfo {author} {\bibfnamefont {John}\ \bibnamefont {Watrous}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Quantum arthur{\textendash}merlin games},}\ }\href {\doibase 10.1007/s00037-005-0194-x} {\bibfield  {journal} {\bibinfo  {journal} {computational complexity}\ }\textbf {\bibinfo {volume} {14}},\ \bibinfo {pages} {122--152} (\bibinfo {year} {2005})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Arora}\ and\ \citenamefont {Barak}(2009{\natexlab{b}})}]{Arora2009}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Sanjeev}\ \bibnamefont {Arora}}\ and\ \bibinfo {author} {\bibfnamefont {Boaz}\ \bibnamefont {Barak}},\ }\href {\doibase 10.1017/cbo9780511804090} {\emph {\bibinfo {title} {Computational Complexity}}}\ (\bibinfo  {publisher} {Cambridge University Press},\ \bibinfo {year} {2009})\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Raz}\ and\ \citenamefont {Tal}(2022)}]{raz2022oracle}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Ran}\ \bibnamefont {Raz}}\ and\ \bibinfo {author} {\bibfnamefont {Avishay}\ \bibnamefont {Tal}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Oracle separation of bqp and ph},}\ }\href@noop {} {\bibfield  {journal} {\bibinfo  {journal} {ACM Journal of the ACM (JACM)}\ }\textbf {\bibinfo {volume} {69}},\ \bibinfo {pages} {1--21} (\bibinfo {year} {2022})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Chen}\ \emph {et~al.}(2023)\citenamefont {Chen}, \citenamefont {Cotler}, \citenamefont {Huang},\ and\ \citenamefont {Li}}]{chen2023complexity}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Sitan}\ \bibnamefont {Chen}}, \bibinfo {author} {\bibfnamefont {Jordan}\ \bibnamefont {Cotler}}, \bibinfo {author} {\bibfnamefont {Hsin-Yuan}\ \bibnamefont {Huang}}, \ and\ \bibinfo {author} {\bibfnamefont {Jerry}\ \bibnamefont {Li}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {{The complexity of NISQ}},}\ }\href@noop {} {\bibfield  {journal} {\bibinfo  {journal} {Nature Communications}\ }\textbf {\bibinfo {volume} {14}},\ \bibinfo {pages} {6001} (\bibinfo {year} {2023})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Buhrman}\ \emph {et~al.}(2021)\citenamefont {Buhrman}, \citenamefont {Patro},\ and\ \citenamefont {Speelman}}]{buhrman2021framework}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Harry}\ \bibnamefont {Buhrman}}, \bibinfo {author} {\bibfnamefont {Subhasree}\ \bibnamefont {Patro}}, \ and\ \bibinfo {author} {\bibfnamefont {Florian}\ \bibnamefont {Speelman}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {A framework of quantum strong exponential-time hypotheses},}\ }in\ \href@noop {} {\emph {\bibinfo {booktitle} {{38th International symposium on theoretical aspects of computer science (stacs 2021)}}}}\ (\bibinfo {organization} {Schloss Dagstuhl-Leibniz-Zentrum f{\"u}r Informatik},\ \bibinfo {year} {2021})\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Garey}\ and\ \citenamefont {Johnson}(1990)}]{10.5555/574848}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Michael~R.}\ \bibnamefont {Garey}}\ and\ \bibinfo {author} {\bibfnamefont {David~S.}\ \bibnamefont {Johnson}},\ }\href@noop {} {\emph {\bibinfo {title} {Computers and Intractability; A Guide to the Theory of NP-Completeness}}}\ (\bibinfo  {publisher} {W. H. Freeman \& Co.},\ \bibinfo {address} {USA},\ \bibinfo {year} {1990})\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Downey}\ and\ \citenamefont {Fellows}(1999)}]{Downey1999}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {R.~G.}\ \bibnamefont {Downey}}\ and\ \bibinfo {author} {\bibfnamefont {M.~R.}\ \bibnamefont {Fellows}},\ }\href {\doibase 10.1007/978-1-4612-0515-9} {\emph {\bibinfo {title} {Parameterized Complexity}}}\ (\bibinfo  {publisher} {Springer New York},\ \bibinfo {year} {1999})\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Cai}\ and\ \citenamefont {Chen}(1997)}]{cai1997fixed}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Liming}\ \bibnamefont {Cai}}\ and\ \bibinfo {author} {\bibfnamefont {Jianer}\ \bibnamefont {Chen}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {On fixed-parameter tractability and approximability of np optimization problems},}\ }\href@noop {} {\bibfield  {journal} {\bibinfo  {journal} {Journal of Computer and System Sciences}\ }\textbf {\bibinfo {volume} {54}},\ \bibinfo {pages} {465--474} (\bibinfo {year} {1997})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Chen}\ \emph {et~al.}(2010)\citenamefont {Chen}, \citenamefont {Kanj},\ and\ \citenamefont {Xia}}]{Chen2010}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Jianer}\ \bibnamefont {Chen}}, \bibinfo {author} {\bibfnamefont {Iyad~A.}\ \bibnamefont {Kanj}}, \ and\ \bibinfo {author} {\bibfnamefont {Ge}~\bibnamefont {Xia}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Improved upper bounds for vertex cover},}\ }\href {\doibase 10.1016/j.tcs.2010.06.026} {\bibfield  {journal} {\bibinfo  {journal} {Theoretical Computer Science}\ }\textbf {\bibinfo {volume} {411}},\ \bibinfo {pages} {3736--3756} (\bibinfo {year} {2010})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Bremner}\ \emph {et~al.}(2022)\citenamefont {Bremner}, \citenamefont {Ji}, \citenamefont {Mann}, \citenamefont {Mathieson}, \citenamefont {Morales},\ and\ \citenamefont {Shaw}}]{bremner2022quantum}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Michael~J.}\ \bibnamefont {Bremner}}, \bibinfo {author} {\bibfnamefont {Zhengfeng}\ \bibnamefont {Ji}}, \bibinfo {author} {\bibfnamefont {Ryan~L.}\ \bibnamefont {Mann}}, \bibinfo {author} {\bibfnamefont {Luke}\ \bibnamefont {Mathieson}}, \bibinfo {author} {\bibfnamefont {Mauro E.~S.}\ \bibnamefont {Morales}}, \ and\ \bibinfo {author} {\bibfnamefont {Alexis T.~E.}\ \bibnamefont {Shaw}},\ }\href@noop {} {\enquote {\bibinfo {title} {Quantum parameterized complexity},}\ } (\bibinfo {year} {2022}),\ \Eprint {http://arxiv.org/abs/2203.08002} {arXiv:2203.08002 [quant-ph]} \BibitemShut {NoStop}%
\bibitem [{\citenamefont {Fomin}\ \emph {et~al.}(2019)\citenamefont {Fomin}, \citenamefont {Lokshtanov}, \citenamefont {Saurabh},\ and\ \citenamefont {Zehavi}}]{fomin2019kernelization}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Fedor~V}\ \bibnamefont {Fomin}}, \bibinfo {author} {\bibfnamefont {Daniel}\ \bibnamefont {Lokshtanov}}, \bibinfo {author} {\bibfnamefont {Saket}\ \bibnamefont {Saurabh}}, \ and\ \bibinfo {author} {\bibfnamefont {Meirav}\ \bibnamefont {Zehavi}},\ }\href {https://doi.org/10.1017/9781107415157} {\emph {\bibinfo {title} {Kernelization: theory of parameterized preprocessing}}}\ (\bibinfo  {publisher} {Cambridge University Press},\ \bibinfo {year} {2019})\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Bodlaender}\ \emph {et~al.}(2016)\citenamefont {Bodlaender}, \citenamefont {Fomin}, \citenamefont {Lokshtanov}, \citenamefont {Penninkx}, \citenamefont {Saurabh},\ and\ \citenamefont {Thilikos}}]{KernelizationMeta}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Hans~L.}\ \bibnamefont {Bodlaender}}, \bibinfo {author} {\bibfnamefont {Fedor~V.}\ \bibnamefont {Fomin}}, \bibinfo {author} {\bibfnamefont {Daniel}\ \bibnamefont {Lokshtanov}}, \bibinfo {author} {\bibfnamefont {Eelko}\ \bibnamefont {Penninkx}}, \bibinfo {author} {\bibfnamefont {Saket}\ \bibnamefont {Saurabh}}, \ and\ \bibinfo {author} {\bibfnamefont {Dimitrios~M.}\ \bibnamefont {Thilikos}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {(meta) kernelization},}\ }\href {\doibase 10.1145/2973749} {\bibfield  {journal} {\bibinfo  {journal} {J. ACM}\ }\textbf {\bibinfo {volume} {63}} (\bibinfo {year} {2016}),\ 10.1145/2973749}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Johnson}(1974)}]{johnson1974max3sat}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {David~S.}\ \bibnamefont {Johnson}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Approximation algorithms for combinatorial problems},}\ }\href {\doibase 10.1016/S0022-0000(74)80044-9} {\bibfield  {journal} {\bibinfo  {journal} {Journal of Computer and System Sciences}\ }\textbf {\bibinfo {volume} {9}},\ \bibinfo {pages} {256--278} (\bibinfo {year} {1974})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {H\r{a}stad}(2001)}]{hastad2001inapproximability}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Johan}\ \bibnamefont {H\r{a}stad}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Some optimal inapproximability results},}\ }\href {\doibase 10.1145/502090.502098} {\bibfield  {journal} {\bibinfo  {journal} {Journal of the ACM}\ }\textbf {\bibinfo {volume} {48}},\ \bibinfo {pages} {798--859} (\bibinfo {year} {2001})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Goemans}\ and\ \citenamefont {Williamson}(1995{\natexlab{a}})}]{Goemans1995}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Michel~X.}\ \bibnamefont {Goemans}}\ and\ \bibinfo {author} {\bibfnamefont {David~P.}\ \bibnamefont {Williamson}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming},}\ }\href {\doibase 10.1145/227683.227684} {\bibfield  {journal} {\bibinfo  {journal} {J. ACM}\ }\textbf {\bibinfo {volume} {42}},\ \bibinfo {pages} {1115--1145} (\bibinfo {year} {1995}{\natexlab{a}})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Khot}\ \emph {et~al.}(2007)\citenamefont {Khot}, \citenamefont {Kindler}, \citenamefont {Mossel},\ and\ \citenamefont {O’Donnell}}]{khot2007inapproximability}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Subhash}\ \bibnamefont {Khot}}, \bibinfo {author} {\bibfnamefont {Guy}\ \bibnamefont {Kindler}}, \bibinfo {author} {\bibfnamefont {Elchanan}\ \bibnamefont {Mossel}}, \ and\ \bibinfo {author} {\bibfnamefont {Ryan}\ \bibnamefont {O’Donnell}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {{Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?}}}\ }\href {\doibase 10.1137/S0097539705447372} {\bibfield  {journal} {\bibinfo  {journal} {SIAM Journal on Computing}\ }\textbf {\bibinfo {volume} {37}},\ \bibinfo {pages} {319--357} (\bibinfo {year} {2007})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Khot}(2002)}]{khot2002uniquegames}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Subhash}\ \bibnamefont {Khot}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {On the power of unique 2-prover 1-round games},}\ }in\ \href {\doibase 10.1145/509907.510017} {\emph {\bibinfo {booktitle} {34th Annual ACM Symposium on Theory of Computing STOC'02}}}\ (\bibinfo {year} {2002})\ pp.\ \bibinfo {pages} {767--775}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Lund}\ and\ \citenamefont {Yannakakis}(1994)}]{Lund1994}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Carsten}\ \bibnamefont {Lund}}\ and\ \bibinfo {author} {\bibfnamefont {Mihalis}\ \bibnamefont {Yannakakis}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {On the hardness of approximating minimization problems},}\ }\href {\doibase 10.1145/185675.306789} {\bibfield  {journal} {\bibinfo  {journal} {Journal of the {ACM}}\ }\textbf {\bibinfo {volume} {41}},\ \bibinfo {pages} {960--981} (\bibinfo {year} {1994})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Aharonov}\ \emph {et~al.}(2008)\citenamefont {Aharonov}, \citenamefont {Arad}, \citenamefont {Landau},\ and\ \citenamefont {Vazirani}}]{aharonov2008detectability}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Dorit}\ \bibnamefont {Aharonov}}, \bibinfo {author} {\bibfnamefont {Itai}\ \bibnamefont {Arad}}, \bibinfo {author} {\bibfnamefont {Zeph}\ \bibnamefont {Landau}}, \ and\ \bibinfo {author} {\bibfnamefont {Umesh}\ \bibnamefont {Vazirani}},\ }\href@noop {} {\enquote {\bibinfo {title} {The detectability lemma and quantum gap amplification},}\ } (\bibinfo {year} {2008}),\ \Eprint {http://arxiv.org/abs/0811.3412} {arXiv:0811.3412 [quant-ph]} \BibitemShut {NoStop}%
\bibitem [{\citenamefont {Aharonov}\ and\ \citenamefont {Naveh}(2002)}]{aharonov2002quantum}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Dorit}\ \bibnamefont {Aharonov}}\ and\ \bibinfo {author} {\bibfnamefont {Tomer}\ \bibnamefont {Naveh}},\ }\href@noop {} {\enquote {\bibinfo {title} {Quantum np - a survey},}\ } (\bibinfo {year} {2002}),\ \Eprint {http://arxiv.org/abs/quant-ph/0210077} {arXiv:quant-ph/0210077 [quant-ph]} \BibitemShut {NoStop}%
\bibitem [{\citenamefont {Aharonov}\ \emph {et~al.}(2013{\natexlab{a}})\citenamefont {Aharonov}, \citenamefont {Arad},\ and\ \citenamefont {Vidick}}]{aharonov2013guest}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Dorit}\ \bibnamefont {Aharonov}}, \bibinfo {author} {\bibfnamefont {Itai}\ \bibnamefont {Arad}}, \ and\ \bibinfo {author} {\bibfnamefont {Thomas}\ \bibnamefont {Vidick}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Guest column: The quantum pcp conjecture},}\ }\href {\doibase 10.1145/2491533.2491549} {\bibfield  {journal} {\bibinfo  {journal} {SIGACT News}\ }\textbf {\bibinfo {volume} {44}},\ \bibinfo {pages} {47–79} (\bibinfo {year} {2013}{\natexlab{a}})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Kitaev}\ \emph {et~al.}(2002)\citenamefont {Kitaev}, \citenamefont {Shen},\ and\ \citenamefont {Vyalyi}}]{kitaev2002classical}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Alexei~Yu}\ \bibnamefont {Kitaev}}, \bibinfo {author} {\bibfnamefont {Alexander}\ \bibnamefont {Shen}}, \ and\ \bibinfo {author} {\bibfnamefont {Mikhail~N}\ \bibnamefont {Vyalyi}},\ }\href {https://doi.org/10.1090/gsm/047} {\emph {\bibinfo {title} {Classical and quantum computation}}},\ Vol.~\bibinfo {volume} {47}\ (\bibinfo  {publisher} {American Mathematical Soc.},\ \bibinfo {year} {2002})\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Anshu}\ \emph {et~al.}(2023)\citenamefont {Anshu}, \citenamefont {Breuckmann},\ and\ \citenamefont {Nirkhe}}]{nlts}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Anurag}\ \bibnamefont {Anshu}}, \bibinfo {author} {\bibfnamefont {Nikolas~P.}\ \bibnamefont {Breuckmann}}, \ and\ \bibinfo {author} {\bibfnamefont {Chinmay}\ \bibnamefont {Nirkhe}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Nlts hamiltonians from good quantum codes},}\ }in\ \href {\doibase 10.1145/3564246.3585114} {\emph {\bibinfo {booktitle} {Proceedings of the 55th Annual ACM Symposium on Theory of Computing}}},\ \bibinfo {series and number} {STOC 2023}\ (\bibinfo  {publisher} {Association for Computing Machinery},\ \bibinfo {address} {New York, NY, USA},\ \bibinfo {year} {2023})\ p.\ \bibinfo {pages} {1090–1096}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Karpinski}\ \emph {et~al.}(2015)\citenamefont {Karpinski}, \citenamefont {Lampis},\ and\ \citenamefont {Schmied}}]{karpinski2015inapproximabilityTSP}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Marek}\ \bibnamefont {Karpinski}}, \bibinfo {author} {\bibfnamefont {Michael}\ \bibnamefont {Lampis}}, \ and\ \bibinfo {author} {\bibfnamefont {Richard}\ \bibnamefont {Schmied}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {New inapproximability bounds for tsp},}\ }\href {\doibase 10.1016/j.jcss.2015.06.003} {\bibfield  {journal} {\bibinfo  {journal} {Journal of Computer and System Sciences}\ }\textbf {\bibinfo {volume} {81}},\ \bibinfo {pages} {1665--1677} (\bibinfo {year} {2015})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Karlin}\ \emph {et~al.}(2021)\citenamefont {Karlin}, \citenamefont {Klein},\ and\ \citenamefont {Gharan}}]{karlin2021approximationTSP}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Anna~R.}\ \bibnamefont {Karlin}}, \bibinfo {author} {\bibfnamefont {Nathan}\ \bibnamefont {Klein}}, \ and\ \bibinfo {author} {\bibfnamefont {Shayan~Oveis}\ \bibnamefont {Gharan}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {A (slightly) improved approximation algorithm for metric tsp},}\ }in\ \href {\doibase 10.1145/3406325.3451009} {\emph {\bibinfo {booktitle} {53rd Annual ACM SIGACT Symposium on Theory of Computing STOC'21}}}\ (\bibinfo {year} {2021})\ pp.\ \bibinfo {pages} {32--45}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Lee}\ and\ \citenamefont {Xu}(2021)}]{lee2021classifying}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Arthur}\ \bibnamefont {Lee}}\ and\ \bibinfo {author} {\bibfnamefont {Bruce}\ \bibnamefont {Xu}},\ }\href@noop {} {\enquote {\bibinfo {title} {Classifying approximation algorithms: Understanding the apx complexity class},}\ } (\bibinfo {year} {2021}),\ \Eprint {http://arxiv.org/abs/2111.01551} {arXiv:2111.01551 [cs.CC]} \BibitemShut {NoStop}%
\bibitem [{\citenamefont {Gonzalez}(2018)}]{gonzalez2018handbook}%
\BibitemOpen
\bibinfo {editor} {\bibfnamefont {Teofilo~F.}\ \bibnamefont {Gonzalez}},\ ed.,\ \href@noop {} {\emph {\bibinfo {title} {Handbook of Approximation Algorithms and Metaheuristics: Methologies and Traditional Applications}}},\ Vol.~\bibinfo {volume} {1}\ (\bibinfo  {publisher} {CRC Press},\ \bibinfo {year} {2018})\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Arora}(1998{\natexlab{a}})}]{arora1998polynomial}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Sanjeev}\ \bibnamefont {Arora}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems},}\ }\href@noop {} {\bibfield  {journal} {\bibinfo  {journal} {Journal of the ACM (JACM)}\ }\textbf {\bibinfo {volume} {45}},\ \bibinfo {pages} {753--782} (\bibinfo {year} {1998}{\natexlab{a}})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Spielman}\ and\ \citenamefont {Teng}(2009)}]{spielman2009smoothed}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Daniel~A}\ \bibnamefont {Spielman}}\ and\ \bibinfo {author} {\bibfnamefont {Shang-Hua}\ \bibnamefont {Teng}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Smoothed analysis: an attempt to explain the behavior of algorithms in practice},}\ }\href@noop {} {\bibfield  {journal} {\bibinfo  {journal} {Communications of the ACM}\ }\textbf {\bibinfo {volume} {52}},\ \bibinfo {pages} {76--84} (\bibinfo {year} {2009})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Bogdanov}\ \emph {et~al.}(2006)\citenamefont {Bogdanov}, \citenamefont {Trevisan} \emph {et~al.}}]{bogdanov2006average}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Andrej}\ \bibnamefont {Bogdanov}}, \bibinfo {author} {\bibfnamefont {Luca}\ \bibnamefont {Trevisan}},  \emph {et~al.},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Average-case complexity},}\ }\href@noop {} {\bibfield  {journal} {\bibinfo  {journal} {Foundations and Trends{\textregistered} in Theoretical Computer Science}\ }\textbf {\bibinfo {volume} {2}},\ \bibinfo {pages} {1--106} (\bibinfo {year} {2006})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Pirnay}\ \emph {et~al.}(2022)\citenamefont {Pirnay}, \citenamefont {Ulitzsch}, \citenamefont {Wilde}, \citenamefont {Eisert},\ and\ \citenamefont {Seifert}}]{PirnayCO2022}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Niklas}\ \bibnamefont {Pirnay}}, \bibinfo {author} {\bibfnamefont {Vincent}\ \bibnamefont {Ulitzsch}}, \bibinfo {author} {\bibfnamefont {Frederik}\ \bibnamefont {Wilde}}, \bibinfo {author} {\bibfnamefont {Jens}\ \bibnamefont {Eisert}}, \ and\ \bibinfo {author} {\bibfnamefont {Jean-Pierre}\ \bibnamefont {Seifert}},\ }\href@noop {} {\enquote {\bibinfo {title} {An in-principle super-polynomial quantum advantage for approximating combinatorial optimization problems},}\ } (\bibinfo {year} {2022}),\ \Eprint {http://arxiv.org/abs/arXiv:2212.08678} {arXiv:2212.08678} \BibitemShut {NoStop}%
\bibitem [{\citenamefont {Szegedy}(2022)}]{szegedy2022quantum}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Mario}\ \bibnamefont {Szegedy}},\ }\href@noop {} {\enquote {\bibinfo {title} {{Quantum advantage for combinatorial optimization problems, Simplified}},}\ } (\bibinfo {year} {2022}),\ \Eprint {http://arxiv.org/abs/2212.12572} {arXiv:2212.12572 [quant-ph]} \BibitemShut {NoStop}%
\bibitem [{\citenamefont {Ball}\ \emph {et~al.}(2017)\citenamefont {Ball}, \citenamefont {Rosen}, \citenamefont {Sabin},\ and\ \citenamefont {Vasudevan}}]{ball2017average}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Marshall}\ \bibnamefont {Ball}}, \bibinfo {author} {\bibfnamefont {Alon}\ \bibnamefont {Rosen}}, \bibinfo {author} {\bibfnamefont {Manuel}\ \bibnamefont {Sabin}}, \ and\ \bibinfo {author} {\bibfnamefont {Prashant~Nalini}\ \bibnamefont {Vasudevan}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Average-case fine-grained hardness},}\ }in\ \href@noop {} {\emph {\bibinfo {booktitle} {Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing}}}\ (\bibinfo {year} {2017})\ pp.\ \bibinfo {pages} {483--496}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Zhang}\ \emph {et~al.}(2022)\citenamefont {Zhang}, \citenamefont {Liu}, \citenamefont {Hsieh},\ and\ \citenamefont {Tao}}]{zhang2022escaping}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Kaining}\ \bibnamefont {Zhang}}, \bibinfo {author} {\bibfnamefont {Liu}\ \bibnamefont {Liu}}, \bibinfo {author} {\bibfnamefont {Min-Hsiu}\ \bibnamefont {Hsieh}}, \ and\ \bibinfo {author} {\bibfnamefont {Dacheng}\ \bibnamefont {Tao}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Escaping from the barren plateau via gaussian initializations in deep variational quantum circuits},}\ }\href@noop {} {\bibfield  {journal} {\bibinfo  {journal} {Advances in Neural Information Processing Systems}\ }\textbf {\bibinfo {volume} {35}},\ \bibinfo {pages} {18612--18627} (\bibinfo {year} {2022})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Fontana}\ \emph {et~al.}(2023)\citenamefont {Fontana}, \citenamefont {Herman}, \citenamefont {Chakrabarti}, \citenamefont {Kumar}, \citenamefont {Yalovetzky}, \citenamefont {Heredge}, \citenamefont {Sureshbabu},\ and\ \citenamefont {Pistoia}}]{fontana2023adjoint}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Enrico}\ \bibnamefont {Fontana}}, \bibinfo {author} {\bibfnamefont {Dylan}\ \bibnamefont {Herman}}, \bibinfo {author} {\bibfnamefont {Shouvanik}\ \bibnamefont {Chakrabarti}}, \bibinfo {author} {\bibfnamefont {Niraj}\ \bibnamefont {Kumar}}, \bibinfo {author} {\bibfnamefont {Romina}\ \bibnamefont {Yalovetzky}}, \bibinfo {author} {\bibfnamefont {Jamie}\ \bibnamefont {Heredge}}, \bibinfo {author} {\bibfnamefont {Shree~Hari}\ \bibnamefont {Sureshbabu}}, \ and\ \bibinfo {author} {\bibfnamefont {Marco}\ \bibnamefont {Pistoia}},\ }\href@noop {} {\enquote {\bibinfo {title} {The adjoint is all you need: Characterizing barren plateaus in quantum ans\"atze},}\ } (\bibinfo {year} {2023}),\ \Eprint {http://arxiv.org/abs/2309.07902} {arXiv:2309.07902 [quant-ph]} \BibitemShut {NoStop}%
\bibitem [{\citenamefont {Ragone}\ \emph {et~al.}(2023)\citenamefont {Ragone}, \citenamefont {Bakalov}, \citenamefont {Sauvage}, \citenamefont {Kemper}, \citenamefont {Marrero}, \citenamefont {Larocca},\ and\ \citenamefont {Cerezo}}]{ragone2023unified}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Michael}\ \bibnamefont {Ragone}}, \bibinfo {author} {\bibfnamefont {Bojko~N.}\ \bibnamefont {Bakalov}}, \bibinfo {author} {\bibfnamefont {Fr\'ed\'eric}\ \bibnamefont {Sauvage}}, \bibinfo {author} {\bibfnamefont {Alexander~F.}\ \bibnamefont {Kemper}}, \bibinfo {author} {\bibfnamefont {Carlos~Ortiz}\ \bibnamefont {Marrero}}, \bibinfo {author} {\bibfnamefont {Martin}\ \bibnamefont {Larocca}}, \ and\ \bibinfo {author} {\bibfnamefont {M.}~\bibnamefont {Cerezo}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {A unified theory of barren plateaus for deep parametrized quantum circuits},}\ }\href@noop {} {\bibfield  {journal} {\bibinfo  {journal} {arXiv preprint - arXiv:2309.09342}\ } (\bibinfo {year} {2023})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {McClean}\ \emph {et~al.}(2018)\citenamefont {McClean}, \citenamefont {Boixo}, \citenamefont {N.~Smelyanskiy}, \citenamefont {Babbush},\ and\ \citenamefont {Neven}}]{Clean_2018_BarrenPlateaus}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Jarrod}\ \bibnamefont {McClean}}, \bibinfo {author} {\bibfnamefont {Sergio}\ \bibnamefont {Boixo}}, \bibinfo {author} {\bibfnamefont {Vadim}\ \bibnamefont {N.~Smelyanskiy}}, \bibinfo {author} {\bibfnamefont {Ryan}\ \bibnamefont {Babbush}}, \ and\ \bibinfo {author} {\bibfnamefont {Hartmut}\ \bibnamefont {Neven}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Barren plateaus in quantum neural network training landscapes},}\ }\href {https://doi.org/10.1038/s41467-018-07090-4} {\bibfield  {journal} {\bibinfo  {journal} {Nature Communications}\ }\textbf {\bibinfo {volume} {9}} (\bibinfo {year} {2018})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Cerezo}\ \emph {et~al.}(2021{\natexlab{a}})\citenamefont {Cerezo}, \citenamefont {Sone}, \citenamefont {Volkoff}, \citenamefont {Cincio},\ and\ \citenamefont {Coles}}]{Cerezo_2021_costfunct}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {M.}~\bibnamefont {Cerezo}}, \bibinfo {author} {\bibfnamefont {Akira}\ \bibnamefont {Sone}}, \bibinfo {author} {\bibfnamefont {Tyler}\ \bibnamefont {Volkoff}}, \bibinfo {author} {\bibfnamefont {Lukasz}\ \bibnamefont {Cincio}}, \ and\ \bibinfo {author} {\bibfnamefont {Patrick~J.}\ \bibnamefont {Coles}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Cost function dependent barren plateaus in shallow parametrized quantum circuits},}\ }\href {\doibase 10.1038/s41467-021-21728-w} {\bibfield  {journal} {\bibinfo  {journal} {Nature Communications}\ }\textbf {\bibinfo {volume} {12}} (\bibinfo {year} {2021}{\natexlab{a}}),\ 10.1038/s41467-021-21728-w}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Cerezo}\ and\ \citenamefont {Coles}(2021)}]{Cerezo_2021higher_order_bps}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {M}~\bibnamefont {Cerezo}}\ and\ \bibinfo {author} {\bibfnamefont {Patrick~J}\ \bibnamefont {Coles}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Higher order derivatives of quantum neural networks with barren plateaus},}\ }\href {https://dx.doi.org/10.1088/2058-9565/abf51a} {\bibfield  {journal} {\bibinfo  {journal} {Quantum Science and Technology}\ }\textbf {\bibinfo {volume} {6}} (\bibinfo {year} {2021})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Holmes}\ \emph {et~al.}(2022)\citenamefont {Holmes}, \citenamefont {Sharma}, \citenamefont {Cerezo},\ and\ \citenamefont {Coles}}]{holmes2021AnsatzExpressBarrenPlateaus}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Zo\"e}\ \bibnamefont {Holmes}}, \bibinfo {author} {\bibfnamefont {Kunal}\ \bibnamefont {Sharma}}, \bibinfo {author} {\bibfnamefont {M.}~\bibnamefont {Cerezo}}, \ and\ \bibinfo {author} {\bibfnamefont {Patrick~J.}\ \bibnamefont {Coles}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Connecting ansatz expressibility to gradient magnitudes and barren plateaus},}\ }\href {\doibase 10.1103/PRXQuantum.3.010313} {\bibfield  {journal} {\bibinfo  {journal} {PRX Quantum}\ }\textbf {\bibinfo {volume} {3}} (\bibinfo {year} {2022}),\ 10.1103/PRXQuantum.3.010313}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Ortiz~Marrero}\ \emph {et~al.}(2021)\citenamefont {Ortiz~Marrero}, \citenamefont {Kieferov\'a},\ and\ \citenamefont {Wiebe}}]{Wiebe2020Barren}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Carlos}\ \bibnamefont {Ortiz~Marrero}}, \bibinfo {author} {\bibfnamefont {M\'aria}\ \bibnamefont {Kieferov\'a}}, \ and\ \bibinfo {author} {\bibfnamefont {Nathan}\ \bibnamefont {Wiebe}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Entanglement-induced barren plateaus},}\ }\href {\doibase 10.1103/PRXQuantum.2.040316} {\bibfield  {journal} {\bibinfo  {journal} {PRX Quantum}\ }\textbf {\bibinfo {volume} {2}},\ \bibinfo {pages} {040316} (\bibinfo {year} {2021})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Wang}\ \emph {et~al.}(2021{\natexlab{a}})\citenamefont {Wang}, \citenamefont {Fontana}, \citenamefont {Cerezo}, \citenamefont {Sharma}, \citenamefont {Sone}, \citenamefont {Cincio},\ and\ \citenamefont {Coles}}]{Wang_21_noiseinducedBPs}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Samson}\ \bibnamefont {Wang}}, \bibinfo {author} {\bibfnamefont {Enrico}\ \bibnamefont {Fontana}}, \bibinfo {author} {\bibfnamefont {M.}~\bibnamefont {Cerezo}}, \bibinfo {author} {\bibfnamefont {Kunal}\ \bibnamefont {Sharma}}, \bibinfo {author} {\bibfnamefont {Akira}\ \bibnamefont {Sone}}, \bibinfo {author} {\bibfnamefont {Lukasz}\ \bibnamefont {Cincio}}, \ and\ \bibinfo {author} {\bibfnamefont {Patrick~J.}\ \bibnamefont {Coles}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Noise-induced barren plateaus in variational quantum algorithms},}\ }\href {https://doi.org/10.1038/s41467-021-27045-6} {\bibfield  {journal} {\bibinfo  {journal} {Nature Communications}\ }\textbf {\bibinfo {volume} {12}} (\bibinfo {year} {2021}{\natexlab{a}})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Napp}(2022)}]{napp2022quantifying}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {John}\ \bibnamefont {Napp}},\ }\href@noop {} {\enquote {\bibinfo {title} {Quantifying the barren plateau phenomenon for a model of unstructured variational ans\"{a}tze},}\ } (\bibinfo {year} {2022}),\ \Eprint {http://arxiv.org/abs/2203.06174} {arXiv:2203.06174 [quant-ph]} \BibitemShut {NoStop}%
\bibitem [{\citenamefont {Uvarov}\ and\ \citenamefont {Biamonte}(2021)}]{Uvarov_2021BPs}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {A~V}\ \bibnamefont {Uvarov}}\ and\ \bibinfo {author} {\bibfnamefont {J~D}\ \bibnamefont {Biamonte}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {On barren plateaus and cost function locality in variational quantum algorithms},}\ }\href {https://dx.doi.org/10.1088/1751-8121/abfac7} {\bibfield  {journal} {\bibinfo  {journal} {Journal of Physics A: Mathematical and Theoretical}\ }\textbf {\bibinfo {volume} {54}},\ \bibinfo {pages} {245301} (\bibinfo {year} {2021})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Letcher}\ \emph {et~al.}(2023)\citenamefont {Letcher}, \citenamefont {Woerner},\ and\ \citenamefont {Zoufal}}]{letcher2023tight}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Alistair}\ \bibnamefont {Letcher}}, \bibinfo {author} {\bibfnamefont {Stefan}\ \bibnamefont {Woerner}}, \ and\ \bibinfo {author} {\bibfnamefont {Christa}\ \bibnamefont {Zoufal}},\ }\href@noop {} {\enquote {\bibinfo {title} {From tight gradient bounds for parameterized quantum circuits to the absence of barren plateaus in qgans},}\ } (\bibinfo {year} {2023}),\ \Eprint {http://arxiv.org/abs/2309.12681} {arXiv:2309.12681 [quant-ph]} \BibitemShut {NoStop}%
\bibitem [{\citenamefont {Papadimitriou}\ and\ \citenamefont {Yannakakis}(1991)}]{Papadimitriou1991}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Christos~H.}\ \bibnamefont {Papadimitriou}}\ and\ \bibinfo {author} {\bibfnamefont {Mihalis}\ \bibnamefont {Yannakakis}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Optimization, approximation, and complexity classes},}\ }\href {https://www.sciencedirect.com/science/article/pii/002200009190023X} {\bibfield  {journal} {\bibinfo  {journal} {Journal of Computer and System Sciences}\ }\textbf {\bibinfo {volume} {43}},\ \bibinfo {pages} {425--440} (\bibinfo {year} {1991})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Krentel}(1988)}]{KRENTEL1988490}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Mark~W.}\ \bibnamefont {Krentel}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {The complexity of optimization problems},}\ }\href {\doibase https://doi.org/10.1016/0022-0000(88)90039-6} {\bibfield  {journal} {\bibinfo  {journal} {Journal of Computer and System Sciences}\ }\textbf {\bibinfo {volume} {36}},\ \bibinfo {pages} {490--509} (\bibinfo {year} {1988})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Dyer}\ and\ \citenamefont {Stougie}(2006)}]{dyer2006computational}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Martin}\ \bibnamefont {Dyer}}\ and\ \bibinfo {author} {\bibfnamefont {Leen}\ \bibnamefont {Stougie}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Computational complexity of stochastic programming problems},}\ }\href@noop {} {\bibfield  {journal} {\bibinfo  {journal} {Mathematical Programming}\ }\textbf {\bibinfo {volume} {106}},\ \bibinfo {pages} {423--432} (\bibinfo {year} {2006})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Valiant}(1979)}]{valiant1979complexity}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Leslie~G}\ \bibnamefont {Valiant}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {The complexity of computing the permanent},}\ }\href@noop {} {\bibfield  {journal} {\bibinfo  {journal} {Theoretical computer science}\ }\textbf {\bibinfo {volume} {8}},\ \bibinfo {pages} {189--201} (\bibinfo {year} {1979})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Papadimitriou}(1985)}]{PAPADIMITRIOU1985288}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Christos~H.}\ \bibnamefont {Papadimitriou}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Games against nature},}\ }\href {\doibase https://doi.org/10.1016/0022-0000(85)90045-5} {\bibfield  {journal} {\bibinfo  {journal} {Journal of Computer and System Sciences}\ }\textbf {\bibinfo {volume} {31}},\ \bibinfo {pages} {288--301} (\bibinfo {year} {1985})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Lee}\ \emph {et~al.}(2023{\natexlab{a}})\citenamefont {Lee}, \citenamefont {Boche},\ and\ \citenamefont {Kutyniok}}]{lee2023computability}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Yunseok}\ \bibnamefont {Lee}}, \bibinfo {author} {\bibfnamefont {Holger}\ \bibnamefont {Boche}}, \ and\ \bibinfo {author} {\bibfnamefont {Gitta}\ \bibnamefont {Kutyniok}},\ }\href@noop {} {\enquote {\bibinfo {title} {Computability of optimizers},}\ } (\bibinfo {year} {2023}{\natexlab{a}}),\ \Eprint {http://arxiv.org/abs/2301.06148} {arXiv:2301.06148 [math.OC]} \BibitemShut {NoStop}%
\bibitem [{\citenamefont {Blum}\ \emph {et~al.}(1996)\citenamefont {Blum}, \citenamefont {Cucker}, \citenamefont {Shub},\ and\ \citenamefont {Smale}}]{blum1996complexity}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Lenore}\ \bibnamefont {Blum}}, \bibinfo {author} {\bibfnamefont {Felipe}\ \bibnamefont {Cucker}}, \bibinfo {author} {\bibfnamefont {Mike}\ \bibnamefont {Shub}}, \ and\ \bibinfo {author} {\bibfnamefont {Steve}\ \bibnamefont {Smale}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Complexity and real computation: A manifesto},}\ }\href@noop {} {\bibfield  {journal} {\bibinfo  {journal} {International Journal of Bifurcation and Chaos}\ }\textbf {\bibinfo {volume} {6}},\ \bibinfo {pages} {3--26} (\bibinfo {year} {1996})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Lemieux}\ \emph {et~al.}(2020)\citenamefont {Lemieux}, \citenamefont {Heim}, \citenamefont {Poulin}, \citenamefont {Svore},\ and\ \citenamefont {Troyer}}]{Lemieux2020efficientquantum}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Jessica}\ \bibnamefont {Lemieux}}, \bibinfo {author} {\bibfnamefont {Bettina}\ \bibnamefont {Heim}}, \bibinfo {author} {\bibfnamefont {David}\ \bibnamefont {Poulin}}, \bibinfo {author} {\bibfnamefont {Krysta}\ \bibnamefont {Svore}}, \ and\ \bibinfo {author} {\bibfnamefont {Matthias}\ \bibnamefont {Troyer}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Efficient {Q}uantum {W}alk {C}ircuits for {M}etropolis-{H}astings {A}lgorithm},}\ }\href {\doibase 10.22331/q-2020-06-29-287} {\bibfield  {journal} {\bibinfo  {journal} {{Quantum}}\ }\textbf {\bibinfo {volume} {4}},\ \bibinfo {pages} {287} (\bibinfo {year} {2020})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Layden}\ \emph {et~al.}(2023)\citenamefont {Layden}, \citenamefont {Mazzola}, \citenamefont {Mishmash}, \citenamefont {Motta}, \citenamefont {Wocjan}, \citenamefont {Kim},\ and\ \citenamefont {Sheldon}}]{layden2023quantum}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {David}\ \bibnamefont {Layden}}, \bibinfo {author} {\bibfnamefont {Guglielmo}\ \bibnamefont {Mazzola}}, \bibinfo {author} {\bibfnamefont {Ryan~V}\ \bibnamefont {Mishmash}}, \bibinfo {author} {\bibfnamefont {Mario}\ \bibnamefont {Motta}}, \bibinfo {author} {\bibfnamefont {Pawel}\ \bibnamefont {Wocjan}}, \bibinfo {author} {\bibfnamefont {Jin-Sung}\ \bibnamefont {Kim}}, \ and\ \bibinfo {author} {\bibfnamefont {Sarah}\ \bibnamefont {Sheldon}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {{Quantum-enhanced Markov chain Monte Carlo}},}\ }\href@noop {} {\bibfield  {journal} {\bibinfo  {journal} {Nature}\ }\textbf {\bibinfo {volume} {619}},\ \bibinfo {pages} {282--287} (\bibinfo {year} {2023})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Intallura}\ \emph {et~al.}(2023)\citenamefont {Intallura}, \citenamefont {Korpas}, \citenamefont {Chakraborty}, \citenamefont {Kungurtsev},\ and\ \citenamefont {Marecek}}]{intallura2023survey}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Philip}\ \bibnamefont {Intallura}}, \bibinfo {author} {\bibfnamefont {Georgios}\ \bibnamefont {Korpas}}, \bibinfo {author} {\bibfnamefont {Sudeepto}\ \bibnamefont {Chakraborty}}, \bibinfo {author} {\bibfnamefont {Vyacheslav}\ \bibnamefont {Kungurtsev}}, \ and\ \bibinfo {author} {\bibfnamefont {Jakub}\ \bibnamefont {Marecek}},\ }\href@noop {} {\enquote {\bibinfo {title} {A survey of quantum alternatives to randomized algorithms: Monte carlo integration and beyond},}\ } (\bibinfo {year} {2023}),\ \Eprint {http://arxiv.org/abs/2303.04945} {arXiv:2303.04945 [quant-ph]} \BibitemShut {NoStop}%
\bibitem [{\citenamefont {Durr}\ and\ \citenamefont {Hoyer}(1999)}]{durr1996quantum}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Christoph}\ \bibnamefont {Durr}}\ and\ \bibinfo {author} {\bibfnamefont {Peter}\ \bibnamefont {Hoyer}},\ }\href@noop {} {\enquote {\bibinfo {title} {A quantum algorithm for finding the minimum},}\ } (\bibinfo {year} {1999}),\ \Eprint {http://arxiv.org/abs/quant-ph/9607014} {arXiv:quant-ph/9607014 [quant-ph]} \BibitemShut {NoStop}%
\bibitem [{\citenamefont {Bulger}\ \emph {et~al.}(2003)\citenamefont {Bulger}, \citenamefont {Baritompa},\ and\ \citenamefont {Wood}}]{Bulger2003}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {D.}~\bibnamefont {Bulger}}, \bibinfo {author} {\bibfnamefont {W.~P.}\ \bibnamefont {Baritompa}}, \ and\ \bibinfo {author} {\bibfnamefont {G.~R.}\ \bibnamefont {Wood}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Implementing pure adaptive search with grover{\textquotesingle}s quantum algorithm},}\ }\href {\doibase 10.1023/a:1023061218864} {\bibfield  {journal} {\bibinfo  {journal} {Journal of Optimization Theory and Applications}\ }\textbf {\bibinfo {volume} {116}},\ \bibinfo {pages} {517--529} (\bibinfo {year} {2003})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Baritompa}\ \emph {et~al.}(2005)\citenamefont {Baritompa}, \citenamefont {Bulger},\ and\ \citenamefont {Wood}}]{Baritompa2005}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {W.~P.}\ \bibnamefont {Baritompa}}, \bibinfo {author} {\bibfnamefont {D.~W.}\ \bibnamefont {Bulger}}, \ and\ \bibinfo {author} {\bibfnamefont {G.~R.}\ \bibnamefont {Wood}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Grover{\textquotesingle}s quantum algorithm applied to global optimization},}\ }\href {\doibase 10.1137/040605072} {\bibfield  {journal} {\bibinfo  {journal} {{SIAM} Journal on Optimization}\ }\textbf {\bibinfo {volume} {15}},\ \bibinfo {pages} {1170--1184} (\bibinfo {year} {2005})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Motta}\ \emph {et~al.}(2019)\citenamefont {Motta}, \citenamefont {Sun}, \citenamefont {Tan}, \citenamefont {O'Rourke}, \citenamefont {Ye}, \citenamefont {Minnich}, \citenamefont {Brand{\~{a}}o},\ and\ \citenamefont {Chan}}]{Motta2019}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Mario}\ \bibnamefont {Motta}}, \bibinfo {author} {\bibfnamefont {Chong}\ \bibnamefont {Sun}}, \bibinfo {author} {\bibfnamefont {Adrian T.~K.}\ \bibnamefont {Tan}}, \bibinfo {author} {\bibfnamefont {Matthew~J.}\ \bibnamefont {O'Rourke}}, \bibinfo {author} {\bibfnamefont {Erika}\ \bibnamefont {Ye}}, \bibinfo {author} {\bibfnamefont {Austin~J.}\ \bibnamefont {Minnich}}, \bibinfo {author} {\bibfnamefont {Fernando G. S.~L.}\ \bibnamefont {Brand{\~{a}}o}}, \ and\ \bibinfo {author} {\bibfnamefont {Garnet Kin-Lic}\ \bibnamefont {Chan}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution},}\ }\href {\doibase 10.1038/s41567-019-0704-4} {\bibfield  {journal} {\bibinfo  {journal} {Nature Physics}\ }\textbf {\bibinfo {volume} {16}},\ \bibinfo {pages} {205--210} (\bibinfo {year} {2019})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Gilliam}\ \emph {et~al.}(2021)\citenamefont {Gilliam}, \citenamefont {Woerner},\ and\ \citenamefont {Gonciulea}}]{Gilliam_2021_grover}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Austin}\ \bibnamefont {Gilliam}}, \bibinfo {author} {\bibfnamefont {Stefan}\ \bibnamefont {Woerner}}, \ and\ \bibinfo {author} {\bibfnamefont {Constantin}\ \bibnamefont {Gonciulea}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Grover adaptive search for constrained polynomial binary optimization},}\ }\href {\doibase 10.22331/q-2021-04-08-428} {\bibfield  {journal} {\bibinfo  {journal} {Quantum}\ }\textbf {\bibinfo {volume} {5}},\ \bibinfo {pages} {428} (\bibinfo {year} {2021})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Bennett}\ \emph {et~al.}(1997{\natexlab{b}})\citenamefont {Bennett}, \citenamefont {Bernstein}, \citenamefont {Brassard},\ and\ \citenamefont {Vazirani}}]{Bennett1997strenghts}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Charles~H.}\ \bibnamefont {Bennett}}, \bibinfo {author} {\bibfnamefont {Ethan}\ \bibnamefont {Bernstein}}, \bibinfo {author} {\bibfnamefont {Gilles}\ \bibnamefont {Brassard}}, \ and\ \bibinfo {author} {\bibfnamefont {Umesh}\ \bibnamefont {Vazirani}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Strengths and weaknesses of quantum computing},}\ }\href {\doibase 10.1137/s0097539796300933} {\bibfield  {journal} {\bibinfo  {journal} {{SIAM} Journal on Computing}\ }\textbf {\bibinfo {volume} {26}},\ \bibinfo {pages} {1510--1523} (\bibinfo {year} {1997}{\natexlab{b}})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Cade}\ \emph {et~al.}(2023)\citenamefont {Cade}, \citenamefont {Folkertsma}, \citenamefont {Niesen},\ and\ \citenamefont {Weggemans}}]{cade2023quantifying}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Chris}\ \bibnamefont {Cade}}, \bibinfo {author} {\bibfnamefont {Marten}\ \bibnamefont {Folkertsma}}, \bibinfo {author} {\bibfnamefont {Ido}\ \bibnamefont {Niesen}}, \ and\ \bibinfo {author} {\bibfnamefont {Jordi}\ \bibnamefont {Weggemans}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Quantifying grover speed-ups beyond asymptotic analysis},}\ }\href@noop {} {\bibfield  {journal} {\bibinfo  {journal} {Quantum}\ }\textbf {\bibinfo {volume} {7}},\ \bibinfo {pages} {1133} (\bibinfo {year} {2023})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Shaydulin}\ \emph {et~al.}(2023)\citenamefont {Shaydulin}, \citenamefont {Li}, \citenamefont {Chakrabarti}, \citenamefont {DeCross}, \citenamefont {Herman}, \citenamefont {Kumar}, \citenamefont {Larson}, \citenamefont {Lykov}, \citenamefont {Minssen}, \citenamefont {Sun}, \citenamefont {Alexeev}, \citenamefont {Dreiling}, \citenamefont {Gaebler}, \citenamefont {Gatterman}, \citenamefont {Gerber}, \citenamefont {Gilmore}, \citenamefont {Gresh}, \citenamefont {Hewitt}, \citenamefont {Horst}, \citenamefont {Hu}, \citenamefont {Johansen}, \citenamefont {Matheny}, \citenamefont {Mengle}, \citenamefont {Mills}, \citenamefont {Moses}, \citenamefont {Neyenhuis}, \citenamefont {Siegfried}, \citenamefont {Yalovetzky},\ and\ \citenamefont {Pistoia}}]{shaydulin2023evidence}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Ruslan}\ \bibnamefont {Shaydulin}}, \bibinfo {author} {\bibfnamefont {Changhao}\ \bibnamefont {Li}}, \bibinfo {author} {\bibfnamefont {Shouvanik}\ \bibnamefont {Chakrabarti}}, \bibinfo {author} {\bibfnamefont {Matthew}\ \bibnamefont {DeCross}}, \bibinfo {author} {\bibfnamefont {Dylan}\ \bibnamefont {Herman}}, \bibinfo {author} {\bibfnamefont {Niraj}\ \bibnamefont {Kumar}}, \bibinfo {author} {\bibfnamefont {Jeffrey}\ \bibnamefont {Larson}}, \bibinfo {author} {\bibfnamefont {Danylo}\ \bibnamefont {Lykov}}, \bibinfo {author} {\bibfnamefont {Pierre}\ \bibnamefont {Minssen}}, \bibinfo {author} {\bibfnamefont {Yue}\ \bibnamefont {Sun}}, \bibinfo {author} {\bibfnamefont {Yuri}\ \bibnamefont {Alexeev}}, \bibinfo {author} {\bibfnamefont {Joan~M.}\ \bibnamefont {Dreiling}}, \bibinfo {author} {\bibfnamefont {John~P.}\ \bibnamefont {Gaebler}}, \bibinfo {author} {\bibfnamefont {Thomas~M.}\ \bibnamefont {Gatterman}}, \bibinfo {author} {\bibfnamefont {Justin~A.}\ \bibnamefont {Gerber}}, \bibinfo {author} {\bibfnamefont {Kevin}\ \bibnamefont {Gilmore}}, \bibinfo {author} {\bibfnamefont {Dan}\ \bibnamefont {Gresh}}, \bibinfo {author} {\bibfnamefont {Nathan}\ \bibnamefont {Hewitt}}, \bibinfo {author} {\bibfnamefont {Chandler~V.}\ \bibnamefont {Horst}}, \bibinfo {author} {\bibfnamefont {Shaohan}\ \bibnamefont {Hu}}, \bibinfo {author} {\bibfnamefont {Jacob}\ \bibnamefont {Johansen}}, \bibinfo {author} {\bibfnamefont {Mitchell}\ \bibnamefont {Matheny}}, \bibinfo {author} {\bibfnamefont {Tanner}\ \bibnamefont {Mengle}}, \bibinfo {author} {\bibfnamefont {Michael}\ \bibnamefont {Mills}}, \bibinfo {author} {\bibfnamefont {Steven~A.}\ \bibnamefont {Moses}}, \bibinfo {author} {\bibfnamefont {Brian}\ \bibnamefont {Neyenhuis}}, \bibinfo {author} {\bibfnamefont {Peter}\ \bibnamefont {Siegfried}}, \bibinfo {author} {\bibfnamefont {Romina}\ \bibnamefont {Yalovetzky}}, \ and\ \bibinfo {author} {\bibfnamefont {Marco}\ \bibnamefont {Pistoia}},\ }\href@noop {} {\enquote {\bibinfo {title} {Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem},}\ } (\bibinfo {year} {2023}),\ \Eprint {http://arxiv.org/abs/2308.02342} {arXiv:2308.02342 [quant-ph]} \BibitemShut {NoStop}%
\bibitem [{\citenamefont {Sommese}\ \emph {et~al.}(2005)\citenamefont {Sommese}, \citenamefont {Wampler} \emph {et~al.}}]{sommese2005numerical}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Andrew~J}\ \bibnamefont {Sommese}}, \bibinfo {author} {\bibfnamefont {Charles~W}\ \bibnamefont {Wampler}},  \emph {et~al.},\ }\href@noop {} {\emph {\bibinfo {title} {The Numerical solution of systems of polynomials arising in engineering and science}}}\ (\bibinfo  {publisher} {World Scientific},\ \bibinfo {year} {2005})\BibitemShut {NoStop}%
\bibitem [{\citenamefont {{Born}}\ and\ \citenamefont {{Fock}}(1928)}]{born1928adiabatic}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {M.}~\bibnamefont {{Born}}}\ and\ \bibinfo {author} {\bibfnamefont {V.}~\bibnamefont {{Fock}}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {{Beweis des Adiabatensatzes}},}\ }\href {\doibase 10.1007/BF01343193} {\bibfield  {journal} {\bibinfo  {journal} {Zeitschrift fur Physik}\ }\textbf {\bibinfo {volume} {51}},\ \bibinfo {pages} {165--180} (\bibinfo {year} {1928})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Finnila}\ \emph {et~al.}(1994)\citenamefont {Finnila}, \citenamefont {Gomez}, \citenamefont {Sebenik}, \citenamefont {Stenson},\ and\ \citenamefont {Doll}}]{FINNILA1994343}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {A.B.}\ \bibnamefont {Finnila}}, \bibinfo {author} {\bibfnamefont {M.A.}\ \bibnamefont {Gomez}}, \bibinfo {author} {\bibfnamefont {C.}~\bibnamefont {Sebenik}}, \bibinfo {author} {\bibfnamefont {C.}~\bibnamefont {Stenson}}, \ and\ \bibinfo {author} {\bibfnamefont {J.D.}\ \bibnamefont {Doll}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Quantum annealing: A new method for minimizing multidimensional functions},}\ }\href {\doibase https://doi.org/10.1016/0009-2614(94)00117-0} {\bibfield  {journal} {\bibinfo  {journal} {Chemical Physics Letters}\ }\textbf {\bibinfo {volume} {219}},\ \bibinfo {pages} {343--348} (\bibinfo {year} {1994})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Bapst}\ \emph {et~al.}(2013)\citenamefont {Bapst}, \citenamefont {Foini}, \citenamefont {Krzakala}, \citenamefont {Semerjian},\ and\ \citenamefont {Zamponi}}]{bapst2013quantum}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Victor}\ \bibnamefont {Bapst}}, \bibinfo {author} {\bibfnamefont {Laura}\ \bibnamefont {Foini}}, \bibinfo {author} {\bibfnamefont {Florent}\ \bibnamefont {Krzakala}}, \bibinfo {author} {\bibfnamefont {Guilhem}\ \bibnamefont {Semerjian}}, \ and\ \bibinfo {author} {\bibfnamefont {Francesco}\ \bibnamefont {Zamponi}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {The quantum adiabatic algorithm applied to random optimization problems: The quantum spin glass perspective},}\ }\href@noop {} {\bibfield  {journal} {\bibinfo  {journal} {Physics Reports}\ }\textbf {\bibinfo {volume} {523}},\ \bibinfo {pages} {127--205} (\bibinfo {year} {2013})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Knysh}(2016)}]{knysh2016zero}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Sergey}\ \bibnamefont {Knysh}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Zero-temperature quantum annealing bottlenecks in the spin-glass phase},}\ }\href@noop {} {\bibfield  {journal} {\bibinfo  {journal} {Nature communications}\ }\textbf {\bibinfo {volume} {7}},\ \bibinfo {pages} {12370} (\bibinfo {year} {2016})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Isakov}\ \emph {et~al.}(2016)\citenamefont {Isakov}, \citenamefont {Mazzola}, \citenamefont {Smelyanskiy}, \citenamefont {Jiang}, \citenamefont {Boixo}, \citenamefont {Neven},\ and\ \citenamefont {Troyer}}]{isakov2016understanding}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Sergei~V}\ \bibnamefont {Isakov}}, \bibinfo {author} {\bibfnamefont {Guglielmo}\ \bibnamefont {Mazzola}}, \bibinfo {author} {\bibfnamefont {Vadim~N}\ \bibnamefont {Smelyanskiy}}, \bibinfo {author} {\bibfnamefont {Zhang}\ \bibnamefont {Jiang}}, \bibinfo {author} {\bibfnamefont {Sergio}\ \bibnamefont {Boixo}}, \bibinfo {author} {\bibfnamefont {Hartmut}\ \bibnamefont {Neven}}, \ and\ \bibinfo {author} {\bibfnamefont {Matthias}\ \bibnamefont {Troyer}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Understanding quantum tunneling through quantum monte carlo simulations},}\ }\href@noop {} {\bibfield  {journal} {\bibinfo  {journal} {Physical review letters}\ }\textbf {\bibinfo {volume} {117}},\ \bibinfo {pages} {180402} (\bibinfo {year} {2016})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Mohseni}\ \emph {et~al.}(2023)\citenamefont {Mohseni}, \citenamefont {Navarrete-Benlloch}, \citenamefont {Byrnes},\ and\ \citenamefont {Marquardt}}]{mohseni2023deep}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Naeimeh}\ \bibnamefont {Mohseni}}, \bibinfo {author} {\bibfnamefont {Carlos}\ \bibnamefont {Navarrete-Benlloch}}, \bibinfo {author} {\bibfnamefont {Tim}\ \bibnamefont {Byrnes}}, \ and\ \bibinfo {author} {\bibfnamefont {Florian}\ \bibnamefont {Marquardt}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Deep recurrent networks predicting the gap evolution in adiabatic quantum computing},}\ }\href@noop {} {\bibfield  {journal} {\bibinfo  {journal} {Quantum}\ }\textbf {\bibinfo {volume} {7}},\ \bibinfo {pages} {1039} (\bibinfo {year} {2023})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Rønnow}\ \emph {et~al.}(2014)\citenamefont {Rønnow}, \citenamefont {Wang}, \citenamefont {Job}, \citenamefont {Boixo}, \citenamefont {Isakov}, \citenamefont {Wecker}, \citenamefont {Martinis}, \citenamefont {Lidar},\ and\ \citenamefont {Troyer}}]{ronnow2014defining}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Troels~F.}\ \bibnamefont {Rønnow}}, \bibinfo {author} {\bibfnamefont {Zhihui}\ \bibnamefont {Wang}}, \bibinfo {author} {\bibfnamefont {Joshua}\ \bibnamefont {Job}}, \bibinfo {author} {\bibfnamefont {Sergio}\ \bibnamefont {Boixo}}, \bibinfo {author} {\bibfnamefont {Sergei~V.}\ \bibnamefont {Isakov}}, \bibinfo {author} {\bibfnamefont {David}\ \bibnamefont {Wecker}}, \bibinfo {author} {\bibfnamefont {John~M.}\ \bibnamefont {Martinis}}, \bibinfo {author} {\bibfnamefont {Daniel~A.}\ \bibnamefont {Lidar}}, \ and\ \bibinfo {author} {\bibfnamefont {Matthias}\ \bibnamefont {Troyer}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Defining and detecting quantum speedup},}\ }\href {\doibase 10.1126/science.1252319} {\bibfield  {journal} {\bibinfo  {journal} {Science}\ }\textbf {\bibinfo {volume} {345}},\ \bibinfo {pages} {420--424} (\bibinfo {year} {2014})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Crosson}\ and\ \citenamefont {Lidar}(2021)}]{crosson2021prospects}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {EJ}~\bibnamefont {Crosson}}\ and\ \bibinfo {author} {\bibfnamefont {DA}~\bibnamefont {Lidar}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Prospects for quantum enhancement with diabatic quantum annealing},}\ }\href@noop {} {\bibfield  {journal} {\bibinfo  {journal} {Nature Reviews Physics}\ }\textbf {\bibinfo {volume} {3}},\ \bibinfo {pages} {466--489} (\bibinfo {year} {2021})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Demirplak}\ and\ \citenamefont {Rice}(2003)}]{Demirplak2003}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Mustafa}\ \bibnamefont {Demirplak}}\ and\ \bibinfo {author} {\bibfnamefont {Stuart~A.}\ \bibnamefont {Rice}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Adiabatic population transfer with control fields},}\ }\href {\doibase 10.1021/jp030708a} {\bibfield  {journal} {\bibinfo  {journal} {The Journal of Physical Chemistry A}\ }\textbf {\bibinfo {volume} {107}},\ \bibinfo {pages} {9937--9945} (\bibinfo {year} {2003})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {del Campo}(2013)}]{Campo2013}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Adolfo}\ \bibnamefont {del Campo}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Shortcuts to adiabaticity by counterdiabatic driving},}\ }\href {\doibase 10.1103/PhysRevLett.111.100502} {\bibfield  {journal} {\bibinfo  {journal} {Phys. Rev. Lett.}\ }\textbf {\bibinfo {volume} {111}},\ \bibinfo {pages} {100502} (\bibinfo {year} {2013})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Claeys}\ \emph {et~al.}(2019)\citenamefont {Claeys}, \citenamefont {Pandey}, \citenamefont {Sels},\ and\ \citenamefont {Polkovnikov}}]{Claeys2019}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Pieter~W.}\ \bibnamefont {Claeys}}, \bibinfo {author} {\bibfnamefont {Mohit}\ \bibnamefont {Pandey}}, \bibinfo {author} {\bibfnamefont {Dries}\ \bibnamefont {Sels}}, \ and\ \bibinfo {author} {\bibfnamefont {Anatoli}\ \bibnamefont {Polkovnikov}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Floquet-engineering counterdiabatic protocols in quantum many-body systems},}\ }\href {\doibase 10.1103/PhysRevLett.123.090602} {\bibfield  {journal} {\bibinfo  {journal} {Phys. Rev. Lett.}\ }\textbf {\bibinfo {volume} {123}},\ \bibinfo {pages} {090602} (\bibinfo {year} {2019})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Chasseur}\ \emph {et~al.}(2015)\citenamefont {Chasseur}, \citenamefont {Theis}, \citenamefont {Sanders}, \citenamefont {Egger},\ and\ \citenamefont {Wilhelm}}]{Chasseur2015}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {T.}~\bibnamefont {Chasseur}}, \bibinfo {author} {\bibfnamefont {L.~S.}\ \bibnamefont {Theis}}, \bibinfo {author} {\bibfnamefont {Y.~R.}\ \bibnamefont {Sanders}}, \bibinfo {author} {\bibfnamefont {D.~J.}\ \bibnamefont {Egger}}, \ and\ \bibinfo {author} {\bibfnamefont {F.~K.}\ \bibnamefont {Wilhelm}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Engineering adiabaticity at an avoided crossing with optimal control},}\ }\href {\doibase 10.1103/PhysRevA.91.043421} {\bibfield  {journal} {\bibinfo  {journal} {Phys. Rev. A}\ }\textbf {\bibinfo {volume} {91}},\ \bibinfo {pages} {043421} (\bibinfo {year} {2015})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {{Suzuki}}(1990)}]{Suzuki1990trotter}%
\BibitemOpen