# Quantum approximate optimization of the long-range Ising model with a trapped-ion quantum simulator

Contributed by Christopher Monroe, July 30, 2020 (sent for review April 13, 2020; reviewed by John Bollinger, James Freericks, and Vito Scarola)

Research Article

September 28, 2020

## Significance

Variational quantum algorithms combine quantum resources with classical optimization methods, providing a promising approach to solve both quantum many-body and classical optimization problems. A crucial question is how variational algorithms perform as a function of qubit number. Here, we address this question by applying a variational quantum algorithm (QAOA) to approximate the ground-state energy of a long-range Ising model, both quantum and classical, and investigating the algorithm performance on a trapped-ion quantum simulator with up to 40 qubits. A negligible performance degradation and almost constant runtime scaling is observed as a function of the number of qubits. By modeling the error sources, we explain the experimental performance, marking a stepping stone toward more general realizations of hybrid quantum–classical algorithms.

## Abstract

Quantum computers and simulators may offer significant advantages over their classical counterparts, providing insights into quantum many-body systems and possibly improving performance for solving exponentially hard problems, such as optimization and satisfiability. Here, we report the implementation of a low-depth Quantum Approximate Optimization Algorithm (QAOA) using an analog quantum simulator. We estimate the ground-state energy of the Transverse Field Ising Model with long-range interactions with tunable range, and we optimize the corresponding combinatorial classical problem by sampling the QAOA output with high-fidelity, single-shot, individual qubit measurements. We execute the algorithm with both an exhaustive search and closed-loop optimization of the variational parameters, approximating the ground-state energy with up to 40 trapped-ion qubits. We benchmark the experiment with bootstrapping heuristic methods scaling polynomially with the system size. We observe, in agreement with numerics, that the QAOA performance does not degrade significantly as we scale up the system size and that the runtime is approximately independent from the number of qubits. We finally give a comprehensive analysis of the errors occurring in our system, a crucial step in the path forward toward the application of the QAOA to more general problem instances.

### Sign up for PNAS alerts.

Get alerts for new articles, or get an alert when an article is cited.

A promising near-term application of quantum devices is the production of highly entangled states with metrological advantage or with properties of interest for many-body physics and quantum information processing. One possible approach to produce useful quantum states is to use quantum devices to perform adiabatic quantum computing (1, 2), which, in some cases, may provide an advantage over classical approaches (3). However, adiabatic quantum computing has stringent adiabaticity requirements that hinder its applicability on existing quantum platforms that have finite coherence times (4).

Alternatively, hybrid quantum–classical variational algorithms may approximately solve hard problems in realms such as quantum magnetism, quantum chemistry (5), and high-energy physics (6). This is because the key resource of quantum computers and simulators is quantum entanglement, which is exactly what makes these many-body quantum problems hard. In a hybrid variational algorithm, entangled states are functions of variational parameters that are iteratively optimized by a classical algorithm. One example is the Quantum Approximate Optimization Algorithm (QAOA) (7), which consists of a “bang-bang” protocol that can provide approximate answers in a time-efficient way, using devices with finite coherence times and without the use of error correction (8–12).

Similarly to adiabatic quantum computing, the QAOA protocol encodes the objective function of the optimization problem in a target spin Hamiltonian. The optimization steps of the QAOA are based on unitary evolution under the target Hamiltonian and a noncommuting “mixing” operator. In general, the QAOA relies on a classical outer loop to optimize the quantum circuit, aided by physical intuition (13–16) or observed structure of the variational parameters (11, 17, 18), producing fast, low-depth circuits for approximate solutions. The QAOA has also been proposed as an efficient way to produce entangled quantum states, such as the ground states of critical Hamiltonians, which gives access to their corresponding energies (19, 20).

