# On the gate-error robustness of variational quantum algorithms

Daniil Rabinovich  Skolkovo Institute of Science and Technology, Moscow,
Russian Federation  Ernesto Campos  Skolkovo Institute of Science and
Technology, Moscow, Russian Federation  Soumik Adhikary  Skolkovo Institute of
Science and Technology, Moscow, Russian Federation  Ekaterina Pankovets
Skolkovo Institute of Science and Technology, Moscow, Russian Federation
Moscow Institute of Physics and Technology, Moscow, Russian Federation  Dmitry
Vinichenko  Skolkovo Institute of Science and Technology, Moscow, Russian
Federation  Moscow Engineering Physics Institute, Moscow, Russian Federation
Jacob Biamonte  Beijing Institute of Mathematical Sciences and Applications,
Beijing, China

###### Abstract

Variational quantum algorithms are tailored to perform within the constraints
of current quantum devices, yet they are limited by performance-degrading
errors. In this study, we consider a noise model that reflects realistic gate
errors inherent to variational quantum algorithms. We investigate the
decoherence of a variationally prepared quantum state due to this noise model,
which causes a deviation from the energy estimation in the variational
approach. By performing a perturbative analysis of optimized circuits, we
determine the noise threshold at which the criteria set by the stability lemma
is met. We assess our findings against the variational quantum approximate
optimization algorithm for $3$-SAT problem instances and unstructured search
with up to $10$ qubits and $30$ layers. Moreover, we show that certain gate
errors have a significantly smaller impact on the coherence of the state,
allowing us to reduce the execution time without compromising performance.

##  I Introduction

Noisy Intermediate Scale Quantum (NISQ) computing preskill2018  is constrained
by limited coherence times and operation precision weidenfeller2022scaling ;
ratcliffe2018scaling ; hegde2022toward ; mills2022two , which restrict the
number of qubits and circuit depths that can be implemented with reasonable
fidelity. This limits the range of possible experimental demonstrations. The
variational model of quantum computation is tailored to operate within these
practical limitations kandala2017hardware ; Rabinovich22 ; pagano2020 , and
has been shown to be computationally universal under idealized conditions
biamonte2021universal . Similar to machine learning, a variational algorithm
employs a parameterized quantum circuit, called an ansatz, that is iteratively
adjusted to minimize a cost function in a quantum-to-classical feedback loop
cerezo2021variational . The cost function usually takes the form of the
expectation of a problem Hamiltonian, where the ground state of the problem
Hamiltonian represents the solution to a given problem instance. By minimizing
the cost function (energy), a variational algorithm aims to approximate the
ground state of the Hamiltonian. However, this approach does not guarantee the
quality of the approximate solution, which is typically measured by the
overlap between the state prepared by the ansatz and the true ground state.
Nonetheless, the overlap can be bounded. Using the stability lemma
biamonte2021universal , it has been demonstrated that the bounds can be
directly linked to the energy, allowing us to determine the energy threshold
(upper bound) required to ensure a minimum (fixed) overlap. We refer to this
as the acceptance threshold, and a state with an energy below this threshold
is considered accepted by the algorithm.

Variational algorithms are designed to mitigate some of the systematic
limitations of NISQ devices Harrigan2021 ; pagano2020 ; Guerreschi2019 ;
Butko2020 . However, these algorithms are still susceptible to stochastic
noise. While there is some evidence that variational algorithms can benefit
from a certain level of stochastic noise Campos2021 , in general, noise
negatively impacts their performance by inducing decoherence and impacting
solution quality.

In this paper, we investigate how errors in the form of parameter deviations
impact the performance of variational algorithms when operated at their
noiseless optimal parameters. We analytically demonstrate that the energy
shift varies quadratically with the spread of parameter deviation, equivalent
to an energy shift linear with respect to the gate error probabilities for
various noise models Dalton2022 . We validate our findings using the quantum
approximate optimization algorithm on two common problems: $3$-SAT Akshay2020
and unstructured search akshay2021parameter ; grover1996fast . We also observe
that the performance of the algorithm is more resilient to alterations in
certain parameters. Based on these findings, we propose methods to potentially
enhance performance and reduce the execution time of variational quantum
algorithms.

##  II Preliminaries

###  II.1 Variational Quantum Approximate Optimization

The quantum approximate optimization algorithm (QAOA) farhi2014quantum ,
originally designed to approximately solve combinatorial optimization problems
niu2019optimizing ; farhi2014quantum ; lloyd2018quantum ;
morales2020universality ; Zhou2020 ; wang2020x ; Brady2021 ; Farhi2016 ;
Akshay2020 ; Farhi2019a ; Wauters2020 ; Claes2021 ; Zhou , consists of ansatze
circuits expressive enough to (in theory) emulate any quantum cirucuit
lloyd2018quantum ; morales2020universality .

Consider a pseudo-Boolean function $\mathcal{C}:\\{0,1\\}^{\times
n}\rightarrow\mathbb{R}$, the objective of the algorithm is to approximate a
bit string that minimizes $\mathcal{C}$. To accomplish this, $\mathcal{C}$ is
first encoded as a problem Hamiltonian $H$, diagonal in the computational
basis. The ground state of $H$ encodes the solution to the problem; in other
words QAOA searches for a solution $\ket{g}$ such that ${\langle
g|H|g\rangle}=\min H$.

The algorithm begins with an ansatz state
$\ket{\psi_{p}(\bm{\gamma},\bm{\beta})}$—prepared by a circuit of depth $p$ —
parameterized as:

