There is a significant ongoing effort in realizing quantum annealing with different physical platforms. The challenge is to achieve a fully programmable quantum device featuring coherent adiabatic quantum dynamics. Here we show that combining the well-developed quantum simulation toolbox for Rydberg atoms with the recently proposed Lechner-Hauke-Zoller (LHZ) architecture allows one to build a prototype for a coherent adiabatic quantum computer with all-to-all Ising interactions and, therefore, a platform for quantum annealing. In LHZ an infinite-range spin-glass is mapped onto the low energy subspace of a spin-1/2 lattice gauge model with quasi-local four-body parity constraints. This spin model can be emulated in a natural way with Rubidium and Caesium atoms in a bipartite optical lattice involving laser-dressed Rydberg-Rydberg interactions, which are several orders of magnitude larger than the relevant decoherence rates. This makes the exploration of coherent quantum enhanced optimization protocols accessible with state-of-the-art atomic physics experiments.
There is a significant ongoing effort in realizing quantum annealing with different physical platforms. The challenge is to achieve a fully programmable quantum device featuring coherent adiabatic quantum dynamics. Here we show that combining the well-developed quantum simulation toolbox for Rydberg atoms with the recently proposed Lechner-Hauke-Zoller (LHZ) architecture allows one to build a prototype for a coherent adiabatic quantum computer with all-to-all Ising interactions and, therefore, a platform for quantum annealing. In LHZ an infinite-range spin-glass is mapped onto the low energy subspace of a spin-1/2 lattice gauge model with quasi-local four-body parity constraints. This spin model can be emulated in a natural way with Rubidium and Caesium atoms in a bipartite optical lattice involving laser-dressed Rydberg-Rydberg interactions, which are several orders of magnitude larger than the relevant decoherence rates. This makes the exploration of coherent quantum enhanced optimization protocols accessible with state-of-the-art atomic physics experiments.
Critical decision-making issues in science, engineering, and industry are based on combinatorial optimization; however, its application is inherently limited by the NP-hard nature of the problem. A specialized paradigm of analogue quantum computing, quantum annealing (QA), has been proposed to solve these problems by encoding optimization problems into physical energy landscapes and solving them by quantum tunnelling systematically through exploration of solution space. This is a critical review that summarizes the current applications of quantum annealing to combinatorial optimization and includes a theoretical background, hardware designs, algorithm implementation strategies, encoding and embedding schemes, protocols to benchmark quantum annealing, areas of implementation, and links with the quantum algorithms implementation with gate-based hardware and classical solvers. We develop a unified framework, relating adiabatic quantum dynamics, Ising and QUBO models, stoquastic and non-stoquastic Hamiltonians, and diabatic transitions to modern flux-qubit annealers (Chimera, Pegasus, Zephyr topologies), and emergent architectures (Lechner-Hauke-Zoller systems, Rydberg atom platforms), and hybrids of quantum and classical computation. Through our analysis, we find that overhead in embedding and encoding is the largest determinant of the scalability and performance (this is not just the number of qubits). Minor embeddings also usually have a physical qubit count per logical variable of between 5 and 12 qubits, which limits effective problem capacity by 80-92% and, due to chain-breaking errors, compromises the quality of solutions.
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.
Quantum annealing aims at solving optimization problems efficiently by preparing the ground state of an Ising spin-Hamiltonian quantum mechanically.A prerequisite of building a quantum annealer is the implementation of programmable long-range two-, three-, or multispin Ising interactions.We discuss an architecture, where the required spin interactions are implemented via two-port or in general multiport quantum Ising wires connecting the spins of interest.This quantum annealing architecture of spins connected by Ising quantum wires can be realized by exploiting the three-dimensional (3D) character of atomic platforms, including atoms in optical lattices and Rydberg tweezer arrays.The realization only requires engineering on-site terms and two-body interactions between nearest neighboring qubits.The locally coupled spin model on a 3D cubic lattice is sufficient to effectively produce arbitrary all-to-all coupled Ising Hamiltonians.We illustrate the approach for few-spin devices solving Max-Cut and prime factorization problems, and discuss the potential scaling to large atom-based systems.
We study an architecture for implementing adiabatic quantum computation with trapped neutral atoms. Ground-state atoms are dressed by laser fields in a manner conditional on the Rydberg blockade mechanism, thereby providing the requisite entangling interactions. As a benchmark, we study the performance of quantum annealing to the ground state of an Ising spin lattice. We model a proof-of-principle experiment in a realistic architecture, including details of the atomic implementation, with qubits encoded in the clock states of 133Cs. Numerical simulation yields fidelities >0.98 for up to four qubits, and implementations of 10--20 qubits are within the range of current technology.
In a recent paper Lechner, Hauke and Zoller (LHZ) described a means to translate a Hamiltonian of N spin-21 particles with `all-to-all' interactions into a larger physical lattice with only on-site energies and local parity constraints. LHZ used this mapping to propose a novel form of quantum annealing. Here we provide a stabiliser-based formulation of this approach, which permits some generalisation to the parity constraints proposed by LHZ. One variant we obtain may simplify the physical realisation since the required ancillas are only spin-21 systems (i.e.~qubits, rather than qutrits) and moreover the interactions {are} very simple. We make a preliminary assessment of the impact of different design choices by simulating small (few-qubit) systems; we find some indications that the new variant may maintain a larger minimum energy gap during the annealing process.
Abstract Quantum Ising models are canonical models for the study of quantum phase transitions (Sachdev 1999 Quantum Phase Transitions (Cambridge: Cambridge University Press)) and are the underlying concept for many analogue quantum computing and quantum annealing ideas (Tanaka et al Quantum Spin Glasses, Annealing and Computation (Cambridge: Cambridge University Press)). Here we focus on the implementation of finite-range interacting Ising spin models, which are barely tractable numerically. Recent experiments with cold atoms have reached the interaction-dominated regime in quantum Ising magnets via optical coupling of trapped neutral atoms to Rydberg states. This approach allows for the tunability of all relevant terms in an Ising spin Hamiltonian with 1 / r 6 interactions in transverse and longitudinal fields. This review summarizes the recent progress of these implementations in Rydberg lattices with site-resolved detection. Strong correlations in quantum Ising models have been observed in several experiments, starting from a single excitation in the superatom regime up to the point of crystallization. The rapid progress in this field makes spin systems based on Rydberg atoms a promising platform for quantum simulation because of the unmatched flexibility and strength of interactions combined with high control and good isolation from the environment.