In this work, we employ a collection of interacting trapped-ion qubits to experimentally implement a specific instance of the QAOA, which is native to our quantum hardware. We focus on both the energy minimization of the quantum Hamiltonian and the combinatorial optimization of the corresponding classical problem. Both problems are encoded in the transverse-field antiferromagnetic Ising Hamiltonian with long-range interactions:Here, we set the reduced Planck’s constant $\hslash =1$; ${\sigma}_{i}^{\gamma}$ ($\gamma =x,y,z$) is the Pauli matrix acting on the ${i}^{\text{th}}$ spin along the $\gamma $ direction of the Bloch sphere; ${J}_{ij}>0$ is the Ising coupling between spins $i$ and $j$, which, in our case, falls off as a power law in the distance between the spins; and $B$ denotes the transverse magnetic field. It is well known (21) that the Hamiltonian (Eq. where the evolution times (or, henceforth, “angles”) ${\beta}_{k}$ and ${\gamma}_{k}$ are variational parameters used in the $k$-th QAOA layer to minimize the final energy $E\left(\overrightarrow{\beta},\overrightarrow{\gamma}\right)=\left.\u27e8\overrightarrow{\beta},\overrightarrow{\gamma}\right|H\left|\overrightarrow{\beta},\overrightarrow{\gamma}\right.\u27e9$.

$$H=\underset{{H}_{A}}{\underbrace{\sum _{i<j}{J}_{ij}{\sigma}_{i}^{x}{\sigma}_{j}^{x}}}+\underset{{H}_{B}}{\underbrace{B\sum _{i}{\sigma}_{i}^{y}}}.$$

[1]

**1**) exhibits a quantum-phase transition for antiferromagnetic interactions with power-law decay. One of the goals of this work is to find an approximation of the ground-state energy both at the critical point ${\left(B/{J}_{0}\right)}_{c}$, where ${J}_{0}$ is the average nearest-neighbor coupling, and in the case of $B=0$, optimizing the QAOA output for the classical Hamiltonian ${H}_{A}$. The realization of the QAOA entails a series of unitary quantum evolutions (Fig. 1) under the noncommuting Hamiltonians ${H}_{A}$ and ${H}_{B}$ (defined under Eq.**1**) that are applied to a known initial state $\left|{\psi}_{0}\right.\u27e9$. The state obtained after $p$ layers of the QAOA is:$$\left|\overrightarrow{\beta},\overrightarrow{\gamma}\right.\u27e9=\prod _{k=1}^{p}{e}^{-i{\beta}_{k}\left({H}_{B}/{J}_{0}\right)}{e}^{-i{\gamma}_{k}\left({H}_{A}/{J}_{0}\right)}\left|{\psi}_{0}\right.\u27e9,$$

[2]

Fig. 1.

In order to implement the quantum-optimization algorithm, each spin in the chain is encoded in the ${2}_{\mathrm{S}}^{1/2}\hspace{0.17em}\left|F=0,{m}_{F}=0\right.\u27e9\equiv {\left|\downarrow \right.\u27e9}_{z}$ and $\left|F=1,{m}_{F}=0\right.\u27e9\equiv {\left|\uparrow \right.\u27e9}_{z}$ hyperfine “clock” states of a