$\ket{\psi_{p}(\bm{\gamma},\bm{\beta})}=\prod\limits_{k=1}^{p}e^{-i\beta_{k}H_{x}}e^{-i\gamma_{k}H}\ket{+}^{\otimes{n}},$
(1)

with real parameters $\gamma_{k}\in[0,2\pi)$, $\beta_{k}\in[0,\pi)$. Here
$H_{x}=\sum_{j=1}^{n}X_{j}$ is the standard one-body mixer Hamiltonian with
Pauli matrix $X_{j}$ applied to the $j$-th qubit. The cost function is given
by the expectation of the problem Hamiltonian with respect to the ansatz
state. The algorith minimizes this cost function to output:

$\displaystyle
E^{*}=\min_{\bm{\gamma},\bm{\beta}}\bra{\psi_{p}(\bm{\gamma},\bm{\beta})}H\ket{\psi_{p}(\bm{\gamma},\bm{\beta})}$
(2)
$\displaystyle{\bm{\gamma}}^{*},{\bm{\beta}}^{*}\in\arg\min_{\bm{\gamma},\bm{\beta}}\bra{\psi_{p}(\bm{\gamma},\bm{\beta})}H\ket{\psi_{p}(\bm{\gamma},\bm{\beta})}$
(3)

Here, $\ket{\psi_{p}({\bm{\gamma}}^{*},{\bm{\beta}}^{*})}$ is the approximate
ground state of $H$ and hence the approximate solution to $\mathcal{C}$.
Indeed, the quality of the approximation, quantified as the overlap between
the true solution and the approximate solution, is not known a priori from
(2). Nevertheless one can establish bounds on this quantity using the so
called stability lemma.

###  II.2 Stability lemma

The stability lemma states that if $\ket{g}$ is the true ground state of $H$
with energy $E_{g}$ and $\Delta$ is the spectral gap (the difference between
the ground state energy and the energy of the first excited state) the
following relation holds biamonte2021universal ; akshay22 :

$1-\frac{E^{*}-E_{g}}{\Delta}\leq|{\langle\psi_{p}({\bm{\gamma}}^{*},{\bm{\beta}}^{*})|g\rangle}|^{2}\leq
1-\frac{E^{*}-E_{g}}{E_{m}-E_{g}}$ (4)

where $E_{m}$ is the maximum eigenvalue of $H$. Thus to guarantee a non-
trivial overlap one must ensure that $E^{*}\leq E_{g}+\Delta$. We call the
latter the acceptance condition.

##  III Variational quantum algorithms in the presence of realistic gate
errors

Implementation of unitary operations depends significantly on the considered
hardware. However, typically the implementation makes use of electromagnetic
pulses, such as in superconducting quantum computers clarke08 ; gambetta17 ,
neutral atom based quantum computers Gerasimov2022 ; Morgado2021 , and trapped
ion based quantum computers pagano2020 ; Zhang2017 . Such pulses can change
the population of the energy levels that constitute a qubit or introduce
phases to the quantum amplitudes, thus controlling the state of the qubits.
Consequently, the main contribution to gate errors comes from variation in
pulse shaping, meaning that amplitude and timing of electromagnetic pulse can
stochasticaly vary. In certain experimental setups, such as ground state ion
qubits, where entangling operations are performed using the radial phonon
modes Egan2021 , the variability in pulse shaping is the main source of gate
errors.

Angles of rotation in a typical gate operation depend on time averaged
intensity $I(t)$ of the electromagnetic pulse; $\theta\propto\int I(t)dt$.
Thus, variations in the pulse shaping lead to stochastic deviations of the
angles of rotations from the desired values. In other words, if a circuit is
composed of the parameterised gates $\\{U_{k}(\theta_{k})\\}_{k=1}^{q}$;
${\theta_{k}\in[0,2\pi)}$ and one tries to prepare a state
$\ket{\psi(\bm{\theta})}=\prod_{k=1}^{q}U_{k}(\theta_{k})\ket{\psi_{0}}$, a
different state

$\ket{\psi(\bm{\theta}+\bm{\delta\theta})}=\prod\limits_{k=1}^{q}U(\theta_{k}+\delta\theta_{k})\ket{\psi_{0}},$
(5)

is prepared instead due to the presence of errors. Notice here that the
perturbation $\bm{\delta\theta}$ to the parameters is stochastic and is
sampled with a certain probability density $p(\bm{\delta\theta})$. This
implies that the prepared state can be described by an ensemble
$\\{\ket{\psi(\bm{\theta}+\bm{\delta\theta})},p(\bm{\delta\theta})\\}$, which
we can equivalently view as a density matrix

$\rho(\bm{\theta})=\int\limits_{\bm{\delta\theta}\in[-\pi,\pi]^{\times
q}}p(\bm{\delta\theta}){|\psi(\bm{\theta}+\bm{\delta\theta})\rangle\\!\langle\psi(\bm{\theta}+\bm{\delta\theta})|}d(\bm{\delta\theta}).$
(6)

Eq. (6) represents a noise model native to the variational paradigm of quantum
computing. For the rest of this paper we systematically study the effect of
this noise model on the performance of QAOA for instances of 3-SAT and the
unstructured search problem (see appendix A for more details on the considered
problems). In particular we study the energy perturbation around $E^{*}$ in
different scenarios subsequently recovering the strength of noise under which
the acceptance condition continues to be satisfied.

##  IV Results

###  IV.1 Perturbative analysis in presence of gate errors

Consider a problem Hamiltonian $H$ and a variational ansatz
$\ket{\psi(\bm{\theta})}=U_{1}(\theta_{1})\dots
U_{q}(\theta_{q})\ket{\psi_{0}}$ used to minimize $H$. Here the gates
$U_{k}(\theta_{k})$ have the form:

