Solving optimization problems with Rydberg analog quantum computers: Realistic requirements for quantum advantage using noisy simulation and classical benchmarks

Platforms of Rydberg atoms have been proposed as promising candidates to solve some combinatorial optimization problems. Here we compute quantitative requirements on the system sizes and noise levels that these platforms must fulfill to reach quantum advantage in approximately solving the Unit-Disk Maximum Independent Set problem. Using noisy simulations of Rydberg platforms of up to 26 atoms interacting through realistic van der Waals interactions, we compute the average approximation ratio that can be attained with a simple quantum annealing-based heuristic within a fixed temporal computational budget. Based on estimates of the correlation lengths measured in the engineered quantum state, we extrapolate the results to large atom numbers and compare them to a simple classical approximation heuristic. We find that approximation ratios of at least $\approx 0.84$ are within reach for near-future noise levels. Not taking into account further classical and quantum algorithmic improvements, we estimate that quantum advantage could be reached by attaining a number of controlled atoms of $\sim 8000$ for a time budget of 2 s, and $\sim 1000–1200$ for a time budget of 0.2 s, provided the coherence levels of the system can be improved by a factor 10 while maintaining a constant repetition rate.

Figure 1

An example of a unit-disk graph with 10 vertices. The red dots correspond to a maximum independent set for this graph, i.e., a set of mutually nonconnected vertices of maximum cardinality.

Figure 2

Time dependence of the coefficients of the dephasing (top) and Rabi (bottom) terms; see Eq. (7).

Figure 3

Illustration of the execution of lines 4 to 10 of Algorithm lg1, for $d$=2, on a graph with 20 vertices (top left). Top right: a random vertex $u$(in blue) is selected, and the sphere $S_d\left(u\right)$ of vertices within distance $d$ (red) is computed. Bottom right: An optimal MIS is computed for $S_d\left(u\right)$ (yellow vertices). All vertices from $S_d\left(u\right)$, along with all vertices not in $S_d\left(u\right)$ but connected to a vertex in the MIS of $S_d\left(u\right)$ are then removed. Bottom left: a new random vertex has been selected for the next iteration of the algorithm.

Figure 4

Approximation ratio as a function of the problem size. Solid lines and circles: average maximum approximation ratio over a fixed 2 s run time ($=10$ shots in the quantum case). Dashed lines and squares: average (single-shot) approximation ratio. Left: Quantum annealing with Rydberg atoms for different noise levels ($\gamma =3.0$ [red]: state-of-the-art noise level, $\gamma =0.3$ [blue]: near-term noise level, $\gamma =0.0$ [black]: noiseless case). Dotted lines: extrapolation using data for 12–26 atoms (see inset) [see Eq. (19)] with 95% prediction interval. Dash-dotted lines: constant extrapolation for one-shot case, based on the last ($\gamma =0.3$) and last three ($\gamma =3.0$) points. Optimized annealing time $t_{\mathrm{f}}$ (see text). Right: average maximum approximation ratios and average approximation ratios achieved by classical locality-based approach for maximum resolution distance $d$ of 0 [red], 5 [blue], 10 [green], and 15 [magenta]. Results were obtained by averaging over 100 random unit-disk graphs. Inset: Maximum graph size (atom number) reachable by classical algorithm within 2 s as a function of $d$.

Figure 5

Break-even diagram. Black dots (resp. gray squares): average classical approximation ratio reached for the maximum graph size reachable in 2 s (resp. 0.2 s) (asymptotic approximation ratio extrapolation from Figs. 4 and 18, and maximum reachable graph size estimation from Figs. 4 and 19). Dash-dotted lines: lower bound to quantum approximation ratio reached for decoherence levels of $\gamma =3.0$ (red) and $\gamma =0.3$ (blue), assuming constant repetition rate with system size. Black (resp. gray) dashed line: break-even line for a time budget of 2 s (resp. 0.2 s).

Figure 6

Néel structure factor as a function of time. Same parameters as Fig. 4.a of Ref. [22]: $4\times 4$ square lattice of atoms, $\gamma =3.0$. Solid lines: with readout error $\epsilon ={\epsilon }^{\prime }=0.03$. Dashed lines: without readout error. Crosses: experimental data, reproduced from Ref. [22].

Figure 7

Target energy as a function of the annealing time (in $\mu \mathrm{s}$) for various noise levels. Solid lines: full Hilbert space. Dashed lines: keeping only IS states in Hilbert space (see Appendix pp5-s1). Dashed green line: energy of the maximally mixed state. Dotted black line: energy of the optimal (MIS) solution.

Figure 8

Approximation ratio as a function of the number of annealing time optimization steps. Solid lines and square symbols: full Hilbert space. Dashed lines and circles: IS-Hilbert space.