^{171}Yb^{+}ion (*SI Appendix*). In this work, depending on the number of qubits and measurements required, we employ two different quantum-simulation apparatus to run the QAOA, which will herein be referred to as system 1 (22) and system 2 (23) (*SI Appendix*). Both systems are based on a linear radiofrequency Paul trap, where we store chains of up to $N=40$ ions and initialize the qubits in the ground state of ${H}_{B}$, namely, the product state ${\left|\uparrow \uparrow \cdots \uparrow \right.\u27e9}_{y}\equiv {\left|+\right.\u27e9}^{\otimes N}=\left|{\psi}_{0}\right.\u27e9$, where ${\left|\uparrow \right.\u27e9}_{y}\equiv \left({\left|\uparrow \right.\u27e9}_{z}+i{\left|\downarrow \right.\u27e9}_{z}\right)/\sqrt{2}$, and $B$ is assumed to be negative. The unitary evolution under ${H}_{A}$ is realized by generating spin–spin interactions through spin-dependent optical dipole forces implemented by an applied laser field. This gives rise to effective long-range Ising couplings that fall off approximately as ${J}_{ij}\approx {J}_{\mathrm{0}}/|i-j{|}^{\alpha}$ (24). The power-law exponent $\alpha \sim 1$ and the interaction strengths vary in the range ${J}_{0}/2\pi =$ (0.3–0.57) kHz, depending on the system size and the experimental realization (see*SI Appendix*for details). The unitary evolution under ${H}_{B}$ is generated by applying a global rotation around the $y$ axis of the Bloch sphere.After each run of the algorithm, we performed a projective measurement of each spin in the $x\hspace{0.17em}\left(y\right)$ basis to measure $\u27e8{H}_{A}\u27e9$ ($\u27e8{H}_{B}\u27e9$) (Fig. 1). Measurements in the $x$ and $y$ bases were carried out by performing a $\pi /2$ rotation about the $y$ ($x$) axis of the Bloch sphere, illuminating the ions with resonant laser light, and collecting the ${\sigma}_{i}^{z}$-dependent fluorescence on a camera with site-resolved imaging. The energy was calculated by combining the measurements of the two-body correlators $\u27e8{\sigma}_{i}^{x}{\sigma}_{j}^{x}\u27e9$ and the total magnetization along the $y$ axis ${\sum}_{i}\u27e8{\sigma}_{i}^{y}\u27e9$, where the indices $i,j$ ranged from one to $N$. We benchmarked the experimental outcome $E\left(\overrightarrow{\beta},\overrightarrow{\gamma}\right)$ with the ground-state ${E}_{gs}$ of the target Hamiltonian (Eq. where ${E}_{max}$ is the energy of the highest excited state. This choice maps the entire many-body spectrum to the $\left[\mathrm{0,1}\right]$ interval. In the following, we show that the best experimental performance ${\eta}^{*}$ is close to the theoretical performance ${\eta}_{th}$, which itself is less than unity for a finite number $p$ of QAOA layers.

**1**), calculated numerically with exact diagonalization or Density Matrix Renormalization Group (DMRG) (25). In order to quantify the performance of the QAOA, we used the dimensionless quantity$$\eta \equiv \frac{E\left(\overrightarrow{\beta},\overrightarrow{\gamma}\right)-{E}_{max}}{{E}_{gs}-{E}_{max}},$$

[3]

## Quantum Hamiltonian Optimization

We first focused on the $p=1$ optimization of the full quantum problem, where two variational parameters ($\gamma $ and $\beta $) are used to minimize the energy of the Hamiltonian (Eq.

**1**). In this case, the time-evolved one- and two-point correlation functions can be efficiently computed (26, 27). This leads to a general formula for the energy expectation under a state produced by the $p=1$ QAOA that is used to compute the theoretical performance of the algorithm (*SI Appendix*). In Fig. 2*A*, we show an experimental exhaustive search over the parameter space $\left\{\gamma ,\beta \right\}$ and compare it to the theoretical performance of the algorithm, showing good agreement for $N=20$ qubits. We also compare the performance of our algorithm as a function of $B/{J}_{0}$ with the expected QAOA performance ${\eta}_{th}$ (Fig. 2*B*).Fig. 2.

As shown in ref. 21, for transverse field greater than the critical value, the ground state is a low-entanglement paramagnet, whereas below the critical point, the ground state is an entangled superposition of antiferromagnetic states. We located this critical point at $|B/{J}_{0}|=0.31$ for 20 qubits by computing the half-chain entanglement entropy ${S}_{L/2}=-\text{Tr}\left({\rho}_{L/2}\mathrm{log}{\rho}_{L/2}\right)$ of the ground state numerically, where ${\rho}_{L/2}$ is the half-chain reduced density matrix. As shown in Fig. 2