$U_{k}(\theta_{k})=e^{iA_{k}\theta_{k}},A_{k}^{2}=\mathbb{1},$ (7)

A typical example of such an ansatz is the checkerboard ansatz, with
M$\o{}$lmer-S$\o{}$rensen (MS) gates as the entangling two qubit gates.
Nevertheless, any quantum circuit can admit a decomposition in terms of
operations that satisfy (7); this adds generality to this assumption.

In the presence of gate errors the prepared quantum state decoheres as
$\ket{\psi(\bm{\theta})}\rightarrow\rho(\bm{\theta})$ as per (6). To obtain
the analytic form of $\rho(\bm{\theta})$ we first note that

$\displaystyle
U_{k}(\theta_{k}+\delta\theta_{k})=U_{k}(\theta_{k})U_{k}(\delta\theta_{k})=\cos\delta\theta_{k}U_{k}(\theta_{k})+\sin\delta\theta_{k}U_{k}\left(\theta_{k}+\frac{\pi}{2}\right).$

This follows directly from (7). Therefore we get:

$\displaystyle{|\psi(\bm{\theta}+\bm{\delta\theta})\rangle\\!\langle\psi(\bm{\theta}+\bm{\delta\theta})|}=\sum\limits_{k_{1},\dots,k_{q},m_{1},\dots,m_{q}=0}^{1}(\cos^{2}\delta\theta_{1}\tan^{k_{1}+m_{1}}\delta\theta_{1})\dots(\cos^{2}\delta\theta_{q}\tan^{k_{q}+m_{q}}\delta\theta_{q}){|\psi_{k_{1}\dots
k_{q}}\rangle\\!\langle\psi_{m_{1}\dots m_{q}}|},$ (8)

where

$\ket{\psi_{k_{1}\dots k_{q}}}=U_{1}(\theta_{1}+k_{1}\frac{\pi}{2})\dots
U_{q}(\theta_{q}+k_{q}\frac{\pi}{2})\ket{\psi_{0}}.$ (9)

Here we make three realistic assumptions—(a) perturbations to all the angles
are independent, (b) mean perturbation $\langle\delta\theta_{k}\rangle=0$ and
(c) the distribution $p(\delta\theta_{k})$ vanishes quickly outside the range
$(-\sigma_{k},\sigma_{k})$; that is, the error is localized on the scale
$\sigma_{k}\ll 1$. Note that even if assumption (b) does not hold, as long as
mean value $\langle\delta\theta_{k}\rangle$ is independent from the angle
$\theta_{k}$, one can always shift the parameters as
$\theta_{k}\to\theta_{k}-\langle\delta\theta_{k}\rangle$ to avoid non-zero
mean. Otherwise, terms linear in $\langle\delta\theta_{k}\rangle$ could
contribute to the energy perturbation Kattemolle2022 .

Substituting (8) in (6) we arrive at the expression:

$\rho(\bm{\theta})={|\psi(\bm{\theta})\rangle\\!\langle\psi(\bm{\theta})|}+\delta\rho,$
(10)

where

$\delta\rho\approx-\sum\limits_{k=1}^{q}a_{k}{|\psi(\bm{\theta})\rangle\\!\langle\psi(\bm{\theta})|}+\sum_{k=1}^{q}a_{k}{|\psi_{k}\rangle\\!\langle\psi_{k}|}+o(\sigma_{k}^{2}).$
(11)

Here $\ket{\psi_{k}}=\ket{\psi_{00...1...00}}$ with $1$ placed in the $k$-th
position, and

$a_{k}\equiv\langle\sin^{2}\delta\theta_{k}\rangle=\int\sin^{2}\delta\theta_{k}p(\delta\theta_{k})d(\delta\theta_{k})\sim\sigma_{k}^{2}.$
(12)

Notice that (11) can be viewed as the action of certain noisy channel, where
each of the gates is altered with probability $a_{k}\sim\sigma_{k}^{2}$. In
this sense, we call $a_{k}$’s gate error probabilities, though this treatment
is specific to the interpretation of the noisy channel.

Notice that the derivation above does not require $\bm{\theta}$ to be a
minimum of the noiseless cost function. Let us now assume that
$\bm{\theta}^{*}$ is a vector of parameters such that
$\ket{\psi(\bm{\theta}^{*})}$ approximates the ground state of $H$. The noise
induced energy perturbation around the optimal energy $E^{*}$ is given as:

$\displaystyle\delta E$ $\displaystyle={\rm
Tr}(\rho(\bm{\theta}^{*})H)-\bra{\psi(\bm{\theta}^{*})}H\ket{\psi(\bm{\theta}^{*})}$
$\displaystyle=\sum_{k}(\bra{\psi_{k}}H\ket{\psi_{k}}-E^{*})a_{k}\leq(E_{m}-E^{*})\sum_{k}a_{k},$
(13)

which demonstrates that energy perturbation depends linearly on the gate error
probabilities $a_{k}$ (quadratic in $\sigma_{k}$) Dalton2022 .

For the simplest case where each parameter is sampled from the same
distribution ($\sigma_{k}=\sigma$) we can roughly estimate:

$\delta E\leq q\sigma^{2}(E_{m}-E^{*}).$ (14)

Thus, requesting an energy threshold $E\leq E_{g}+\Delta$, we conclude that
for $\sigma\lesssim\sqrt{\dfrac{\Delta-(E^{*}-E_{g})}{q(E_{m}-E^{*})}}$ the
acceptance condition is still satisfied.

