††thanks: Data and source code available upon reasonable request.

# Ion native variational ansatz for quantum approximate optimization

Daniil Rabinovich  Skolkovo Institute of Science and Technology, Moscow,
Russian Federation  Soumik Adhikary  Skolkovo Institute of Science and
Technology, Moscow, Russian Federation  Ernesto Campos  Skolkovo Institute of
Science and Technology, Moscow, Russian Federation  Vishwanathan Akshay
Skolkovo Institute of Science and Technology, Moscow, Russian Federation
Evgeny Anikin  The Russian Quantum Center, Moscow, Russian Federation  Richik
Sengupta  Skolkovo Institute of Science and Technology, Moscow, Russian
Federation  Olga Lakhmanskaya  The Russian Quantum Center, Moscow, Russian
Federation  Kiril Lakhmanskiy  The Russian Quantum Center, Moscow, Russian
Federation  Jacob Biamonte  Skolkovo Institute of Science and Technology,
Moscow, Russian Federation http://quantum.skoltech.ru

###### Abstract

Variational quantum algorithms involve training parameterized quantum circuits
using a classical co-processor. An important variational algorithm, designed
for combinatorial optimization, is the quantum approximate optimization
algorithm. Realization of this algorithm on any modern quantum processor
requires either embedding a problem instance into a Hamiltonian or emulating
the corresponding propagator by a gate sequence. For a vast range of problem
instances this is impossible due to current circuit depth and hardware
limitations. Hence we adapt the variational approach—using ion native
Hamiltonians—to create ansatze families that can prepare the ground states of
more general problem Hamiltonians. We analytically determine symmetry
protected classes that make certain problem instances inaccessible unless this
symmetry is broken. We exhaustively search over six qubits and consider upto
twenty circuit layers, demonstrating that symmetry can be broken to solve all
problem instances of the Sherrington-Kirkpatrick Hamiltonian. Going further,
we numerically demonstrate training convergence and level-wise improvement for
up to twenty qubits. Specifically these findings widen the class problem
instances which might be solved by ion based quantum processors. Generally
these results serve as a test-bed for quantum approximate optimization
approaches based on system native Hamiltonians and symmetry protection.

Modern quantum processors face noise and other imperfections that serve to
limit realizable circuit depth. Today’s quantum processors allow realization
of a short circuit with fixed error tolerance and tunable gates. This prompted
many researchers to envision such quantum circuits as a new type of machine
learning model [1, 2, 3, 4] leading to variational quantum algorithms (VQA).
In practice, open questions surround the expressability and trainability of
low-depth circuits.

A typical example of VQA, a so called Quantum Approximate Optimization
Algorithm (QAOA), requires an alternating sequencing of two propagators to
form approximate solutions of combinatorial optimization problems [5]. In such
a setting, one of the propagators embeds the optimization problem as a
diagonal unitary. With long enough circuits, QAOA can approximate the
adiabatic evolution [6, 7, 8], which certifies success. Moreover, QAOA has
been shown to be successful in approximating solutions to several
combinatorial problems even with medium depths [5, 9, 10]. More
optimistically, it was established by Lloyd [11] and refined in [12] that QAOA
anstaze circuits can be used to emulate any other quantum circuit. In
practice, however, depth limits realizations of this approach in two
interconnected ways. Firstly, the QAOA sequence must be long enough to perform
the minimization, thereby avoiding underparameterisation effects such as
reachability deficits [13, 14]. Secondly, the problem Hamiltonian itself can
require significant overhead to realize, which in turn can translate into
increasingly longer circuits.

To take theory a step closer to practice, inspired in part by recent
experiments [15], we consider these challenges relative to the implementation
of QAOA assuming an ion based quantum computer. Ion based quantum computers
have made rapid progress in recent years [16], the primary advantages being
(i) the ability to prepare identical qubits with all-to all-connectivity [17],
(ii) high gate fidelities [18, 16, 19, 20, 21] and (iii) clean and relatively
fast readout [22]. Ion based quantum computers enable a native realization of
certain tunable Ising interactions [23, 24, 25, 26, 27, 28, 29, 30, 31, 32].
Such a Hamiltonian has recently been used in an experiment to implement a QAOA
circuit with upto $40$ qubits and $2$ layers [15]. The problem Hamiltonian
considered in this experiment is native to ion quantum computers. A natural
question arises regarding the solution of more arbitrary combinatorial
optimization problems. Gate based realization of general problem Hamiltonians
appears unattainable due to the required depths for all but the simplest
cases. How then might one solve general combinatorial optimisation problems
using today’s ion based processors?

In an attempt to circumvent direct realisation [27, 33, 15], we are left to
consider ion native Hamiltonians with tunable parameters. Whereas these native
Hamiltonians would typically have no direct relation to the problem
Hamiltonian, a variational ansatz can still be developed to solve a problem of
interest. Following this idea we propose a native realization of variational
QAOA-like circuit, and benchmark it against instances of Sherington-Kirkpatric
(SK) Hamiltonian. This model arises in physics as a mean field approach to
spin glasses – a disordered system which exhibits non trivial magnetic
behavior [34, 35]. Importantly, as the underlying interaction graph of SK
Hamiltonian has all-to-all connectivity, it rules out a direct implementation
for planar quantum processors. Furthermore, since the algorithmic performance
of QAOA on typical instances of SK Hamiltonians can be estimated in the
thermodynamic limit [36], the model therefore offers an ideal test case for
the developments made here.

For specific assignments of experimentally relevant parameters the proposed
ansatz produces states with a type of reflection symmetry. This induces
symmetry protection for some problem instances, that is these instances could
not be minimized, as their ground state belongs to a different symmetry class.
Violation of this symmetry with other assignments of the experimental
parameters, however, allowed to minimize all SK problem instances. Thus, our
approach extends the applicability of ion native QAOA to general combinatorial
problems which have no native realization on ion based quantum processors.