*B*, while the experimental performance was $\eta >94\%$ when $|B/{J}_{0}|$ is above the critical point, the gain relative to the initial state $\left|{\psi}_{0}\right.\u27e9$ was modest. On the other hand, below the critical point, the target state is more entangled, which allows for a larger experimental performance gain, at the expense of a reduced absolute performance. In order to quantitatively assess the gain over the finite initial-state performance, we introduced a performance natural scale based on the quantity ${\sigma}_{\eta}\left({J}_{0},B,N\right)$—namely, the SD around the mean performance achieved implementing a QAOA algorithm with random angles (see*SI Appendix*for details). For $N=20$ and $B/{J}_{0}\sim -0.3$, ${\sigma}_{\eta}\sim 2\times 1{0}^{-3}$. Our experimental performance at the critical point ${\eta}^{*}$ is more than 20${\sigma}_{\eta}$ away from the initial state. On the other hand, the discrepancy between the ideal and experimental performance can be explained by taking into account our noise sources in the numerics (Fig. 2*C*and*Combinatorial Optimization*).We investigated the performance of the $p=1$ QAOA algorithm as a function of the number of qubits. For each system size, we ensured that the spin–spin couplings ${J}_{ij}$ had the same dependence on the qubit distance $|i-j|$ by varying the trap parameters (

*SI Appendix*). As shown in Fig. 2*D*,*Inset*, the half-chain entanglement entropy as a function of system size $N$ exhibited a peak located at $B/{J}_{0}\sim -0.33$, displaying the onset of the phase transition as $N$ tended to infinity. For all system sizes, we optimized the algorithm by performing a scan of the interaction angle $\gamma $ and applying discrete variations of the mixing angle $\beta $ around the optimal value predicted by the theory. In Fig. 2*D*, we compare the optimal experimental and theoretical performances $\eta $ for different system sizes from 20 up to 40 qubits for fixed $B/{J}_{0}\sim -0.3$. We observed experimentally that the QAOA yielded a similar performance as a function of number of qubits, even if the algorithm runtime stayed approximately constant as the number of qubits increased. Numerically, we found that the performance $\eta $ scaled polynomially with $N$ and with the number of layers $p$ (28) (*SI Appendix*). Assuming that extrapolation to higher numbers of qubits holds, this scaling, combined with a polynomial-time search heuristic, suggests that for any desired energy threshold $\u03f5$, our approach allows us to approximate the energy to a degree $\eta >1-\u03f5$ in time and number of layers that scale as $\text{poly}\left(N,1/\u03f5\right)$.We experimentally performed a search for the optimal $p=2$ QAOA performance using 20 qubits. Unlike the $p=1$ case, there is no known analytic formula to efficiently compute the energy. However, exploiting relationships between optimal angles as a function of increasing $p$, we used a bootstrapping heuristic (see

*SI Appendix*for details) that allows the experiment to identify a set of optimal angles faster than a global parameter search. The bootstrapping heuristic computes a guess for optimal angles at $p$ given optimal angles at lower $p$. A local optimizer, such as the greedy gradient descent described below, is then needed to take this guess to the true optimum. Our heuristic method allows us to find variational parameters in time that scale polynomially with the number of layers and sublinearly in the number of qubits (when used in conjunction with the quantum device).We started from the optimal guess and performed a fine scan of ${\gamma}_{2}$, while varying ${\gamma}_{1},{\beta}_{1}$ and ${\beta}_{2}$ in larger steps. The result is shown in Fig. 2