While our perturbative analysis holds for all variational algorithms, we
substantiate our findings numerically using QAOA. In particular we solve
instances of 3-SAT and unstructured search problems to study the behaviour of
energy perturbation around $E^{*}$ caused by the presence of gate errors.

####  IV.1.1 Constant perturbation

We begin with a simplified version of the noise model proposed in (6). We ran
QAOA for 100 uniformly generated 3-SAT instances of 6,8, and 10 variables with
26, 34 and 42 clauses respectively. All the instances were selected to have a
unique satisfying assignment. The instances were minimized by QAOA sequences
of 15, 25 and 30 layers respectively in order to obtain expected values well
below the energy gap. In order to numerically verify the behaviour of the
energy perturbation, we vary all optimal parameters by a constant angle
$\delta$. Figure 1 illustrates the shift in the energy for the minimized
instances, which can be seen to have a quadratic dependence of the perturbed
energy $\delta E$ with respect to the shift $\delta$. This is natural to
expect since the parameters deviate from the local minimum, where linear
contribution must have vanished (a rigorous expression showing the quadratic
behavior is derived in appendix B).

Similar to the case of 3-SAT, for the problem of unstructured search we
perturb optimal parameters of the circuit by an angle $\delta$ and plot
corresponding energy in Fig. 2. Again, as expected, for small values of
$\delta$ the energy perturbation is quadratic which comes from the fact that
the deviation happens around the minimum.

Figure 1: Energy shift obtained by perturbing the ansatz state as
$\ket{\psi_{p}(\bm{\gamma}^{*}+\delta,\bm{\beta}^{*}+\delta)}$. The curves
illustrate averages over 100 uniformly generated 3-SAT instances of 6, 8 and
10 qubits with clause to variable ratio of 4.2 and unique satisfying
assignment. The error bars depict standard error. Polynomial fits of data in
range $\delta\in[0,0.02]$ indicates quadratic behaviour. Figure 2: Energy
shift for the problem of unstructured search obtained by perturbing of the
ansatz state as
$\ket{\psi_{p}(\bm{\gamma}^{*}+\delta,\bm{\beta}^{*}+\delta)}$. Polynomial
fits for data points of 6, 8 and 10 qubits follow quadratic curves in the
ranges $\delta\in[0,0.02],~{}[0,0.01],~{}[0,0.008]$ respectively.

####  IV.1.2 Stochastic perturbation

We now consider the complete noise model in (6) and verify our analytical
prediction as shown in (14). For each 3-SAT instance, we randomly sample
perturbations $\delta$ to each of the gates from a uniform distribution on the
interval $(-\sigma,\sigma)$ and average the obtained energy. Then we average
energies over instances of the same number of qubits as depicted in Fig. 3. It
is seen that for small values of noise the energy scales as $\delta
E\propto\sigma^{2}$, as per (14), which is equivalent to linear dependence on
the gate error probabilities $a_{k}$. It is seen, that the value $\sigma\sim
0.075$ could never violate the acceptance criteria, as corresponding energy
error never exceeds the gap $\Delta\geq 1$. For smaller number of qubits and
gates the threshold value of $\sigma$ increases.

Figure 3: Average energy shift of 100 uniformly generated 3-SAT instances of
6, 8 and 10 qubits with clause to variable ratio of 4.2 and unique satisfying
assignment. The shifts are obtained by the perturbation of
$\bm{\gamma}^{*},~{}\bm{\beta}^{*}$ by $\delta$ uniformly sampled from the
range $(-\sigma,\sigma)$. Error bars depict standard error. Polynomial fits of
data indicate that in the range $\sigma\in[0,0.1]$ $\delta
E\propto\sigma^{2}$. Figure 4: Average energy for the problem of unstructured
search obtained by the perturbation of $\bm{\gamma}^{*},~{}\bm{\beta}^{*}$ by
$\delta$ uniformly sampled from the range $(-\sigma,\sigma)$. Error bars
depict standard error. Polynomial fits of data points of 6, 8 and 10 qubits in
the ranges $\sigma\in[0,0.1],~{}[0,0.07],~{}[0,0.05]$, respectively confirm
that $\delta E\propto\sigma^{2}$.

For unstructured search, we average the energy over $\delta$ sampled for each
gate from the uniform distribution $(-\sigma,\sigma)$. We again recover that
$\delta E\propto\sigma^{2}$, as depicted in Fig. 4. It is seen that the same
threshold $\sigma\sim 0.075$ now increases energy by no more then $0.6$, which
guaranties $40\%$ overlap with the target state.

###  IV.2 Perturbation to individual parameters

Here we consider a modified version of (6), where parameters are perturbed one
at a time while the rest are kept intact. Effect of this model on the energy
is illustrated in Figures 5 and 6 for $n=10$ qubits. Similar results were also
obtained for $n=6$ and $n=8$ qubits. The results are numerical and are yet to
be explained analytically. We observe that perturbations to certain angles
have a significantly smaller effect on the energy. Thus we can infer that
reducing the values of such angles would not have a significant effect on
performance but will reduce the execution time of the circuit, that is
$t_{exec}=\sum_{k=1}^{p}\beta_{k}+\gamma_{k}$. Alternatively, increasing depth
to $p+1$ while limiting the maximum execution time to that of the original
circuit, $t_{exec}^{p+1}\leq t^{p+1}_{max}=t^{p}_{exec}$, one can potentially
improve performance.

Figure 5: Energy $\langle
H\rangle=\bra{\psi(\bm{\theta}^{*}+\bm{\delta}\bm{\theta})}H\ket{\psi(\bm{\theta}^{*}+\bm{\delta}\bm{\theta})}$
obtained for the unstructured search on $n=10$ qubits with $p=25$ layers, when
only $\beta_{k}$ (top) and $\gamma_{k}$ (bottom) are perturbed.