##  I Quantum Approximate Optimization Algorithm on ion based quantum
computers

###  I.1  Traditional approach to QAOA

The Quantum Approximate Optimization Algorithm approximates the ground state
of a given $n$ qubit problem Hamiltonian $H_{P}$. That is, the algorithm
prepares a unit norm quantum state $\ket{\psi}$ to find the minimum of the
expectation value ${\langle\psi|H_{P}|\psi\rangle}$. $H_{P}$ can embed a host
of combinatorial problems for e.g. graph minimization, Max-Cut [5] etc. The
embedding is such that the solution to the problem is encoded in the ground
state of $H_{P}$.

The optimization begins with a candidate solution (a.k.a. QAOA ansatz):

$\displaystyle\ket{\Psi_{p}(\bm{\beta},\bm{\gamma})}=$
$\displaystyle\Big{(}\prod_{k=1}^{p}\exp(-i\beta_{k}H_{x})\exp(-i\gamma_{k}H_{P})\Big{)}\ket{+}^{\otimes
n},$ (1)

where $H_{x}=\sum_{k=1}^{n}X_{k}$ is the mixer Hamiltonian, $X_{k}$ being the
Pauli-$X$ operator on the $k$-th qubit. A $p$-depth QAOA circuit has $2p$
variational parameters $\bm{\beta},\bm{\gamma}\in[0,\pi)^{\times
p},[0,2\pi)^{\times p}$. The ground state of $H_{P}$ is then prepared by
tuning $\bm{\beta},\bm{\gamma}$ variationally following the minimization:

$\min_{\bm{\beta},\bm{\gamma}}{\langle\Psi_{p}(\bm{\beta},\bm{\gamma})|H_{P}|\Psi_{p}(\bm{\beta},\bm{\gamma})\rangle},$
(2)

until a certain threshold is reached. A typical threshold, for example, is the
spectral gap $\Delta$, of the considered problem Hamiltonian. Reaching this
threshold guaranties certain overlap with the ground state [37] as,

$g(\psi)\geq 1-\frac{\bra{\psi}H_{P}\ket{\psi}-\lambda_{min}}{\Delta}.$ (3)

Here, $g(\psi)$ represents the ground state overlap with a state $\ket{\psi}$
and $\lambda_{min}$, the ground energy of $H_{P}$.

###  I.2 Native gates and propagators in ion based quantum computers

An ion based quantum computer comprises of ions in a radio frequency Paul trap
[20, 38]. Certain electronic energy levels of the trapped ion approximate a
two level system and hence serve as a qubit. Whereas there are multiple ways
to control ion qubits, the most relevant realization is based on laser-ion
interactions [16]. We will therefore focus on this case for the rest of the
paper.

Any unitary operation can be implemented on an ion based quantum computer
using a universal set of native gates. The set comprises of two single qubit
rotation operations $R_{Z}(\kappa)$ and $R_{\phi}(\theta)$ and one two qubit
entangling gate—typically based on the M$\o{}$lmer-S$\o{}$rensen (MS) gate
[33, 39]. Here $R_{Z}(\kappa)=\exp(-i\kappa Z)$, where $Z$ is the Pauli-$Z$
operator. The second single qubit gate is given by
$R_{\phi}(\theta)=\exp(-i\theta S_{\phi})$ where
$S_{\phi}=(X\cos\phi+Y\sin\phi)$, $X,Y$ being the Pauli-$X$ and Pauli-$Y$
operators. Both of these single qubit gates can be implemented by irradiating
an ion with laser fields. The laser is characterized by specific parameters
such as detuning, intensity, phase and laser pulse time, which can control the
factors $\kappa$, $\theta$ and select the axis of rotation [40].

The single qubit gates are known to demonstrate fidelities higher than
$99.9\%$ [41, 42, 18, 43, 16]. Two qubit gates on the other hand are more
difficult to implement: in general its performance degrades with the length of
ion chains and is not uniform acrosss all qubit pairs. For ion chains of
length 4 and 11, the two qubit gate fidelity are found to be ranging from
95$\%$ to 99$\%$ depending on the qubit pair [20, 21].

Given the limited fidelities in the gate based model, implementing arbitrary
circuits becomes a challenging task. One way to overcome this challenge is to
realize native propagators directly instead of gates. In fact this approach is
motivated by recent experimental demonstration of QAOA on 40 ions [15] and
quantum simulation of the transverse-field Ising model with long-range
interactions using 53 ion qubits [25]. It has been shown that upon the
application of specific external laser fields a system of trapped ions can be
described by the effective Ising Hamiltonian [27]:

$H_{I}=\dfrac{1}{2}\sum_{j\neq k}J_{jk}X_{j}X_{k},$ (4)

where the coupling constants $J_{jk}$ are approximated as

$J_{jk}\approx\frac{J_{\text{max}}A_{j}A_{k}}{|j-k|^{\alpha}},$ (5)

with $A_{j}\in[-1,1]$ which can be controlled experimentally by varying the
amplitude of the applied laser field. Here $J_{\text{max}}\in\mathbb{R}_{+}$
and $\alpha\in[0,3]$ [23, 27]. $H_{I}$ and hence the entangling propagator
$\exp(-i\gamma H_{I})$ are native to the ion hardware. Implementing this
propagator suppresses phonon excitation, which is one of the main source of
heating and decoherence in ion quantum computers [25]. This makes the choice
of $H_{I}$ pertinent. More experimentally relevant details on the ion
Hamiltonian are provided in appendix A.

###  I.3 Native QAOA implementation