*D*, where we plot the performances $\eta $ as a function of ${\gamma}_{2}$ for every set of parameters used in the experiment. Fig. 2*D*also shows a color plot of all of the optimal energies found as a function of the other three parameters ${\gamma}_{1},{\beta}_{1}$, and ${\beta}_{2}$. The $p=2$ QAOA performance with 20 qubits ${\eta}^{*}=\left(93.9\pm 0.3\right)\%$ is in agreement with the $p=1$ performance in system 2, taken with the same parameters (Fig. 2*C*). This indicates that decoherence and bit-flip errors (*SI Appendix*) accumulated during longer evolution times were already balancing out the $2\%$ expected performance gain of one additional optimization layer.As a brute-force approach is inefficient, we implemented a closed-loop QAOA by interfacing the analog trapped-ion quantum simulator with a greedy gradient-descent algorithm to optimize the measured energy. In the $p=1$ QAOA, we can visualize the optimization trajectory on the theoretical performance surface, as shown in Fig. 3. Starting from a guess $\left({\beta}^{\left(0\right)},{\gamma}^{\left(0\right)}\right)$, we measured the approximate local gradient by performing the energy measurements in two orthogonal directions ${\beta}^{\left(0\right)}+\delta \beta $ and ${\gamma}^{\left(0\right)}+\delta \gamma $ to compute the new guess $\left({\beta}^{\left(1\right)},{\gamma}^{\left(1\right)}\right)$, where we measured the new energy on the quantum simulator. As shown in Fig. 3, the algorithm converged after about 10 iterations. Compared to an exhaustive search, the gradient descent used fewer queries to the quantum simulator and was therefore more robust to slow drifts in the experimental system. For this reason, we were able to achieve a better performance compared to the exhaustive search method.

Fig. 3.

## Combinatorial Optimization

We further explored the performance of the trapped-ion system by investigating the combinatorial optimization of the classical Hamiltonian ${H}_{A}$ (Eq.

**1**with $B=0$) approximately sampling the output of the $p=1$ QAOA, using high-fidelity, single-shot measurement of all of the qubits. It has been proven, under reasonable complexity-theoretic assumptions, that no classical algorithm can efficiently sample exactly from a sufficiently general class of $p=1$ QAOA circuits (8). Recent results (29, 30) suggest that this could also hold in the case of approximate sampling (*SI Appendix*). In this case, by measuring in the $x$ basis, it is possible to sample the probability distribution of all of the ${2}^{N}$ eigenstates $\left|{x}_{i}\right.\u27e9$ of the Hamiltonian ${H}_{A}$. We performed the experiment with 12 qubits so that we could both compute the expected QAOA theoretical output and also experimentally oversample the Hilbert space of all of the possible 2^{12}= 4,096 possible outcomes. In Fig. 4*A*, we show on a log scale the QAOA eigenstates probability distribution using the optimal variational parameters ${\beta}^{*},{\gamma}^{*}$ and compare the experimental eigenstate histogram with the exact diagonalization prediction of the QAOA output state, sorting the eigenstates according to their energies.Fig. 4.

However, sampling from the full QAOA output distribution is a daunting task, since the experimental outcome is extremely sensitive to fluctuations in the Hamiltonian parameters and to experimental errors caused by detection and phonon-assisted bit-flip events and unwanted effective magnetic fields along the $z$ direction of the Bloch sphere caused by uncompensated light shift (see also

*SI Appendix*). Given our measured experimental parameters, we can calculate the effect of these errors on the quantum evolution, resulting in a good agreement with the experimental outcome, as shown in Fig. 4*A*.Another useful way to compare numerics and experimental data is to implement the coarse-graining procedure of the Hilbert space proposed in ref. 31. After sorting in decreasing order the observed states according to their experimental probability, we iteratively grouped the states into “bubbles” of Hamming distance $L$ around the most probable state, producing a coarse-grained dataset. We then applied the same coarse-graining to the theoretical probability distribution and plotted the comparison in Fig. 4where ${p}_{i}\left({q}_{i}\right)$ is the experimental (theoretical) probability of observing the $i$-th outcome. As shown in Fig. 4