Figure 9

Optimal annealing time $t_{\mathrm{f}}^{*}$ (in $\mu \mathrm{s}$) as a function of the number of atoms for various noise levels.

Figure 10

Approximation ratio as a function of the run time (computed as the number of repetitions $n_{\mathrm{shots}}$ times the repetition rate, $f=5\mathrm{Hz}$ here), after optimization of the annealing time $t_{\mathrm{f}}$. Solid lines: without readout noise. Dashed lines: with readout noise $\epsilon ={\epsilon }^{\prime }=3\%$. Black, blue and red curves: approximation ratio for the final state distribution obtained with noise parameters $\gamma =0.0$, 0.3, and 3.0, respectively. Green curves: for a uniform distribution over the IS states. State space restricted to IS-Hilbert space.

Figure 11

Approximation ratio as a function of the number of atoms in quantum annealing for various fixed run times (same data as Fig. 10). Solid lines: without readout noise. Dashed lines: with readout noise $\epsilon ={\epsilon }^{\prime }=3\%$. Dash-dotted lines: fit function Eq. (19). Black, blue and red curves: approximation ratio for the final state distribution obtained with noise parameters $\gamma =0.0$, 0.3, and 3.0, respectively, averaged over 20 random graphs (except for $N_{\mathrm{atoms}}=24,26$: 10 graphs). Green dash-dotted lines: average approximation ratio for a uniform probability over IS states.

Figure 12

Spin-spin correlation length $\xi$ extracted by fitting the spin-spin correlation function for various noise levels (black: $\gamma =0.0$, blue: $\gamma =0.3$, red: $\gamma =3.0$). (See Fig. 22 for fitting details.)

Figure 13

Top: Run time of locality-based approximation heuristic as a function of the number of atoms. Bottom: corresponding number of allowed shots within a 2 s time window.

Figure 14

Run time of locality-based heuristic from Algorithm lg1. Solid lines: run time including graph manipulations (such as BFS) and solving, not taking file I/O overhead inherent to the execution of [40]. Dashed lines: solving time only, disregarding BFS and other graph manipulation. Overall, run time is governed by the number and sizes of graph instances to solve.

Figure 15

0.9th quantile of sizes (i.e., 90% of the sizes fall below this threshold) of subinstances to solve exactly when running the locality-based heuristic Algorithm lg1.

Figure 16

Run time of exact branch-and-bound solver [40] as a function of the number of vertices, for the class of random graphs we considered (described in Appendix pp4).

Figure 17

Comparison of execution times of generic state-of-the-art branch-and-bound MIS solver (bb-generic) [40] and an implementation of a specialized UD-MIS solver, based on dynamic programming [29], as can be readily derived from Ref. [25] (specific-dp-based).

Figure 18

Single-shot average (over 100 random graphs) approximation ratio achieved by classical locality-based heuristic (Algorithm lg1) on random unit-disk graphs (see Sec. pp4).

Figure 19

Top: execution time of classical locality-based approximation heuristic, as a function of the number of atoms. Bottom: corresponding allowed number of shots in 2 s.

Figure 20

Hybrid quantum-classical algorithm for the approximate solution of the UD-MIS problem. Box (a): outer minimization. Box (b): inner minimization. Box (c): quantum part of the algorithm, performed with a Rydberg platform. Red labels in brackets: simplified variational parameters used in this work. All variational parameters are lumped into a single parameter $\vec{\theta }$. $u$ is set to $u=1.35$ for all shown results.

Figure 21

Spin-spin correlation function ${\langle z_i{z}_j\rangle }_{\mathrm{\Psi }}$ (see text) as a function of the Euclidean distance for one graph instance and for various noise levels (black: $\gamma =0.0$, blue: $\gamma =0.3$, red: $\gamma =3.0$) and graph sizes (clockwise from top left: $N_{\mathrm{atoms}}=10,12,16,14$).

Figure 22

Spin-spin correlation function $g^{\left(2\right)}\left(r\right)$ (see text) as a function of the distance for various noise levels (black: $\gamma =0.0$, blue: $\gamma =0.3$, red: $\gamma =3.0$) and various graph sizes (clockwise from top left: $N_{\mathrm{atoms}}=10,12,16,14$). The dashed lines show the result of a fit with the exponential decay function $e^{-r/\xi (\gamma ,N_{\mathrm{atoms}})}$.

Figure 23

Comparison of approximation ratio with its upper bound in the uniform case. Solid lines: $S{(\alpha (N,S)-1/2)}^2$, with $\alpha (N,S)=\mathbb{E}\left[{max}_{p=1,\cdots ,N}\left\{E_i(S;p)\right\}\right]/S$. Dashed black line: $\text{ln}N/2$.