In the gate based model, implementation of the circuit (I.1) on an ion based
quantum computer would require the circuit to be converted into a sequence of
native gates [38]. The propagator $\exp(-i\beta_{k}H_{x})$ admits a
decomposition in terms of single qubit rotation operation as
$(R_{\phi=0}(\beta_{k}))^{\otimes n}$. Decomposition of the propagator
$\exp(-i\gamma_{k}H_{P})$ on the other hand can prove more challenging as it
involves both single and two qubit gates. As discussed previously two qubit
gates are significantly noisier than single qubit gates. Thus, only a limited
number of two qubit gates can be implemented in order to restrict the total
error. This makes realization of the propagator $\exp(-i\gamma_{k}H_{P})$ for
an arbitrary $H_{P}$, impossible, within a reasonable error tolerance.

These shortcomings may however be avoided by choosing an alternate candidate
ansatz to minimize $H_{P}$:

$\displaystyle\ket{\psi_{p}(\bm{\beta},\bm{\gamma})}=$
$\displaystyle\prod_{k=1}^{p}\Big{(}\exp(-i\beta_{k}H_{x})\exp(-i\gamma_{k}H)\Big{)}\ket{+}^{\otimes
n},$ (6)

where $H$ is a non-local Hamiltonian that can create entanglement and does not
commute with $H_{x}$. Such an ansatz is reminiscent of Quantum Alternating
Operator Ansatz, also QAOA [44]. Apart from these algorithmic requirements,
the choice of $H$ should be dictated by specifications of the ion quantum
computer such that the propagator $\exp(-i\gamma_{k}H)$ and hence the circuit
(I.3) can be implemented naturally on the ion hardware. This step in
particular allows us to circumvent the gate model while implementing QAOA.

Consider the ansatz:

$\displaystyle\ket{\phi_{p}(\bm{\beta},\bm{\gamma})}=$
$\displaystyle\text{H}_{+}\Big{[}\prod_{k=1}^{p}\Big{(}\exp(-i\beta_{k}H_{z})\exp(-i\gamma_{k}H_{I})\Big{)}\ket{0}^{\otimes
n}\Big{]},$ (7)

where $\text{H}_{+}=({|+\rangle\\!\langle 0|}+{|-\rangle\\!\langle
1|})^{\otimes n}$ is the Hadamard gate applied to each of the qubits and
$H_{z}=\sum_{k}Z_{k}$. It can be shown that
$\ket{\phi_{p}(\bm{\beta},\bm{\gamma})}$ is equal to
$\ket{\psi_{p}(\bm{\beta},\bm{\gamma})}$ in (I.3) with

$\displaystyle H=\text{H}_{+}H_{I}\text{H}_{+}=\dfrac{1}{2}\sum_{j\neq
k}J_{jk}Z_{j}Z_{k}$ (8)

(see Appendix B for details). Eq. (I.3) is therefore indeed a QAOA circuit. It
gives rise to a variational state space

$\mathcal{S}=\bigcup_{\bm{\beta},\bm{\gamma}}\ket{\phi_{p}(\bm{\beta},\bm{\gamma})}.$
(9)

We further show that (I.3) is ion compatible; each term involved in the
preparation of $\ket{\phi_{p}(\bm{\beta},\bm{\gamma})}$ is native to the ion
quantum computer. Using the propagator $\exp(-i\gamma_{k}H_{I})$ in (I.3) is
vital; the propagator naturally arises when the system evolves under the ion
Hamiltonian $H_{I}$, and thus requires no gate decomposition unlike the
propagator $\exp(-i\gamma_{k}H_{P})$ in the original QAOA setting (I.1). The
term $\exp(-i\beta_{k}H_{z})$ can be decomposed into single qubit rotation
operations which, as was discussed, can be implemented with high fidelity.
Equivalently this term can also be implemented as a global rotation operation
by applying a single laser on all the ions at once. We further note that the
mixer Hamiltonian $H_{z}$ does not commute with $H_{I}$ as per the requirement
of the algorithm. Finally the gate $\text{H}_{+}$ is implemented as
$(R_{\phi={\frac{\pi}{2}}}(\frac{\pi}{4})R_{Z}(\frac{\pi}{2}))^{\otimes n}$,
where all gates involved in the decomposition are again native to the ion
based quantum computers.

##  II Numerical Experiments

###  II.1 The problem

We benchmark the proposed algorithm with all instances of $n=6$-qubit
Sherrington-Kirkpatrick (SK) Hamiltonians

$H_{P}=\frac{1}{2}\sum_{j\neq k}K_{jk}Z_{j}Z_{k},$ (10)

where $K_{jk}\in\\{1,-1\\}$. Our goal is to minimize $H_{P}$ with respect to
the ansatz (I.3) (see Appendix D numerics details). In other words, we seek
for the elements of

$\operatorname*{arg\,min}\limits_{\ket{\psi}\in\mathcal{S}}\bra{\psi}H_{P}\ket{\psi}.$
(11)

We consider the minimization to be successful if the difference between the
energy $\bra{\psi}H_{P}\ket{\psi}$ and the true ground state energy of
$\lambda_{min}(H_{P})$ is upper bounded by
$\dfrac{5}{100}|\lambda_{min}(H_{P})|$, that is a $5\%$ threshold on the
ground state energy, which is always below the gap for any $6$-qubit SK
instance.

During the minimization, we fix certain parameters in $H_{I}$. We work in the
dimensionless units where energy is measured in $\mathrm{kHz}$ and propagation
time in $\mathrm{ms}$ and set $J_{max}=4$ (see Appendix A for justification).
We chose $\alpha=1$, which we show to be sufficient in the next section. Thus,
we consider the couplings of the form

$J_{jk}=\frac{4A_{j}A_{k}}{|j-k|}.$ (12)

###  II.2 Results

####  II.2.1 Symmetric configuration