*B*. In this procedure, the Hamming-distance radius was varied to ensure that each bubble contained a comparable number of experimental shots, leading to bubbles of average Hamming distance $\overline{L}=2.5$. In order to quantitatively compare the coarse-grained experiment and the theory, we used two different metrics, namely, the total variation distance (TVD) and the Kullback–Leibler divergence (${\mathrm{D}}_{K-\mathrm{L}}$), defined as:$$\mathrm{T}\mathrm{V}\mathrm{D}=\frac{1}{2}\sum _{i}|{p}_{i}-{q}_{i}|,$$

[4]

$${\mathrm{D}}_{\mathrm{K}-\mathrm{L}}=-\sum _{i}{p}_{i}\mathrm{log}\left(\frac{{q}_{i}}{{p}_{i}}\right),$$

[5]

*C*, when the system is in the initial state, it is closer to a uniform probability distribution since $\left|{\psi}_{0}\right.\u27e9$ is an equal superposition of all of the eigenstates of ${H}_{A}$. Indeed, at $\gamma =0$, the TVD between the data $\left\{{p}_{i}\right\}$ and the uniform distribution is smaller than the one comparing the data and the ideal QAOA distribution ${\left\{{q}_{i}\right\}}_{{\beta}^{*},{\gamma}^{*}}$. On the other hand, as the $\gamma $ parameter was scanned, we observed a net decrease of both TVD and ${\mathrm{D}}_{\mathrm{K}-\mathrm{L}}$ between the experiment $\left\{{p}_{i}\right\}$ and the QAOA ideal distribution ${\left\{{q}_{i}\right\}}_{{\beta}^{*},{\gamma}^{*}}$, in agreement with the decrease in energy, computed by measuring one- and two-body correlators.The variational quantum algorithm reported here, with up to 40 trapped-ion qubits, is the largest ever realized on a quantum device. We approximated the ground-state energy of a nontrivial quantum Hamiltonian, showing almost constant time scaling with the system size. Single-shot, high-efficiency qubit measurements in different bases gave access to the full distribution of bit-strings that is difficult or potentially impossible to model classically. With the addition of individual control over the interactions between qubits, as well as improvements to fidelity and system size, the variational quantum-classical hybrid approach can be employed in this experimental platform to give insight into quantum chemistry (32–34) and hard optimization problems (35), such as maximum-satisfiability or exact cover (36), or be used for the production of highly entangled states of metrological interest (37).

### Data and Code Availability.

All study data are included in the article and

*SI Appendix*.## Acknowledgments

We thank L.-M. Duan, Y. Wu, B. Fefferman, and S. Wang for illuminating discussions. The DMRG simulations were performed by using Open Source Matrix Product States. This work is supported by the Army Research Office (ARO) and Air Force Office of Scientific Research (AFOSR) Quantum Information Sciences (QIS) and Atomic and Molecular Physics programs; the AFOSR Multidisciplinary University Research Initiative (MURIs) on Quantum Measurement/Verification and Quantum Interactive Protocols; the ARO MURI on Modular Quantum Systems; the Intelligence Advanced Research Programs Activity (IARPA) Logical Qubits program; the National Science Foundation Practical Fully-Connected Quantum Computer STAQ program PHY-1818914; the Department of Energy (DOE) Basic Energy Sciences: Materials and Chemical Sciences for Quantum Information Science program DE-SC0019449 (optical design and instrumentation and theoretical analysis of sampling complexity); and the DOE High Energy Physics: Quantum Information Science Enabled Discovery Programs DE-0001893 (cryogenic vacuum chamber maintenance) and DE-SC0019139 (theoretical variational optimization analysis).

## Supporting Information

Appendix (PDF)

- Download
- 1.47 MB

## References

1

T. Kadowaki, H. Nishimori, Quantum annealing in the transverse Ising model.

*Phys. Rev. E***58**, 5355–5363 (1998).2

E. Farhi, J. Goldstone, S. Gutmann, M. Sipser, Quantum computation by adiabatic evolution. arXiv:quant–ph/0001106 (28 January 2000).

3

M. B. Hastings, M. H. Freedman, Obstructions to classically simulating the quantum adiabatic algorithm. arXiv:1302.5733 (22 February 2013).