Figure 6: Average energy $\langle
H\rangle=\bra{\psi(\bm{\theta}^{*}+\bm{\delta}\bm{\theta})}H\ket{\psi(\bm{\theta}^{*}+\bm{\delta}\bm{\theta})}$
of 100 uniformly generated 3-SAT instances solved with $p=30$ layers, where
$\beta_{k}$ (top) or $\gamma_{k}$ (bottom), from the $k$-th layer, are
perturbed. The instances are of 10 qubits with clause to variable ratio of 4.2
and unique satisfying assignment. Figure 7: Expected value for multiple
combinations of depth for maximum execution times. Green and orange rectangles
depict the two branches of angles that minimize expectation value for a given
depth.

Reducing the execution time is important to quantum algorithms, since
variational parameters are proportional to the time required to execute the
gates experimentally. NISQ era devices suffer from limited coherence, thus
reducing execution times can lead to more efficient hardware utilization
yang2017optimizing ; ibrahim2022pulse . We test these ideas in the setting of
unstructured search, as depicted in Fig. 7. Here we demonstrate the optimized
QAOA energies for 6 qubits at multiple depths with execution time limited to
$t_{max}$. The highlighted green and orange rectangles correspond to the two
groups of optimal angles that minimize the energy at each depth, as presented
in akshay2021parameter . Green rectangles also indicate the depth and
$t_{exec}$ at which the ansatz will not be able to decrease its energy by
either increasing depth or $t_{max}$. Following the observations of Fig. 5, by
slightly reducing $t_{max}$ the optimizer may reduce the parameters to which
the energy is less sensitive. This results in a slight energy increase as
illustrated in Fig. 7 where to the left of the green rectangles we can observe
darkening gradients.

By contrast, orange rectangles highlight longer execution times corresponding
to different sets of angles that also minimize the energy for a given number
of layers. Therefore, if the optimization routine finds the solution
corresponding to the orange rectangle, setting $t_{max}$ to be slightly less
than the $t_{exec}$ of the orange rectangle will lead the optimizer to find
angles corresponding to the green rectangle. This will amount to a
considerable reduction in execution time. Alternatively, increasing the number
of layers while keeping $t_{max}$ constant may reduce the energy.

In general, for an arbitrary problem Hamiltonian one can not be sure if
optimization has returned the ideal set of angles (green ones in our example).
For this reason, one might employ several strategies based on Fig. 7 to
achieve a minimum threshold energy. These include—to reduce $t_{max}$ until
energy starts degrading or increase depth with fixed $t_{max}$ until
performance stagnates.

##  V Discussion

In this study, we considered a noise model where variational gate parameters
are stochastically perturbed, and we demonstrated how this perturbation
affects the optimised energy $E^{*}$. Through a perturbative analysis, we
found that the change in energy $\delta E$ due to the presence of the gate
errors behaves quadratically with respect to the spread of parameter
deviations, which is equivalent to linear dependence on the gate error
probabilities. Using this result, we derived upper bounds on the amount of
perturbation that can be tolerated while still satisfying the acceptance
condition and achieving a fixed overlap between the target state and the state
prepared by the noisy variational circuit.

Our analytical findings are confirmed by numerical simulations of the quantum
approximate optimisation algorithm (QAOA) for two common problems - 3-SAT and
unstructured search - using different modifications of the considered noise
model. Our numerical results further showed that the algorithmic performance
is more resilient to perturbations of certain variational parameters. Based on
this observation, we proposed a strategy to improve performance and reduce the
execution time of variational quantum algorithms. Specifically, we showed that
the performance of QAOA (with execution time $t_{exec}$) is not affected when
limiting the maximum execution time to $t_{max}=t_{exec}-\epsilon$ for
$\epsilon\ll t_{exec}$. We also demonstrated that in some cases reducing
$t_{max}$ can lead to significant reductions in $t_{exec}$, while increasing
the depth of the algorithm can lead to an energy reduction while fixing
$t_{exec}$.

Whereas our study primarily focused on energy perturbations around the
noiseless optimum $\bm{\theta}^{*}$, in practice, one has to train the
algorithm in the presence of noise, which can change the optimal angles
$\bm{\theta}^{*}$ to $\bm{\theta}^{*}+\bm{\delta\theta}^{*}$, where the shift
$\bm{\delta\theta}^{*}$ increases with the strength of the noise. However,
using perturbation theory around the noiseless optimum, one can estimate
$\bm{\delta\theta}^{*}=O(\sigma^{2})$ in the regime of weak noise, and the
corresponding change in the energy is ${\rm
Tr}(\rho(\bm{\theta}^{*}+\bm{\delta\theta}^{*})H)-{\rm
Tr}(\rho(\bm{\theta}^{*})H)=O(\sigma^{4})$. Therefore, in the regime of weak
noise, one can safely use the noiseless optimum $\bm{\theta}^{*}$. For
detailed calculations, please refer to appendix C.

## Acknowledgement

D.R., E.C., S.A., E.P., D.V. acknowledge support from the research project,
Leading Research Center on Quantum Computing (agreement No. 014/20).