We start with elementary experimental setting $A_{j}=1$ for each qubit $j$.
The ion Hamiltonian couplings (12) under this assignment of $A_{j}$ become
$J_{jk}=\frac{4}{|j-k|}$. Based on our numerical data, we observed that not
all SK Hamiltonians could be minimized by our algorithm with the present
setting.

The instances for which the minimization was successful will be called easy
instances. Figure 1 demonstrates the energy minimization for such a case:
algorithmic performance gradually improves with increasing depth until the
ground state is recovered. In contrary, figure 2 illustrates the energy
minimization of what we call hard instances. These instances could not be
minimized by our algorithm in the symmetric setting: while performance still
can improve with increasing depth, the algorithm stagnates and energy can not
go past a certain threshold.

Figure 1: (color online) Energy minimization of an easy instance with respect
to the QAOA ansatz (I.3). Here we set $A_{j}=1$ for all qubits $j$. The energy
(see (2)) gradually decreases with increasing depth until minimization.
Insert: SK instance that is being minimized, red thin edges depict
$K_{jk}=+1$, while blue thick ones depict $K_{jk}=-1$. Figure 2: (color
online) Energy minimization of a hard instance with respect to the QAOA ansatz
(I.3). Here we set $A_{j}=1$ for all qubits $j$. The energy (see (2))
gradually decreases with increasing depth yet stagnates at some intermediate
value (here $\sim-5$). Insert: SK instance that is being minimized, red thin
edges depict $K_{jk}=+1$, while blue thick ones depict $K_{jk}=-1$.

The reason why some of the SK instances could not be minimized is related
directly to the symmetries intrinsic to our ansatz:

$\displaystyle X^{\otimes n}\ket{\psi}=\ket{\psi}$ (13)
$\displaystyle\mathcal{R}\ket{\psi}=\ket{\psi}$ (14)

Here $\mathcal{R}$ is a linear reflection operation that acts on a bitstring
as $\mathcal{R}\ket{j_{1}j_{2}\cdots j_{n-1}j_{n}}=\ket{j_{n}j_{n-1}\cdots
j_{2}j_{1}}$. Physically, operation $\mathcal{R}$ corresponds to reflection of
the ion string around the middle point. While the symmetry (13) is intrinsic
to our ansatz (I.3), the symmetry (14) arises only in the symmetric
configuration when $A_{j}=A_{n-j+1}$.

These relations (13) and (14) restrict the class of states that can be
prepared by our QAOA ansatz. In-fact $\mathcal{S}\subseteq\mathcal{V}$, where
$\mathcal{V}$ is the space of all possible $n$ qubit states that satisfy (13)
and (14) simultaneously. We call $\mathcal{V}$ the symmetric state space.
Naturally, this induces a symmetry protection for the instances without
symmetric ground state $\ket{\chi}\in\mathcal{V}$, all of which were therefore
classified as hard. Moreover, we observe that for the case of $6$ qubits SK
instances considered here, all instances with symmetric ground states are
classified as easy. We further show in Appendix C that one can define a basis
in $\mathcal{V}$ which forms a minimal set of states, sufficient to minimize
all easy instances. This results demonstrates that the choice of $J_{max}$ and
$\alpha$ was sufficient: with these choices the algorithm minimized all the
instances with symmetric ground states. In contrary, the other instances could
not be minimized for any other choice of $J_{max}$ and $\alpha$ due to
symmetry protection.

Finally, we observed that $\sim 0.67$ of all SK instances are hard due to
symmetry protection induced by (14). This can be seen in figure 4 (orange
curve): the fraction of solved instances monotonically grows with increasing
depth until it stagnates at depth $p=12$ at the value $\sim 0.33$. A question
follows naturally: is it possible to have a setting where all SK instances
could be minimized? We address this next.

####  II.2.2 Asymmetric configurations

We consider configurations that violate the condition $A_{j}=A_{n-j+1}$ and,
therefore remove the symmetry restriction (14). We consider two such settings
(i) randomly assigned values to the parameters $A_{j}$ and (ii) $A_{j}=1$,
$\forall j\neq j^{\prime}$ while the value of $A_{j^{\prime}}$ is selected at
random.

In both settings we observe that all SK instances are solved by our algorithm.
The blue curve in figure 4 demonstrates an example of this, where the fraction
of easy instances can be seen to be monotonically increasing with QAOA circuit
depth, until it reaches 1 at depth $p=20$. From this data we confirm that
lifting the symmetry is sufficient to minimize all the instances including
those that were classified as hard in the symmetric configuration.
Minimization of such instances became possible as violation of (14) ensures
that $\mathcal{S}$ is no longer restricted to $\mathcal{V}$. Figure 3 shows
the QAOA recovered energy minimization for one such instance using setting
(i). It must be noted here that despite similar performances setting (ii) is,
in principle, easier to implement experimentally as fewer ions require
individual addressing.

Figure 3: (color online) Energy minimization for the instance considered in
figure 2, with respect to the QAOA ansatz (I.3). Here we demonstrate three
random assignments of $A_{j}$, shown in different colors. We see that the
energy monotonically decreases with depth and eventually reaches the minimum.
We contrast this with the performance that was recorded with the symmetric
configuration: $A_{j}=1$, depicted by the blue curve.

####  II.2.3 Problem specific configuration

We find that using problem specific assignment of potentially unequal $A_{j}$
can lead to faster minimization of the problem instances compared to the
symmetric and asymmetric assignments. This is confirmed by our numerical data:
for each instance there exists a specific assignment of $A_{j}$ which allows
to minimize the instance in no more than $7$ layers (see figure 4 green
curve). Thus, we see a considerable reduction in the number of layers required
to minimize any instance compared to (i) the previous settings, which require
depths upto $p=20$, and (ii) standard QAOA which required depth $p=10$ to
minimize all SK instances (see red curve in figure 4).