4

P. Richerme et al., Experimental performance of a quantum simulator: Optimizing adiabatic evolution and identifying many-body ground states.

*Phys. Rev. A***88**, 012334 (2013).5

J. R. McClean, J. Romero, R. Babbush, A. Aspuru-Guzik, The theory of variational hybrid quantum-classical algorithms.

*New J. Phys.***18**, 023023 (2016).6

C. Kokail et al., Self-verifying variational quantum simulation of lattice models.

*Nature***569**, 355–360 (2019).7

E. Farhi, J. Goldstone, S. Gutmann, A quantum approximate optimization algorithm. arXiv:1411.4028 (14 November 2014).

8

E. Farhi, A. W. Harrow, Quantum supremacy through the quantum approximate optimization algorithm. arXiv:1602.07674 (24 February 2016).

9

S. Lloyd, Quantum approximate optimization is computationally universal. arXiv:1812.11075 (28 December 2018).

10

J. Preskill, Quantum computing in the NISQ era and beyond.

*Quantum***2**, 79 (2018).11

L. Zhou, S. T. Wang, S. Choi, H. Pichler, M. D. Lukin, Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices. arXiv:1812.01041 (3 December 2018).

12

M. B. Hastings, Classical and quantum bounded depth approximation algorithms. arXiv:1905.07047 (16 May 2019).

13

A. Bapat, S. Jordan, Bang-bang control as a design principle for classical and quantum optimization algorithms. arXiv:1812.02746 (6 December 2018).

14

G. Verdon, J. Pye, M. Broughton, A universal training algorithm for quantum deep learning. arXiv:1806.09729 (25 June 2018).

15

Z. Jiang, E. G. Rieffel, Z. Wang, Near-optimal quantum circuit for Grover’s unstructured search using a transverse field.

*Phys. Rev. A***95**, 062317 (2017).16

Z. Wang, S. Hadfield, Z. Jiang, E. G. Rieffel, Quantum approximate optimization algorithm for Maxcut: A fermionic view.

*Phys. Rev. A***97**, 022304 (2018).17

G. E. Crooks, Performance of the quantum approximate optimization algorithm on the maximum cut problem. arXiv:1811.08419 (20 November 2018).

18

G. B. Mbeng, R. Fazio, G. Santoro, Quantum annealing: A journey through digitalization, control, and hybrid quantum variational schemes. arXiv:1906.08948 (21 June 2019).

19

W. W. Ho, T. H. Hsieh, Efficient variational simulation of non-trivial quantum states.

*SciPost Phys.***6**, 29 (2019).20

W. W. Ho, C. Jonay, T. H. Hsieh, Ultrafast state preparation via the quantum approximate optimization algorithm with long range interactions. arXiv:1810.04817 (11 October 2018).

21

T. Koffel, M. Lewenstein, L. Tagliacozzo, Entanglement entropy for the long-range Ising chain in a transverse field.

*Phys. Rev. Lett.***109**, 267203 (2012).22

K. Kim et al., Entanglement and tunable spin-spin couplings between trapped ions using multiple transverse modes.

*Phys. Rev. Lett.***103**, 120502 (2009).23

G. Pagano et al., Cryogenic trapped-ion system for large scale quantum simulation.

*Quantum Sci. Technol.***4**, 014004 (2019).24

D. Porras, J. I. Cirac, Effective quantum spin systems with trapped ions.

*Phys. Rev. Lett.***92**, 207901 (2004).25

D. Jaschke, M. L. Wall, L. D. Carr, Open source matrix product states: Opening ways to simulate entangled many-body quantum systems in one dimension.

*Comput. Phys. Commun.***225**, 59–91 (2018).26

D. Dylewsky, J. Freericks, M. Wall, A. Rey, M. Foss-Feig, Nonperturbative calculation of phonon effects on spin squeezing.

*Phys. Rev. A***93**, 013415 (2016).27

