We discuss the computational complexity of finding the ground state of the two-dimensional array of quantum bits that interact via strong van der Waals interactions. Specifically, we focus on systems where the interaction strength between two spins depends only on their relative distance $x$ and decays as $1/x^6$ that have been realized with individually trapped homogeneously excited neutral atoms interacting via the so-called Rydberg blockade mechanism. We show that the solution to NP-complete problems can be encoded in ground state of such a many-body system by a proper geometrical arrangement of the atoms. We present a reduction from the NP-complete maximum independent set problem on planar graphs with maximum degree three. Our results demonstrate that computationally hard optimization problems can be naturally addressed with coherent quantum optimizers accessible in near term experiments.
We discuss the computational complexity of finding the ground state of the two-dimensional array of quantum bits that interact via strong van der Waals interactions. Specifically, we focus on systems where the interaction strength between two spins depends only on their relative distance x and decays as 1/x6 that have been realized with individually trapped homogeneously excited neutral atoms interacting via the so-called Rydberg blockade mechanism. We show that the solution to NP-complete problems can be encoded in ground state of such a many-body system by a proper geometrical arrangement of the atoms. We present a reduction from the NP-complete maximum independent set problem on planar graphs with maximum degree three. Our results demonstrate that computationally hard optimization problems can be naturally addressed with coherent quantum optimizers accessible in near term experiments.
We describe and analyze an architecture for quantum optimization to solve maximum independent set (MIS) problems using neutral atom arrays trapped in optical tweezers. Optimizing independent sets is one of the paradigmatic, NP-hard problems in computer science. Our approach is based on coherent manipulation of atom arrays via the excitation into Rydberg atomic states. Specifically, we show that solutions of MIS problems can be efficiently encoded in the ground state of interacting atoms in 2D arrays by utilizing the Rydberg blockade mechanism. By studying the performance of leading classical algorithms, we identify parameter regimes, where computationally hard instances can be tested using near-term experimental systems. Practical implementations of both quantum annealing and variational quantum optimization algorithms beyond the adiabatic principle are discussed.
We describe an architecture to map the Ising model problem onto the dynamics of two-dimensional neutral trapped atom arrays. Specifically, we show that the NP-complete Ising model decision problem on n variables can be reduced to deciding whether, for O(n2) Rubidium atoms in two dimensions, interacting via Rydberg excitations, there exists a state with energy below a certain threshold. This provides an alternative proof of the NP-hardness of two dimensional Rydberg dynamics with a single species in the regime where long-range interactions are negligible. Therefore, we can encode NP-complete problems onto the ground state of Rydberg atom arrays and use quantum optimization techniques such as quantum adiabatic algorithms and variational algorithms to estimate the ground state. Furthermore, as the Ising model describes many-body phenomena in statistical physics, we can probe a plethora of emergent phenomena via quantum simulators. Our result is based on the Lechner-Hauke-Zoller (LHZ) scheme that enables the encoding of an all-to-all connected Ising model onto systems with local-only interactions. We improve the scheme in the following ways to make the it feasible for near-term Rydberg simulators: (1) Implementations of the scheme in literature that use qubits suffer from a double-counting error causing inconsistencies in the strength of the interactions. Identical interactions must have different strengths based on their spatial location. We describe and resolve this error without impacting the O(n2) scaling of the atom array by introducing additional ancillary qubits. (2) We introduce new formalism and simpler proofs via novel approaches regarding the validity of the LHZ scheme and its variants. These proofs lend more easily to complexity-theoretic arguments regarding the hardness of Rydberg dynamics. (3) Finally, we circumvent the LHZ scheme constraint of requiring four-body interactions, qutrits, or multiple species of atoms by providing an implementation that uses only Rubidium atoms to encode both physical and ancillary qubits. To engineer the required interactions, the atoms are coupled to different Rydberg energy levels. We also provide a brief review of classical and quantum computation, quantum computing platforms, near-term quantum experiments, and Rydberg physics.
We study the Rydberg blockade in a system of three atoms arranged in different two-dimensional geometries (linear and triangular configurations). In the strong blockade regime, we observe high-contrast, coherent collective oscillations of the single excitation probability and an almost perfect van der Waals blockade. Our data are consistent with a total population in doubly and triply excited states below 2%. In the partial blockade regime, we directly observe the anisotropy of the van der Waals interactions between |nD> Rydberg states in the triangular configuration. A simple model that only uses independently measured two-body van der Waals interactions fully reproduces the dynamics of the system without any adjustable parameter. These results are extremely promising for scalable quantum information processing and quantum simulation with neutral atoms.
Realizing quantum speedup for practically relevant, computationally hard problems is a central challenge in quantum information science. Using Rydberg atom arrays with up to 289 qubits in two spatial dimensions, we experimentally investigate quantum algorithms for solving the maximum independent set problem. We use a hardware-efficient encoding associated with Rydberg blockade, realize closed-loop optimization to test several variational algorithms, and subsequently apply them to systematically explore a class of graphs with programmable connectivity. We find that the problem hardness is controlled by the solution degeneracy and number of local minima, and we experimentally benchmark the quantum algorithm's performance against classical simulated annealing. On the hardest graphs, we observe a superlinear quantum speedup in finding exact solutions in the deep circuit regime and analyze its origins.
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 pth≳26% across different layout geometries. Experimentally, on the QuEra Aquila QPU, the Cluster decoder recovers exact optimization solutions with an average success rate of ≳8% 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.
Programmable quantum systems provide insights into many-body quantum phenomena and enable new methods for computation and metrology. The frontier challenge for these systems is scaling up in the number of quantum particles while retaining a high degree of quantum control. In recent years arrays of neutral atoms have emerged as a scalable and powerful platform for tackling these challenges, thanks to their large number of qubits, flexible geometry, and a well-established toolbox for preparation, detection, coherent control. At the forefront of quantum science and engineering, these systems have been used for quantum simulation of various spin models and have also demonstrated building blocks of quantum computation. In this thesis I will present advances in development of large two-dimensional atom arrays, where hundreds of individual atoms are trapped, rearranged, and initialized in various defect-free arrangements in one or two dimensions. Afterwards, interactions between atoms is controlled via coherent excitation to highly excited Rydberg states, resulting in strong long-range van der Waals forces. We utilize these interaction for quantum simulation of many-body spin Hamiltonians by demonstrating preparation of several exotic phases of matter, study phase transitions, and probe non-equilibrium dynamics. Further, we study the quantum speedup in solving a hard combinatorial optimization problem via efficiently mapping the problem onto the Rydberg atom array. We also utilize Rydberg interactions to demonstrate high-fidelity two-qubit gate operations in a reconfigurable atom array architecture. Lastly I will demonstrate recent technical improvements that have enabled larger system sizes, higher fidelity rydberg excitations, and local control of individual atoms, paving the way for novel approaches for studying quantum many-body phenomena.