Figure 4: (color online) Fraction of SK instances with $n=6$ that could be
minimized by the proposed QAOA ansatz at each depth. For the orange curve we
have set $A_{j}=1$ for all qubits $j$. For the blue curve we use randomly
assigned values of $A_{j}$ provided $A_{j}\neq A_{n-j+1}$. For the green curve
an instance was classified as solved if it was minimized with at least one of
the 50 randomly sampled sets of $A_{j}$. The red curve illustrates fraction of
SK instances that are minimized by standard QAOA circuit (I.1).

####  II.2.4 Large system size

While the benchmarking of the proposed algorithm was set against $n=6$-qubits
SK instances, here we demonstrate its performance for a larger system sizes.
We consider minimization of random instances of the SK Hamiltonian with the
number of qubits from $n=2$ to $20$ using $p=4,8$ layer QAOA-like circuit. For
every considered instance a specific choice of $A_{j}$ was used. In this
setting we demonstrate that the overlap of the prepared state with the ground
space of the instances improves with increasing depth (see figure 5). This
shows that the present algorithm has the potential to minimize arbitrary
instances of SK Hamiltoninas for large problem sizes.

We note from figure 5 that the overlap diminishes with the number of qubits
and the scaling is approximately exponential. This limitation is not peculiar
to our modification alone and is known in traditional QAOA [15]. This arises
from the fact that QAOA, in general, might require exponential (in $n$) depth
to minimize an $n$ qubit Hamiltonian [45, 46, 47].

Figure 5: (colors online) Overlap of the state prepared by the ansatz (I.3)
with the ground space, for different number of qubits. At each $n$ the overlap
is averaged over a set of fixed $20$ random instances. Blue curve represents
the overlap calculated for the initial QAOA state $\ket{+}^{\otimes n}$.
Orange curve illustrates overlap for the trained $p=4$ layer circuit. Green
curve demonstrates improved overlap for $p=8$ layer circuit, obtained via
repeated sampling of circuit parameters.

##  III Conclusion

We circumvent the traditional embedding problem and thereby expand the
application potential for modern day ion based processors. Given a problem
instance, one must either embed its Hamiltonian or emulate its propagator on a
given quantum processor. This requires overheads that currently prove the task
impossible in all but the simplest of cases. Hence we adapt the variational
approach to consider an ansatze family of states, based on the native ions
Hamiltonian, that prepare low energy states of the corresponding problem
Hamiltonian.

We exhaustively benchmarked the proposed algorithm by considering instances of
Sherrington-Kirkpatrick Hamiltonians for $n=6$ qubits. Upon considering
multiple experimentally relevant setups, we observed that certain
configurations induce symmetry protection for specific classes of problem
instances, which thus can not be minimized by the algorithm. Configurations
which violate the symmetry allowed the minimization of arbitrary SK instances.
In real settings, the required asymmetry can equivalently come from the more
general ion-compatible Hamiltonian used as a propagator, or from noise in the
system. We demonstrate that with problem specific configuration any instance
can be minimized with no more then $7$ layers, which is experimentally
accessible. Numerically we considered up to $n=20$ qubits and demonstrated
both training and performance improvement with increasing circuit depth.

Considering more general combinatorial optimization problem, one would expect
the problem density (the constraint to variable ratio) induce under-
parameterization which might necessitate large circuit depth [13]. As training
such circuits becomes costly at large depth, certain heuristics based on the
parameter concentrations [48] and layerwise training might be useful to
simplify the optimization. While, in principle, the proposed algorithm can
still suffer from training saturation, the performance might be recovered
under certain types of noise [49]. An alternative way to improve circuit
expressivity is to variationally control the $A_{j}$ terms, which is a subject
of further studies.

###### Acknowledgements.

The work was supported in the framework of the Roadmap for Quantum computing
(Contract No. 868-1.3-15/15-2021 and R2163). The large calculations were
performed on the Zhores supercomputer. The code is written in Python with
Intel optimised libraries and is available on reasonable request.

