Error-Corrected Quantum Optimization via Rydberg Atom Array Embeddings

Abstract

Rydberg atom quantum optimizers naturally encode the maximum independent set problem on geometric graphs. However, to solve general combinatorial optimization problems on more complex topologies, an embedding is required to overcome the limited-range native interactions. Such embeddings use gadgets, specific arrangements of atoms, which inevitably introduce ancillary atoms. Here, we show that this apparent overhead instead provides an intrinsic resource for error correction. Specifically, we demonstrate that the Parity Architecture-based Rydberg embedding naturally forms a classical error-correcting code, a principle that extends to other Rydberg blockade-based embeddings. Within superatom substructures, exact Rydberg-excitation-number constraints provide local error syndromes at no additional hardware cost and give rise to a strictly nonlinear code. To correct bit-flip errors, we introduce the precisely tailored Cluster decoder, which exploits these local constraints and the underlying gadget structure. Numerically, this approach achieves an error threshold of $p_{\text{th}}\gtrsim26 \%$ across different layout geometries. Experimentally, on the QuEra Aquila QPU, the Cluster decoder recovers exact optimization solutions with an average success rate of $\gtrsim8\%$ for systems of up to 107 atoms, even when bare hardware and standard greedy post-processing find none. A Rydberg atom array embedding is therefore not merely a hardware mapping of an optimization problem, but a co-designed architecture for quantum optimization in which embedding, computation, and error correction emerge from the same physical structure.

Gadget embeddings allow Rydberg-array optimizers to represent non-native interaction graphs but introduce auxiliary atoms. This paper asks whether that redundancy can support error correction without additional hardware. It treats parity-architecture Rydberg embeddings as nonlinear classical codes: valid configurations contain exactly one excitation in each overlapping dimer or trimer “superatom,” so local excitation counts provide error syndromes. A Cluster decoder groups violated constraints, propagates uniquely determined gadget configurations from fixed boundaries, and grows or merges unresolved regions. For the two-dimensional layouts considered, its estimated worst-case runtime is $\mathcal{O}(N^3)$ for $N$ logical variables and $\mathcal{O}(N^2)$ atoms. Simulations with independent symmetric readout bit flips show finite-size crossings near $p_{\mathrm{th}}=0.275$ for complete-graph embeddings and $0.263$ for bipartite embeddings; these estimates use the two largest simulated sizes. The minimum code distance grows linearly with logical size. Extensions to crossing-lattice and quantum-wire embeddings are also examined. Experiments on QuEra Aquila use fixed $4\,\mu\mathrm{s}$ anneals and layouts containing up to 107 atoms. After post-selection on fully loaded arrays, decoding recovers exact optimization solutions with an average success rate of at least approximately $8\%$ at the largest size, where raw samples and the tested greedy post-processing recover none. The correction is classical post-processing, not active quantum error correction. Decoding can fail or return a different valid codeword. Experimental noise is correlated, asymmetric, and potentially size-dependent; experimental success still decreases with size. Extension to unstructured layouts and an additional crossing in the quantum-wire simulations remain unresolved.