S. Hadfield, Quantum algorithms for scientific computing and approximate optimization. arXiv:1805.03265 (8 May 2018).

28

M. M. Wauters, G. B. Mbeng, G. E. Santoro, Polynomial scaling of QAOA for ground-state preparation: Taming first-order phase transitions. arXiv 2003.07419 (16 March 2020).

29

M. J. Bremner, A. Montanaro, D. J. Shepherd, Average-case complexity versus approximate simulation of commuting quantum computations.

*Phys. Rev. Lett.***117**, 080501 (2016).30

A. Bouland, B. Fefferman, C. Nirkhe, U. Vazirani, On the complexity and verification of quantum random circuit sampling.

*Nat. Phys.***15**, 159–163 (2019).31

S. T. Wang, L. M. Duan, Certification of boson sampling devices with coarse-grained measurements. arXiv 1601.02627 (11 January 2016).

32

A. Kandala et al., Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets.

*Nature***549**, 242–246 (2017).33

C. Hempel et al., Quantum chemistry calculations on a trapped-ion quantum simulator.

*Phys. Rev. X***8**, 031022 (2018).34

Y. Nam et al., Ground-state energy estimation of the water molecule on a trapped ion quantum computer. arXiv:1902.10171 (26 February 2019).

35

J. S. Otterbach et al., Unsupervised machine learning on a hybrid quantum computer. arXiv:1712.05771 (15 December 2017).

36

E. Farhi et al., A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem.

*Science***292**, 472–475 (2001).37

V. Giovannetti, S. Lloyd, L. Maccone, Advances in quantum metrology.

*Nat. Photon.***5**, 222–229 (2011).## Information & Authors

### Information

#### Published in

#### Classifications

#### Copyright

Copyright © 2020 the Author(s). Published by PNAS. This open access article is distributed under Creative Commons Attribution-NonCommercial-NoDerivatives License 4.0 (CC BY-NC-ND).

#### Submission history

**Published online**: October 6, 2020

**Published in issue**: October 13, 2020

#### Change history

August 16, 2021: The SI Appendix has been updated to coincide with a formal Correction.

#### Keywords

#### Acknowledgments

We thank L.-M. Duan, Y. Wu, B. Fefferman, and S. Wang for illuminating discussions. The DMRG simulations were performed by using Open Source Matrix Product States. This work is supported by the Army Research Office (ARO) and Air Force Office of Scientific Research (AFOSR) Quantum Information Sciences (QIS) and Atomic and Molecular Physics programs; the AFOSR Multidisciplinary University Research Initiative (MURIs) on Quantum Measurement/Verification and Quantum Interactive Protocols; the ARO MURI on Modular Quantum Systems; the Intelligence Advanced Research Programs Activity (IARPA) Logical Qubits program; the National Science Foundation Practical Fully-Connected Quantum Computer STAQ program PHY-1818914; the Department of Energy (DOE) Basic Energy Sciences: Materials and Chemical Sciences for Quantum Information Science program DE-SC0019449 (optical design and instrumentation and theoretical analysis of sampling complexity); and the DOE High Energy Physics: Quantum Information Science Enabled Discovery Programs DE-0001893 (cryogenic vacuum chamber maintenance) and DE-SC0019139 (theoretical variational optimization analysis).

### Authors

#### Competing Interests

Competing interest statement: C.M. is co-founder and chief scientist of IonQ, a company that manufactures quantum computers. No IonQ employees, equipment, or other assets were involved with any aspect of the planning, design, execution, analysis, or reporting of this research.

## Metrics & Citations

### Metrics

#### Citation statements

#### Altmetrics

### Citations

If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.

#### Cited by

Loading...

## View Options

### View options

#### PDF format

Download this article as a PDF file

DOWNLOAD PDF### Get Access

#### Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Personal login Institutional Login#### Recommend to a librarian

Recommend PNAS to a Librarian#### Purchase options

Purchase this article to access the full text.