## References

  * [1] J Biamonte, P Wittek, N Pancotti, P Rebentrost, N Wiebe, and S Lloyd.  Quantum machine learning.  Nature, 549(7671):195–202, 2017.
  * [2] A Kardashin, A Uvarov, and J Biamonte.  Quantum machine learning tensor network states.  Frontiers in Physics, 8:586374, 2021.
  * [3] A V Uvarov, A S Kardashin, and J D Biamonte.  Machine learning phase transitions with a quantum processor.  Physical Review A, 102:012415, 2020.
  * [4] M E S Morales, T Tlyachev, and J Biamonte.  Variational learning of grover’s quantum search algorithm.  Physical Review A, 98:062333, 2018.
  * [5] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann.  A quantum approximate optimization algorithm.  arXiv:1411.4028, Nov 2014.
  * [6] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Joshua Lapan, Andrew Lundgren, and Daniel Preda.  A quantum adiabatic evolution algorithm applied to random instances of an np-complete problem.  Science, 292(5516):472–475, 2001.
  * [7] Tadashi Kadowaki and Hidetoshi Nishimori.  Quantum annealing in the transverse ising model.  Physical Review E, 58(5):5355, 1998.
  * [8] Sergio Boixo, Troels F Rønnow, Sergei V Isakov, Zhihui Wang, David Wecker, Daniel A Lidar, John M Martinis, and Matthias Troyer.  Evidence for quantum annealing with more than one hundred qubits.  Nature physics, 10(3):218–224, 2014.
  * [9] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann.  A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem.  arXiv preprint arXiv:1412.6062, 2014.
  * [10] Zhihui Wang, Stuart Hadfield, Zhang Jiang, and Eleanor G Rieffel.  Quantum approximate optimization algorithm for maxcut: A fermionic view.  Physical Review A, 97(2):022304, 2018.
  * [11] Seth Lloyd.  Quantum approximate optimization is computationally universal.  arXiv:1812.11075, 2018.
  * [12] M E S Morales, J D Biamonte, and Z Zimborás.  On the universality of the quantum approximate optimization algorithm.  Quantum Information Processing, 19(9):291, 2020.
  * [13] V Akshay, H Philathong, M E S Morales, and J D Biamonte.  Reachability deficits in quantum approximate optimization.  Physical Review Letters, 124:090504, 2020.
  * [14] V Akshay, H Philathong, I Zacharov, and J Biamonte.  Reachability deficits implicit in quantum approximate optimization of graph problems.  Quantum, 5:532, 2021.
  * [15] Guido Pagano, Aniruddha Bapat, Patrick Becker, Katherine S. Collins, Arinjoy De, Paul W. Hess, Harvey B. Kaplan, Antonis Kyprianidis, Wen Lin Tan, Christopher Baldwin, Lucas T. Brady, Abhinav Deshpande, Fangli Liu, Stephen Jordan, Alexey V. Gorshkov, and Christopher Monroe.  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.
  * [16] Colin D. Bruzewicz, John Chiaverini, Robert McConnell, and Jeremy M. Sage.  Trapped-ion quantum computing: Progress and challenges.  Applied Physics Reviews, 6(2):021314, 201.
  * [17] J. I. Cirac and P. Zoller.  Quantum computations with cold trapped ions.  Physical Review Letters, 74(20):4091–4094, may 1995.
  * [18] A. Bermudez, X. Xu, R. Nigmatullin, J. O’Gorman, V. Negnevitsky, P. Schindler, T. Monz, U. G. Poschinger, C. Hempel, J. Home, F. Schmidt-Kaler, M. Biercuk, R. Blatt, S. Benjamin, and M. Müller.  Assessing the progress of trapped-ion processors towards fault-tolerant quantum computation.  Phys. Rev. X, 7:041061, Dec 2017.
  * [19] Martin Ringbauer, Michael Meth, Lukas Postler, Roman Stricker, Rainer Blatt, Philipp Schindler, and Thomas Monz.  A universal qudit quantum processor with trapped ions, 2021.
  * [20] I. Pogorelov, T. Feldker, Ch. D. Marciniak, L. Postler, G. Jacob, O. Krieglsteiner, V. Podlesnic, M. Meth, V. Negnevitsky, M. Stadler, B. Höfer, C. Wächter, K. Lakhmanskiy, R. Blatt, P. Schindler, and T. Monz.  Compact ion-trap quantum computing demonstrator.  PRX Quantum, 2:020343, Jun 2021.
  * [21] K. Wright, K. M. Beck, S. Debnath, J. M. Amini, Y. Nam, N. Grzesiak, J.-S. Chen, N. C. Pisenti, M. Chmielewski, C. Collins, K. M. Hudek, J. Mizrahi, J. D. Wong-Campos, S. Allen, J. Apisdorf, P. Solomon, M. Williams, A. M. Ducore, A. Blinov, S. M. Kreikemeier, V. Chaplin, M. Keesan, C. Monroe, and J. Kim.  Benchmarking an 11-qubit quantum computer.  Nature Communications, 10(1):5464, 2019.
  * [22] Pengfei Wang, Chun-Yang Luan, Mu Qiao, Mark Um, Junhua Zhang, Ye Wang, Xiao Yuan, Mile Gu, Jingning Zhang, and Kihwan Kim.  Single ion qubit with estimated coherence time exceeding one hour.  Nature Communications, 12(1):233, 2021.
  * [23] D. Porras and J. I. Cirac.  Effective quantum spin systems with trapped ions.  Phys. Rev. Lett., 92:207901, May 2004.
  * [24] X.-L. Deng, D. Porras, and J. I. Cirac.  Effective spin quantum phases in systems of trapped ions.  Phys. Rev. A, 72:063407, Dec 2005.
  * [25] 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.
  * [26] Christine Maier, Tiff Brydges, Petar Jurcevic, Nils Trautmann, Cornelius Hempel, Ben P. Lanyon, Philipp Hauke, Rainer Blatt, and Christian F. Roos.  Environment-assisted quantum transport in a 10-qubit network.  Phys. Rev. Lett., 122:050501, Feb 2019.
  * [27] C. Monroe, W. C. Campbell, L.-M. Duan, Z.-X. Gong, A. V. Gorshkov, P. W. Hess, R. Islam, K. Kim, N. M. Linke, G. Pagano, P. Richerme, C. Senko, and N. Y. Yao.  Programmable quantum simulations of spin systems with trapped ions.  Rev. Mod. Phys., 93:025001, Apr 2021.
  * [28] P. Richerme, C. Senko, S. Korenblit, J. Smith, A. Lee, R. Islam, W. C. Campbell, and C. Monroe.  Quantum catalysis of magnetic phase transitions in a quantum simulator.  111(10):100506, sep 2013.
  * [29] P. Richerme, C. Senko, J. Smith, A. Lee, S. Korenblit, and C. Monroe.  Experimental performance of a quantum simulator: Optimizing adiabatic evolution and identifying many-body ground states.  88(1):012334, jul 2013.
  * [30] Philip Richerme, Zhe-Xuan Gong, Aaron Lee, Crystal Senko, Jacob Smith, Michael Foss-Feig, Spyridon Michalakis, Alexey V. Gorshkov, and Christopher Monroe.  Non-local propagation of correlations in quantum systems with long-range interactions.  Nature, 511(7508):198–201, jul 2014.
  * [31] J. Smith, A. Lee, P. Richerme, B. Neyenhuis, P. W. Hess, P. Hauke, M. Heyl, D. A. Huse, and C. Monroe.  Many-body localization in a quantum simulator with programmable random disorder.  12(10):907–911, jun 2016.
  * [32] C. Senko, J. Smith, P. Richerme, A. Lee, W. C. Campbell, and C. Monroe.  Coherent imaging spectroscopy of a quantum many-body spin system.  345(6195):430–433, jul 2014.
  * [33] Anders Sørensen and Klaus Mølmer.  Quantum computation with ions in thermal motion.  Phys. Rev. Lett., 82:1971–1974, Mar 1999.
  * [34] Dmitry Panchenko.  The sherrington-kirkpatrick model: an overview.  Journal of Statistical Physics, 149(2):362–383, 2012.
  * [35] David Sherrington and Scott Kirkpatrick.  Solvable model of a spin-glass.  Phys. Rev. Lett., 35:1792–1796, Dec 1975.
  * [36] 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.
  * [37] V. Akshay, H. Philathong, E. Campos, D. Rabinovich, I. Zacharov, Xiao-Ming Zhang, and J. Biamonte.  On circuit depth scaling for quantum approximate optimization.  2022\.
  * [38] Philipp Schindler, Daniel Nigg, Thomas Monz, Julio T Barreiro, Esteban Martinez, Shannon X Wang, Stephan Quint, Matthias F Brandl, Volckmar Nebendahl, Christian F Roos, Michael Chwalla, Markus Hennrich, and Rainer Blatt.  A quantum information processor with trapped ions.  New Journal of Physics, 15(12):123012, dec 2013.
  * [39] Anders Sørensen and Klaus Mølmer.  Entanglement and quantum computation with ions in thermal motion.  Phys. Rev. A, 62:022311, Jul 2000.
  * [40] Peter Zoller Crispin Gardiner.  The Quantum World of Ultra-Cold Atoms and Light Book II.  ICP, April 2015.
  * [41] Nitzan Akerman, Nir Navon, Shlomi Kotler, Yinnon Glickman, and Roee Ozeri.  Universal gate-set for trapped-ion qubits using a narrow linewidth diode laser.  New Journal of Physics, 17(11):113060, nov 2015.
  * [42] C. J. Ballance, T. P. Harty, N. M. Linke, M. A. Sepiol, and D. M. Lucas.  High-fidelity quantum logic gates using trapped-ion hyperfine qubits.  Phys. Rev. Lett., 117:060504, Aug 2016.
  * [43] Harry Levine, Alexander Keesling, Ahmed Omran, Hannes Bernien, Sylvain Schwartz, Alexander S. Zibrov, Manuel Endres, Markus Greiner, Vladan Vuletić, and Mikhail D. Lukin.  High-fidelity control and entanglement of rydberg-atom qubits.  Phys. Rev. Lett., 121:123603, Sep 2018.
  * [44] Stuart Hadfield, Zhihui Wang, Bryan O’Gorman, Eleanor G. Rieffel, Davide Venturelli, and Rupak Biswas.  From the quantum approximate optimization algorithm to a quantum alternating operator ansatz.  Algorithms, 12(2), 2019.
  * [45] Wim van Dam, Michele Mosca, and Umesh Vazirani.  How Powerful is Adiabatic Quantum Computation?  arXiv e-prints, pages quant–ph/0206003, May 2002.
  * [46] Boris Altshuler, Hari Krovi, and Jérémie Roland.  Anderson localization makes adiabatic quantum optimization fail.  Proceedings of the National Academy of Science, 107(28):12446–12450, July 2010.
  * [47] Zhang Jiang, Eleanor G. Rieffel, and Zhihui Wang.  Near-optimal quantum circuit for Grover’s unstructured search using a transverse field.  Phys. Rev. A, 95(6):062317, June 2017.
  * [48] V. Akshay, D. Rabinovich, E. Campos, and J. Biamonte.  Parameter concentrations in quantum approximate optimization.  Phys. Rev. A, 104:L010401, Jul 2021.
  * [49] E. Campos, D. Rabinovich, V. Akshay, and J. Biamonte.  Training saturation in layerwise quantum approximate optimization.  Phys. Rev. A, 104:L030401, Sep 2021.
  * [50] K. Kim, M.-S. Chang, R. Islam, S. Korenblit, L.-M. Duan, and C. Monroe.  Entanglement and tunable spin-spin couplings between trapped ions using multiple transverse modes.  Physical Review Letters, 103(12):120502, sep 2009.
  * [51] Igor Zacharov, Rinat Arslanov, Maksim Gunin, Daniil Stefonishin, Andrey Bykov, Sergey Pavlov, Oleg Panarin, Anton Maliutin, Sergey Rykovanov, and Maxim Fedorov.  “zhores”—petaflops supercomputer for data-driven modeling, machine learning and artificial intelligence installed in skolkovo institute of science and technology.  Open Engineering, 9(1):512–520, 2019.
  * [52] V. Akshay, H. Philathong, E. Campos, D. Rabinovich, I. Zacharov, Xiao-Ming Zhang, and J Biamonte.  On circuit depth scaling for quantum approximate optimization.  arXiv preprint arXiv:2205.01698, 2022.