## References

  * [1] John Preskill.  Quantum computing in the nisq era and beyond.  Quantum, 2:79, 2018.
  * [2] Johannes Weidenfeller, Lucia C Valor, Julien Gacon, Caroline Tornow, Luciano Bello, Stefan Woerner, and Daniel J Egger.  Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware.  arXiv preprint arXiv:2202.03459, 2022.
  * [3] Alexander K Ratcliffe, Richard L Taylor, Joseph J Hope, and André RR Carvalho.  Scaling trapped ion quantum computers using fast gates and microtraps.  Physical Review Letters, 120(22):220501, 2018.
  * [4] Swathi S Hegde, Jingfu Zhang, and Dieter Suter.  Toward the speed limit of high-fidelity two-qubit gates.  Physical Review Letters, 128(23):230502, 2022.
  * [5] Adam R Mills, Charles R Guinn, Michael J Gullans, Anthony J Sigillito, Mayer M Feldman, Erik Nielsen, and Jason R Petta.  Two-qubit silicon quantum processor with operation fidelity exceeding 99%.  Science Advances, 8(14):eabn5130, 2022.
  * [6] Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M Chow, and Jay M Gambetta.  Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets.  Nature, 549(7671):242–246, 2017.
  * [7] Daniil Rabinovich, Soumik Adhikary, Ernesto Campos, Vishwanathan Akshay, Evgeny Anikin, Richik Sengupta, Olga Lakhmanskaya, Kirill Lakhmanskiy, and Jacob Biamonte.  Ion-native variational ansatz for quantum approximate optimization.  Phys. Rev. A, 106:032418, Sep 2022.
  * [8] Guido Pagano, Aniruddha Bapat, Patrick Becker, Katherine S Collins, Arinjoy De, Paul W Hess, Harvey B Kaplan, Antonis Kyprianidis, Wen Lin Tan, Christopher Baldwin, et al.  Quantum approximate optimization of the long-range ising model with a trapped-ion quantum simulator.  Proceedings of the National Academy of Sciences, 117(41):25396–25401, 2020.
  * [9] Jacob Biamonte.  Universal variational quantum computation.  Physical Review A, 103(3):L030401, 2021.
  * [10] Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, et al.  Variational quantum algorithms.  Nature Reviews Physics, 3(9):625–644, 2021.
  * [11] Matthew P Harrigan, Kevin J Sung, Matthew Neeley, Kevin J Satzinger, Frank Arute, Kunal Arya, Juan Atalaya, Joseph C Bardin, Rami Barends, Sergio Boixo, et al.  Quantum approximate optimization of non-planar graph problems on a planar superconducting processor.  Nature Physics, 17(3):332–336, 2021.
  * [12] Gian Giacomo Guerreschi and Anne Y Matsuura.  Qaoa for max-cut requires hundreds of qubits for quantum speed-up.  Scientific reports, 9(1):1–7, 2019.
  * [13] Anastasiia Butko, George Michelogiannakis, Samuel Williams, Costin Iancu, David Donofrio, John Shalf, Jonathan Carter, and Irfan Siddiqi.  Understanding quantum control processor capabilities and limitations through circuit characterization.  In 2020 International Conference on Rebooting Computing (ICRC), pages 66–75, 2020.
  * [14] E Campos, D Rabinovich, V Akshay, and J Biamonte.  Training saturation in layerwise quantum approximate optimisation.  (Letter) Physical Review A, 104:L030401, 2021.
  * [15] Kieran Dalton, Christopher K. Long, Yordan S. Yordanov, Charles G. Smith, Crispin H. W. Barnes, Normann Mertig, and David R. M. Arvidsson-Shukur.  Variational quantum chemistry requires gate-error probabilities below the fault-tolerance threshold, 2022.
  * [16] V. Akshay, H. Philathong, M. E.S. Morales, and J. D. Biamonte.  Reachability Deficits in Quantum Approximate Optimization.  Physical Review Letters, 124(9):090504, Mar 2020.
  * [17] Vishwanathan Akshay, Daniil Rabinovich, Ernesto Campos, and Jacob Biamonte.  Parameter concentrations in quantum approximate optimization.  Physical Review A, 104(1):L010401, 2021.
  * [18] Lov K Grover.  A fast quantum mechanical algorithm for database search.  In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212–219, 1996.
  * [19] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann.  A quantum approximate optimization algorithm.  arXiv preprint arXiv:1411.4028, 2014.
  * [20] Murphy Yuezhen Niu, Sirui Lu, and Isaac L Chuang.  Optimizing qaoa: Success probability and runtime dependence on circuit depth.  arXiv preprint arXiv:1905.12134, May 2019.
  * [21] Seth Lloyd.  Quantum approximate optimization is computationally universal.  arXiv preprint arXiv:1812.11075, 2018.
  * [22] Mauro ES Morales, Jacob D Biamonte, and Zoltán Zimborás.  On the universality of the quantum approximate optimization algorithm.  Quantum Information Processing, 19(9):1–26, 2020.
  * [23] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D. Lukin.  Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices.  Phys. Rev. X, 10:021067, Jun 2020.
  * [24] Zhihui Wang, Nicholas C Rubin, Jason M Dominy, and Eleanor G Rieffel.  X y mixers: Analytical and numerical results for the quantum alternating operator ansatz.  Physical Review A, 101(1):012320, 2020.
  * [25] Lucas T. Brady, Christopher L. Baldwin, Aniruddha Bapat, Yaroslav Kharkov, and Alexey V. Gorshkov.  Optimal Protocols in Quantum Annealing and Quantum Approximate Optimization Algorithm Problems.  Physical Review Letters, 126(7):070505, Feb 2021.
  * [26] Edward Farhi and Aram W Harrow.  Quantum supremacy through the quantum approximate optimization algorithm.  arXiv preprint arXiv:1602.07674, 2016.
  * [27] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Leo Zhou.  The quantum approximate optimization algorithm and the sherrington-kirkpatrick model at infinite size.  arXiv preprint arXiv:1910.08187, Oct 2019.
  * [28] Matteo M Wauters, Glen Bigan Mbeng, and Giuseppe E Santoro.  Polynomial scaling of qaoa for ground-state preparation of the fully-connected p-spin ferromagnet.  arXiv preprint arXiv:2003.07419, 2020.
  * [29] Jahan Claes and Wim van Dam.  Instance independence of single layer quantum approximate optimization algorithm on mixed-spin models at infinite size.  arXiv preprint arXiv:2102.12043, 2021.
  * [30] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D. Lukin.  Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices.  Phys. Rev. X, 10:021067, Jun 2020.
  * [31] Vishwanathan Akshay, H Philathong, E Campos, Daniil Rabinovich, Igor Zacharov, Xiao-Ming Zhang, and J Biamonte.  On circuit depth scaling for quantum approximate optimization.  arXiv preprint arXiv:2205.01698, 2022.
  * [32] John Clarke and Frank K Wilhelm.  Superconducting quantum bits.  Nature, 453(7198):1031–1042, 2008.
  * [33] Jay M Gambetta, Jerry M Chow, and Matthias Steffen.  Building logical qubits in a superconducting quantum computing system.  npj quantum information, 3(1):1–7, 2017.
  * [34] L. V. Gerasimov, R. R. Yusupov, A. D. Moiseevsky, I. Vybornyi, K. S. Tikhonov, S. P. Kulik, S. S. Straupe, C. I. Sukenik, and D. V. Kupriyanov.  Coupled dynamics of spin qubits in optical dipole microtraps.  2022\.
  * [35] M. Morgado and S. Whitlock.  Quantum simulation and computing with rydberg-interacting qubits.  AVS Quantum Science, 3(2):023501, 2021.
  * [36] J. Zhang, G. Pagano, P. W. Hess, A. Kyprianidis, P. Becker, H. Kaplan, A. V. Gorshkov, Z.-X. Gong, and C. Monroe.  Observation of a many-body dynamical phase transition with a 53-qubit quantum simulator.  Nature, 551(7682):601–604, 2017.
  * [37] Laird Nicholas Egan.  Scaling Quantum Computers with Long Chains of Trapped Ions.  PhD thesis, University of Maryland, College Park, 2021.
  * [38] Joris Kattemölle and Guido Burkard.  Effects of correlated errors on the quantum approximate optimization algorithm, 2022.
  * [39] Zhi-Cheng Yang, Armin Rahmani, Alireza Shabani, Hartmut Neven, and Claudio Chamon.  Optimizing variational quantum algorithms using pontryagin’s minimum principle.  Physical Review X, 7(2):021027, 2017.
  * [40] Mohannad Ibrahim, Hamed Mohammadbagherpoor, Cynthia Rios, Nicholas T Bronn, and Gregory T Byrd.  Pulse-level optimization of parameterized quantum circuits for variational quantum algorithms.  arXiv preprint arXiv:2211.00350, 2022.

