Breakthrough! Neutral-atom quantum computing enables universal coding with lower overhead
In a new development at QuEra Computing, a Harvard-MIT-derived neutral-atom quantum computing company, researchers and collaborators have developed a universal encoding blueprint that can be used to optimize arbitrary connectivity problems on arrays of neutral atoms.
Combinatorial optimization to find an optimal solution from a large number of discrete solutions has common applications in many fields of science and technology. However, similar problems are computationally difficult for classical algorithms and belong to the NP-hard complexity class: the quest to solve these difficult problems is one of the main topics of modern quantum information science.
In May of this year, the research in which QuEra participated, "Quantum optimization of the largest independent set using the Reedeburg atomic array", has been published in the journal Science. which used a neutral atom quantum processor with 289 (17×17 array) quantum bits.
01Riedberg atomic arrays, encoding solutions to optimization problems
In the last two decades, various quantum algorithms have been proposed: for example, the Quantum Adiabatic Algorithm (QAA) and the Quantum Approximate Optimization Algorithm (QAOA). The core of these approaches often involves encoding the solution of the optimization problem into a tunable ground state of quantum Hamiltonian quantities; thus, the efficient encoding of physically realizable quantum Hamiltonian quantities poses a practical challenge.
Recently, Riedberg atomic arrays were shown to encode a class of combinatorial optimization problems with maximum independent sets (MIS) on geometrical graphs - unitary disk graphs (UDG) - and higher superlinear quantum speeds than optimized classical simulated annealing methods were observed. For the UDG, the encoding using Riedberg atoms is overhead-free, since each vertex of the graph can be represented by an atom and the hardware connections correspond directly to the unit disk connections. For this experiment, the team extended this approach to a wider range of optimization problems: including the maximum weight independent set (MWIS) problem on arbitrary graphs, quadratic unconstrained binary optimization (QUBO), the Ising problem, and typical problems such as integer decomposition; all elements have been shown to be implementable on the current Reedeburg atom array platform.
Various optimization problems are solved using programmable Riedberg atom arrays. The original computational problem (a) can be mapped to the maximum weight independent set (MWIS) problem on the unit disc graph (UDG) in (b). The physical platform in (c), each vertex in (b) represents an atom captured by the optical tweezers. Each two-energy atom can be coherently driven with Rabi frequency Ω and detuned ∆. If two atoms are within unit distance, the Riedberg blocking mechanism prevents them from being excited to state |1⟩ at the same time. (d) The solution of the UDG-MWIS problem encodes the solution of the original problem.
For implementation on a quantum computer, it is extremely important to find a low-overhead explicit mapping, which is the key goal of this experiment. Extending the applicability of Riedberg atomic arrays beyond UDGs, they are either restricted to specific graph classes or require three-dimensional arrays. Other schemes that map arbitrary nonlocal interactions to local interactions are experimentally more demanding and require 4-body interactions [2] or tunable Ising interactions [3]. In contrast, the present scheme relies only on Riedberg blocking and requires only a 2-D array; therefore, it can be easily implemented in the present Riedberg atomic array experiment.
02Three major coding cases, MWIS problem mapping on UDG
The main result of this work is that, given a computational problem, it is possible to map it to a UDG-MWIS problem (i.e., a MWIS problem on UDG) using a new encoding scheme. The resulting UDG-MWIS is a local problem for the Reedeburg Atomic Array platform, allowing a direct implementation of QAA or QAOA to solve it: a general framework for low overhead, efficient and explicit mappings will be provided. The following figure summarizes the three examples discussed in detail in this work.
UDG-MWIS mappings for three example problems. (a) Non-UDG examples on MWIS and quadratic unconstrained binary optimization (QUBO) problems denoted by G = (V, E). (b) The crossed grid used to construct the UDG-MWIS mapping. The vertices in (a) are binary variables that can be effectively represented by lines to construct the grid. The intersection points in the grid allow arbitrary connections between variables, abstractly represented as squares. The grid mimics the upper triangular adjacency matrix A. For two vertices {v, w} ∈ V, Avw = 1 if (v, w) ∈ E and Avw = 0 otherwise, which are abstractly represented here by filled and empty squares, respectively. (c) Final UDG-MWIS representation of the original MWIS problem on the general graph. (d) Final UDG-MWIS representation of the original QUBO/Ising problem. (e), (f), (g) Similar encoding procedure for the 6=2×3 integer decomposition problem, and the corresponding UDG-MWIS representation.
03The next step of exploration: higher-order multivariate problem computation
In this work, the research team describes an encoding strategy that maps various computational problems with arbitrary connectivity to maximum weighted independent set problems on unit disc graphs that are implemented in quantum optimization of neutral atoms interacting via Riedberg states. The encoding is very efficient as it generates at most four overheads in the number of variables of the optimization problem. Furthermore, the mapping follows an explicit and straightforward procedure: it generates a unit disc map that can be embedded on a square lattice with favorable conditions for the necessary unit disc radius and can therefore be practically implemented by means of an array of Riedberg atoms.
In addition to this, the team provides three specific examples of problem mapping: the MWIS problem on an arbitrarily connected general graph, the QUBO problem, and the integer decomposition problem. Numerical simulations show that the performance of the quantum algorithm on the mapping problem is directly related to the performance of the original problem, suggesting that any quadratic quantum acceleration in the original graph can be transferred to an equivalent acceleration on the unit disc graph.
In the future, the following directions deserve further exploration: first, the approach can be extended to computational problems involving the interaction of three or more variables, such as the high-order unconstrained binary optimization (HUBO) problem; it is also interesting to consider encoding methods beyond two-dimensional geometry: for example, generalizing the concept of crossed lattices to a three-dimensional "crossed cube" For example, the concept of crossed lattices can be generalized to "crossed cubes" in three dimensions; one can design coding methods with lower overhead in three dimensions.
Reference links：
[1]https://arxiv.org/abs/2209.03965
[2]https://www.science.org/doi/10.1126/sciadv.1500838
[3]https://journals.aps.org/prxquantum/abstract/10.1103/PRXQuantum.1.020311