##  Appendix A The ion model Hamiltonian

The review on different types of spin-spin interactions existing in trapped
ion Coulomb crystals exposed to external laser fields can be found in [27].
Here we focus on a specific type of Ising couplings which arises when the ions
are illuminated by bichromatic laser beams with same symmetric detunings
$\Delta$ (from the qubit transition frequencies), and ion–dependent beams
intensities. In the Lamb–Dicke approximation and in the dispersive regime [50]
the qubit dynamics can be described by the effective Hamiltonian (4) with the
couplings

$\begin{gathered}J_{jk}=\Omega_{j}\Omega_{k}\mathcal{C}_{jk}.\end{gathered}$
(15)

Here $\Omega_{j}$ are the Rabi frequencies induced by the laser field acting
on ion number $j$ and are, in general, controlled individually for each ion.
The matrix $\mathcal{C}_{jk}$ does not depend on $\Omega_{j}$ and has complex
dependence on the phonon normal modes and laser detunings for each phonon mode
frequency [27].

In this paper, we focus on the long range Ising couplings given by (4) and
(5). When the detuning $\Delta$ exceeds the frequency of the radial center of
mass mode, the dependence of $\mathcal{C}_{jk}$ on $j$ and $k$ can be
approximated with the power law $\mathcal{C}_{jk}\propto 1/|j-k|^{\alpha}$.
Given the notation $A_{j}=\Omega_{j}/|\Omega_{\mathrm{max}}|$, and
$J_{\text{max}}=J_{j,j+1}$ when $\Omega_{j}=\Omega_{\mathrm{max}}$ for all
qubits $j$, one gets (5) from (15). The exponent of the power law $\alpha$
ranges between $0$ and $3$ depending on the value of $\Delta$. Nevertheless,
the most relevant values for experimental realization lie between 0.8 and 1.8
[25], which allow to avoid motional decoherence and experimental drifts.