$\bullet$

##  Appendix A 3-SAT and unstructured search problems

###  A.1 3-SAT

Boolean satifyability, or SAT, is the problem of determining weather a boolean
formula written in conjunctive normal form (CNF) is satisfiable. It is
possible to map any SAT instance via Karp reduction into $3$-SAT, which are
restricted to $3$ literals per clause. In order to approximate solutions to
SAT we embed the instance into a Hamiltonian as

$H_{\text{SAT}}=\sum_{j}P(j),$ (15)

where $j$ indexes clauses of an instance, and $P(j)$ is the tensor product of
projectors that penalizes bit string assignments that do not satisfy the
$j$-th clause.

###  A.2 Unstructured search

Consider an unstructured database $S$ indexed by $j\in\\{0,1\\}^{\times n}$.
Let $f:\\{0,1\\}^{\times n}\rightarrow\\{0,1\\}$ be a Boolean function (a.k.a.
black box) such that:

$f(j)=\begin{cases}1&\text{iff}~{}j=t\\\ 0&otherwise.\end{cases}$ (16)

The task is to find $t\in\\{0,1\\}^{\times n}$. The corresponding problem
Hamiltonian for QAOA is

$H_{t}=\mathbb{1}-{|t\rangle\\!\langle t|},$ (17)

thus the expected value is given by

$\langle H\rangle=1-|{\langle
t|\psi_{p}(\bm{\gamma},\bm{\beta})\rangle}|^{2}.$ (18)

QAOA performance for unstructured search is not sensitive to the particular
target state $\ket{t}$ in the computational basis. For any target state
$\ket{t}$ representing a binary string, there is a $U=U^{\dagger}$ composed of
$X$ and $\mathbb{1}$ operators such that $U\ket{0}^{\otimes n}=\ket{t}$. The
overlap of an arbitrary state prepared by a QAOA sequence with $\ket{t}$ is
then:

$\displaystyle{\langle t|\psi_{p}(\bm{\gamma},\bm{\beta})\rangle}$
$\displaystyle=\bra{t}\prod\limits_{k=1}^{p}e^{-i\beta_{k}\mathcal{H}_{x}}e^{-i\gamma_{k}{|\bm{t}\rangle\\!\langle\bm{t}|}}\ket{+}^{\otimes{n}}$
$\displaystyle=\bra{0}^{\otimes
n}U\prod\limits_{k=1}^{p}e^{-i\beta_{k}\mathcal{H}_{x}}e^{-i\gamma_{k}U({|0\rangle\\!\langle
0|})^{\otimes n}U}\ket{+}^{\otimes{n}}$ $\displaystyle=\bra{0}^{\otimes
n}U\prod\limits_{k=1}^{p}e^{-i\beta_{k}\mathcal{H}_{x}}Ue^{-i\gamma_{k}({|0\rangle\\!\langle
0|})^{\otimes n}}U\ket{+}^{\otimes{n}}$ $\displaystyle=\bra{0}^{\otimes
n}\prod\limits_{k=1}^{p}e^{-i\beta_{k}\mathcal{H}_{x}}e^{-i\gamma_{k}({|0\rangle\\!\langle
0|})^{\otimes n}}\ket{+}^{\otimes{n}},$

