| dc.description.abstract | 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(n^2)$ 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(n^2)$ 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. | |