Typically, $J_{\text{max}}\sim 1\text{kHz}$ implying propagation times with
the ion Hamiltonian are of the order of several milliseconds. Thus, the
standard range of QAOA angle $\gamma\in[0,2\pi)$ can be treated as propagation
time measured in milliseconds. In dimensionless units we chose $J_{max}=4$
such that the phase $\gamma J_{max}$ could range in the experimentally
accessible range of several multiples of $\pi$.

##  Appendix B Relation between $\ket{\phi_{p}(\bm{\beta},\bm{\gamma})}$ and
$\ket{\psi_{p}(\bm{\beta},\bm{\gamma})}$

$\displaystyle\ket{\phi_{p}(\bm{\beta},\bm{\gamma})}=\text{H}_{+}\Big{[}\prod_{k=1}^{p}\Big{(}\exp(-i\beta_{k}H_{z})\exp(-i\gamma_{k}H_{I})\Big{)}\ket{0}^{\otimes
n}\Big{]}$
$\displaystyle=\text{H}_{+}\text{H}_{+}^{\dagger}\Big{[}\prod_{k=1}^{p}\Big{(}\text{H}_{+}\exp(-i\beta_{k}H_{z})\text{H}_{+}^{\dagger}\text{H}_{+}\times$
$\displaystyle\hskip
113.81102pt\times\exp(-i\gamma_{k}H_{I})\text{H}_{+}^{\dagger}\Big{)}\text{H}_{+}\ket{0}^{\otimes
n}\Big{]}$
$\displaystyle=\prod_{k=1}^{p}\Big{(}\exp(-i\beta_{k}\text{H}_{+}H_{z}\text{H}_{+}^{\dagger})\exp(-i\gamma_{k}\text{H}_{+}H_{I}\text{H}_{+}^{\dagger})\Big{)}\ket{+}^{\otimes
n}$
$\displaystyle=\prod_{k=1}^{p}\Big{(}\exp(-i\beta_{k}H_{x})\exp(-i\gamma_{k}H)\Big{)}\ket{+}^{\otimes
n}$ $\displaystyle=\ket{\psi_{p}(\bm{\beta},\bm{\gamma})}$ (16)

##  Appendix C Details on SK Hamiltonian minimization in symmetric
configuration

We construct a basis $\mathcal{M}$ in $\mathcal{V}$ such that any easy
instance, that is the ones with symmetric states in its ground space, can be
minimized by at least one state $\ket{\chi}\in\mathcal{M}$. The set
$\mathcal{M}$ comprises of 20 vectors divided into three classes. The first
two classes contain states of the form:

$\ket{s_{j}}=\frac{1}{\sqrt{2}}(\ket{t_{j}}+X^{\otimes n}\ket{t_{j}}),$ (17)

where $t_{j}$ are bit-strings, albeit with additional conditions. For the
first class the condition is $\ket{t_{j}}=\mathcal{R}\ket{t_{j}}$. Since $n=6$
only 4 states belong to this class. For the second class the condition is
$\ket{t_{j}}=\mathcal{R}X^{\otimes n}\ket{t_{j}}$. Again there are 4 states
that belong to this class. For the third class the states are of the form:

$\ket{r_{j}}=\frac{1}{2}(\ket{t_{j}}+X^{\otimes
n}\ket{t_{j}}+\mathcal{R}\ket{t_{j}}+\mathcal{R}X^{\otimes n}\ket{t_{j}}),$
(18)

provided that $\ket{t_{j}}$ do not obey the two conditions mentioned before. A
total of 12 such states were enumerated. We numerically confirm that all the
basis vectors can be prepared with our ansatz, that is,
$\mathcal{M}\subset\mathcal{S}$.

##  Appendix D Numerical details

The large calculations were performed on Zhores supercomputer [51]. We
required to classify weather each one of the $2^{15}$ 6-qubit SK instances
could be minimized with ansatz (I.3). In order to reduce the number of
calculations, each time the code took a new instance its ground space was
compared with those in a database. In the database the ground spaces were
classified on whether they can be prepared by the ansatz or not. If the ground
space was found in the database, the instance would be classified without
requiring minimization. On the contrary, if the ground space was not found in
the database, the program would attempt to minimize the instance with up to 20
layers and its ground space would be added to the database.

The minimization process was performed using a layerwise inspired heuristic
[52]. It starts with a single layer that is optimized, then keeping all the
previous parameters fixed, a new layer is added and trained. This is followed
by simultaneous optimization of all the parameters and the process of adding
and training is repeated. In our implementation, at each optimization step we
took the best of 25 seeds of the L-BFGS-B optimizer. The heuristic was
repeated a total of 50 times in hopes of finding the global minimum.