which is independent on $t$.

##  Appendix B Energy variation in presence of constant perturbations to gate
parameters

Using (8) one can calculate perturbation to the energy caused by a shift of
the optimal angles by a constant $\bm{\delta}\bm{\theta}$ as

$\displaystyle\delta E$
$\displaystyle=\bra{\psi(\bm{\theta}^{*}+\bm{\delta}\bm{\theta})}H\ket{\psi(\bm{\theta}^{*}+\bm{\delta}\bm{\theta})}-\bra{\psi(\bm{\theta}^{*})}H\ket{\psi(\bm{\theta}^{*})}$
$\displaystyle=-\sum_{k=1}^{q}\delta\theta_{k}^{2}E^{*}+\sum_{m\neq
k}^{q}\delta\theta_{k}\delta\theta_{m}(\bra{\psi(\bm{\theta}^{*})}H\ket{\psi_{km}}+h.c.)$
$\displaystyle~{}~{}~{}~{}+\sum_{m,k}^{q}\delta\theta_{k}\delta\theta_{k}\bra{\psi_{m}}H\ket{\psi_{k}}+o(\delta\theta_{k}\delta\theta_{m})$
$\displaystyle=\dfrac{1}{2}(\bm{\delta\theta})^{T}\bm{H}\bm{\delta\theta}+o(\delta\theta_{k}\delta\theta_{m}),$
(19)

where $\ket{\psi_{mk}}=\ket{\psi_{0...1...1...0}}$ with $1$ placed only at
$m$-th and $k$-th positions. $\bm{H}$ is the Hessian of the energy at
noiseless optimum,
$\bm{H}_{ij}=\dfrac{\partial^{2}}{\partial\theta_{i}\partial\theta_{j}}\bra{\psi(\bm{\theta})}H\ket{\psi(\bm{\theta})}|_{\bm{\theta}=\bm{\theta}^{*}}$.
Here we use the fact that at the optimal position linear contribution to the
cost function necessarily vanishes. It is seen now that for the constant
perturbation $\delta\theta_{k}=\delta$ the energy changes as $\delta
E\propto\delta^{2}$.

##  Appendix C Optimal parameters variation in the presence of noise

Let us use expressions (10) and (11) to estimate change in the energy if one
accounts for shift of optimal parameters
$\bm{\theta}^{*}\to\bm{\theta}^{*}+\bm{\delta\theta}^{*}$:

$\displaystyle{\rm Tr}(\rho(\bm{\theta}^{*}+\bm{\delta\theta}^{*})H)=$
$\displaystyle~{}~{}~{}(1-\sum_{k=1}^{q}a_{k})\bra{\psi(\bm{\theta}^{*}+\bm{\delta\theta}^{*})}H\ket{\psi(\bm{\theta}^{*}+\bm{\delta\theta}^{*})}$
$\displaystyle+\sum_{k=1}^{q}a_{k}\bra{\psi_{k}(\bm{\theta}^{*}+\bm{\delta\theta}^{*})}H\ket{\psi_{k}(\bm{\theta}^{*}+\bm{\delta\theta}^{*})}+o(\sigma_{k}^{2})$
(20)

We introduce gradients of the noisy terms
$\bm{B}^{k}=\dfrac{\partial}{\partial\bm{\theta}}\bra{\psi_{k}(\bm{\theta})}H\ket{\psi_{k}(\bm{\theta})}|_{\bm{\theta}=\bm{\theta}^{*}}$.
Notice that gradients of the noiseless function
$\bra{\psi(\bm{\theta})}H\ket{\psi(\bm{\theta})}$ vanish at optimum. Then,

$\displaystyle{\rm
Tr}(\rho(\bm{\theta}^{*}+\bm{\delta\theta}^{*})H)\approx(1-\sum_{k=1}^{q}a_{k})E^{*}+\dfrac{1}{2}(\bm{\delta\theta}^{*})^{T}\bm{H}\bm{\delta\theta}^{*}$
$\displaystyle+\sum_{k=1}^{q}a_{k}[\bra{\psi_{k}(\bm{\theta}^{*})}H\ket{\psi_{k}(\bm{\theta}^{*})}+(\bm{\delta\theta}^{*})^{T}\bm{B}^{k}].$
(21)

Minimizing it with respect to $\bm{\delta\theta}^{*}$ one gets
$\bm{\delta\theta}^{*}=\sum_{k=1}^{q}a_{k}\bm{H}^{-1}\bm{B}^{k}$. Thus, if we
account for the change of optimal parameters in the presence of noise, the
energy shifts by

$\displaystyle{\rm Tr}(\rho(\bm{\theta}^{*}+\bm{\delta\theta}^{*})H)-{\rm
Tr}(\rho(\bm{\theta}^{*})H)\approx$
$\displaystyle(\bm{\delta\theta}^{*})^{T}\bm{H}\bm{\delta\theta}^{*}+\sum_{k=1}^{q}a_{k}(\bm{\delta\theta}^{*})^{T}\bm{B}^{k}=O(\sigma^{4}).$
(22)