Quantum Optimization via Four-Body Rydberg Gates

A large ongoing research effort focuses on obtaining a quantum advantage in the solution of combinatorial optimization problems on near-term quantum devices. A particularly promising platform implementing quantum optimization algorithms are arrays of trapped neutral atoms, laser coupled to highly excited Rydberg states. However, encoding combinatorial optimization problems in atomic arrays is challenging due to limited interqubit connectivity of the native finite-range interactions. Here, we present a four-body Rydberg parity gate, enabling a direct and straightforward implementation of the parity architecture, a scalable architecture for encoding arbitrarily connected interaction graphs. Our gate relies on adiabatic laser pulses and is fully programmable by adjusting two hold times during operation. We numerically demonstrate implementations of the quantum approximate optimization algorithm (QAOA) for small-scale test problems. Variational optimization steps can be implemented with a constant number of system manipulations, paving the way for experimental investigations of QAOA beyond the reach of numerical simulations.

Figure 1

Rydberg parity QAOA protocol. Arbitrarily connected optimization problems can be parity encoded in a regular geometry of neutral atoms trapped in, e.g., optical tweezers. After initializing the Rydberg quantum processor in an equal superposition state, generating variational wave functions by applying QAOA unitaries only requires local control of laser fields generating quasilocal four-qubit (square boxes) and single-qubit gates (discs).

Figure 2

Four-body Rydberg gate protocol. The laser-parameter dependent plaquette energy-spectrum exhibits distinct behavior with respect to the number of laser-excitable spins (indicated by ). Solid (dashed) lines show the energy-spectrum as function of the laser detuning ${\mathrm{\Delta }}_{\downarrow ,\uparrow }$ for a fixed Rabi frequency of ${\mathrm{\Omega }}_{\downarrow ,\uparrow }=V/2$ (${\mathrm{\Omega }}_{\downarrow ,\uparrow }=0$). Applying an adiabatic, time-dependent laser pulse $[{\mathrm{\Omega }}_{\downarrow }(t),{\mathrm{\Delta }}_{\downarrow }(t)]$ addressing qubit state $|\downarrow ⟩$ imprints an excitation-sector dependent dynamical phase ${\varphi }_n$ on the corresponding computational basis states (upper row). For constant Rydberg interaction strengths between plaquette atoms, subsequently applying the same adiabatic laser pulse on qubit states $|\uparrow ⟩$ leads to the desired phase separation of even and odd parity configurations (bottom line).

Figure 3

(a) Two-pause pulse example. Laser parameters that are used for pulse optimization are indicated as dots (see main text). (b) Gate error of the parity gate for experimental conditions as $V=2\pi \times 40\mathrm{MHz}$, ${\mathrm{\Omega }}_{\max }=2\pi \times 30\mathrm{MHz}$, ${\mathrm{\Delta }}_{\text{start},\mathrm{end}}/V\in [-3.0,0.0]$, and ${\mathrm{\Delta }}_{A,B}/V\in [-3.0,1.0]$, averaged over ${10}^4$ randomly chosen phase-combinations (see SM [36]). Highlighted points correspond to the pulse shown in panel (a), with pause times $t_{A,B}$ adjusted to $\gamma =\pi /4$, corresponding to the maximally entangling gate operation.

Figure 4

(a) Example QAOA simulation for 20 qubits. Shown are the lowest observed- and average residual energy after each parameter update. (b) Distribution of average residual energies of 50 independent optimization runs (200 parameter updates) for a single optimization problem with varying error rates of the four-body parity gate. Final energy values were reestimated via 5000 circuit executions and measurements. The black bars visualize the 25th to 75th percentiles and the white circles denote the median of the distribution.