Quantum Optimization with Arbitrary Connectivity Using Rydberg Atom Arrays

Programmable quantum systems based on Rydberg atom arrays have recently been used for hardware-efficient tests of quantum optimization algorithms [Ebadi et al., Science, 376, 1209 (2022)] with hundreds of qubits. In particular, the maximum independent set problem on so-called unit-disk graphs, was shown to be efficiently encodable in such a quantum system. Here, we extend the classes of problems that can be efficiently encoded in Rydberg arrays by constructing explicit mappings from a wide class of problems to maximum-weighted independent set problems on unit-disk graphs, with at most a quadratic overhead in the number of qubits. We analyze several examples, including maximum-weighted independent set on graphs with arbitrary connectivity, quadratic unconstrained binary optimization problems with arbitrary or restricted connectivity, and integer factorization. Numerical simulations on small system sizes indicate that the adiabatic time scale for solving the mapped problems is strongly correlated with that of the original problems. Our work provides a blueprint for using Rydberg atom arrays to solve a wide range of combinatorial optimization problems with arbitrary connectivity, beyond the restrictions imposed by the hardware geometry.

Popular Summary

Programmable quantum systems offer unique possibilities to test the performance of various quantum optimization algorithms. Some of the main practical limitations in this context are often set by specific hardware restrictions. In particular, the native connectivity of the qubits for a given platform typically restricts the class of problems that can addressed. For instance, Rydberg atom arrays naturally allow encoding maximum independent set problems, but native encodings are restricted to so-called unit disk graphs.

In this work we significantly expand the class of problems that can be addressed with Rydberg atom arrays, overcoming the limitations to geometric graphs. We develop a specific encoding scheme to map a variety of problems into arrangements of Rydberg atoms, including maximum weighted independent sets on graphs with arbitrary connectivity, quadratic unconstrained binary optimization problems with arbitrary or restricted connectivity, and integer factorization. Our work thus provides a blueprint for using Rydberg atom arrays to solve a wide range of combinatorial optimization problems, using technology already available in experiments.

Figure 1

Procedure to solve a variety of optimization problems using programmable Rydberg atom arrays. The original computational problem (a) can be mapped onto a MWIS problem on a UDG in (b). (c) Physical platform, where each vertex in (b) represents an atom trapped by optical tweezers. Each two-level atom can be coherently driven with Rabi frequency $\mathrm{\Omega }$ and detuning $\mathrm{\Delta }$, and the Rydberg-blockade mechanism prevents two atoms from being simultaneously excited to state $|1⟩$ if they are within a unit distance $r_B$. (d) The solution to the UDG-MWIS problem encodes the solution to the original problem.

Figure 2

Architecture of UDG-MWIS mapping for three example problems. (a) Example non-UDG represented by $G=(V,E)$ for the MWIS and QUBO problems. (b) Crossing lattice used to construct UDG-MWIS mappings. Vertices in (a) are binary variables that can be represented effectively by lines to construct the lattice. Intersections in the lattice allow arbitrary connectivity between the variables, abstractly represented by squares. The lattice mimics an upper triangular adjacency matrix $A$, where for two vertices $\{v,w\}\in V$, $A_{vw}=1$ if $(v,w)\in E$ and $A_{vw}=0$ otherwise, represented abstractly by a filled and empty square here, respectively. (c) Final UDG-MWIS representation of the original MWIS problem on general graphs. (d) Final UDG-MWIS representation of the original QUBO and Ising problem. (e),(f),(g) Similar encoding procedure for the integer factorization problem for the example $6=2\times 3$, with the corresponding UDG-MWIS representation shown in (g).

Figure 3

MWIS representation of some example constraints. Each bit is represented by a corresponding vertex in the MWIS problem graph. The weight of the vertices is indicated by its interior color on a gray scale. For each example, the degenerate MWIS configurations are shown by identifying vertices in a MWIS with a red boundary. The MWISs correspond to the satisfying assignments to the corresponding constraint-satisfaction problem. (a) MWIS representation of $n_1=\overline{n_2}$. (b) MWIS representation of $n_1{n}_2=0$, with the third, unlabeled vertex being an ancillary vertex. For each of the three MWIS states, the configuration on the relevant vertices 1 and 2 matches the corresponding satisfying assignment. (c) MWIS representation of the NOR constraint using two ancilla vertices. Note that only four of the five MWIS states are shown. Nevertheless, all five MWIS states correspond to the four satisfying assignments on the relevant vertices 1, 2, and 3. (d) A set of constraints $C=\{n_1=\overline{n_2},n_2{n}_3=0\}$, where each is of the form given in (a),(b). The corresponding MWIS problem is obtained by combining the two graphs corresponding to both constraints in $C$, resulting in the weighted graph on the right. Observe that vertex $2$, which appears in both constraints, has twice the weight of the other vertices.

Figure 4

Important gadgets for formulating constraint-satisfaction problems as UDG-MWIS. (a) Copy gadget. A 1D line graph encodes an effective bit. The two degenerate MWIS solutions are shown: the subset of odd-numbered vertices (top) and even-numbered vertices (bottom) represent the effective bit values $1$ and $0$, respectively. In this way, one can copy a single bit to any odd-numbered vertex. (b) Crossing gadget. The four degenerate MWIS solutions of the left graph coincide with the four MWIS solutions on the right graph on vertices $1,2,3,4$. One of these solutions is shown. Given a graph that contains a crossing, we can thus replace it with the right UDG, without changing the structure of the MWIS solution. (c) Crossing-with-edge gadget. Similar to (b), we can replace any subgraph of the type depicted on the left with the UDG on the right. One can check the MWIS solutions have one-to-one correspondence. The weights in (a)–(c) are encoded in grayscale according to the legend at the bottom of the figure.

Figure 5

(a) Two decoupled effective degrees of freedom. By combining the copy gadget and the crossing gadget, we can form two 1D lines, here drawn horizontally and vertically. Both lines represent a binary variable, $n_h\in \{0,1\}$ and $n_v\in \{0,1\}$, respectively. The crossing gadget effectively decouples these degrees of freedom. Accordingly, this weighted graph has a fourfold degenerate MWIS, corresponding to the four possible states of two binary variables. One of the MWISs is shown in red corresponding to $n_h=0$ and $n_v=1$. Note that each of the four MWISs contains exactly one of the four internal vertices of the crossing gadget, so these internal vertices encode the states of both effective degrees of freedom. (b) Two effective degrees of freedom, defined on a horizontal and a vertical line, respectively, that satisfy an independence constraint $n_h{n}_v=0$, introduced by the crossing-with-edge gadget [Fig. 4]. Note that this graph has exactly three degenerate MWIS (out of which, one is shown in red), corresponding to the configurations $(n_h,n_v)\in \{(0,0),(0,1),(1,0)\}$.

Figure 6

Example encoding procedure for the MWIS problem on the $K_{2,3}$ (non-unit-disk) graph into UDG-MWIS. (a) Crossing lattice. Each vertex $v$ is represented by a line using the copy gadget, with odd-numbered vertices labeled. Each line is bent to form a triangular lattice, giving a crossing point between any two variables. If the two variables share an edge in the original graph, we draw an edge between their representative vertices on the lattice. A UDG is then obtained by replacing each crossing with a crossing or crossing-with-edge gadget. (b) UDG representation and the corresponding ground-state solution. Each crossing in (a) is replaced with a unit cell containing at most eight vertices, thus resulting in a final mapping with 92 vertices. The MWIS of the original graph ($\{2,4,5\}$) can be read out from the boundary vertices of the ground state of the mapped graph. This mapping can further be simplified (see Fig. 10) to a mapping of only nine vertices, where the vertices corresponding to the original degrees of freedom still encode the desired MWIS solution.

Figure 7

Example encoding procedure for the QUBO and Ising problem for a 5-bit system. (a) Crossing lattice. Similar to the MWIS mapping, we can construct the UDG-MWIS representation of a generic QUBO problem by inserting a gadget at each crossing. The gadget has a similar structure as the crossing gadget used in the MWIS encoding, but the weights on the ancillary vertices are biased to induce quadratic interaction terms $w_{ij}$ between the effective degrees of freedom; see (b). (c) Example of an encoded $N=5$ QUBO problem, and the high-weight spectrum of the encoded cost function, illustrating that the MWIS is indeed in the 0-defect sector and thus encodes the solution of the QUBO problem. The QUBO solution $\{-1,+1,+1,+1,+1\}$ is encoded in the boundary of the graph.

Figure 8

Encoding procedure for integer factorization. (a) Graphical representation of the set of equations to be satisfied for integer factorization ($m=p\cdot q$). The factor bits $p_i,q_i$ and binary variables $s_{i,j},c_{i,j}$ are represented by copy lines to construct an effective square crossing lattice for the problem, with a filled square at crossings and the integer bits $m_i$ specifying some of the boundary conditions of the problem. (b) Each filled square represents a set of equality constraints between the binary variables associated with the adjacent legs. The final UDG-MWIS can be obtained by replacing each square with the factoring gadget that enforces the mathematical constraints relevant for the factoring problem. The unit-disk radius should be slightly larger than $2\sqrt{2}$ times the lattice constant. (c) An example of the UDG-MWIS representation of the factoring problem $6=3\times 2$.

Figure 9

QAA performance for MWIS on original and mapped graphs. (a) Example unit-disk mapping and MIS configuration of a six-vertex graph. The original graph (left) is unweighted, and the mapped graph is a weighted UDG (right). The corresponding vertices are labeled with numbers. (b) i. Rabi frequency $\mathrm{\Omega }(t)$ and detuning $\mathrm{\Delta }(t)$ sweep used in the QAA protocol. The global detuning $\mathrm{\Delta }(t)$ is shown in solid red, while $2\mathrm{\Delta }(t)$ and $3\mathrm{\Delta }(t)$ are shown in dashed lines. ii. Computed $P_{\mathrm{MIS}}$ for the original and mapped graphs as a function of total sweep time $T$. The adiabatic timescale $T_{\mathrm{LZ}}$, which is related to the minimum energy gap, is extracted from the long-time Landau-Zener fitting. (c) Scaling of $T_{\mathrm{LZ}}$ for mapped graphs for the ensemble of unweighted nonisomorphic graphs with size $N=6$.

Figure 10

(a)–(c) Simplification techniques to reduce the overhead. Vertex reordering can be used to reduce the depth of the crossing lattice. (d) Final mapping of the $K_{2,3}$ graph after bipartition and vertex reordering, reducing the overhead mapping from 92 nodes to 9 [see Fig. 6]. (e) MWIS overhead scaling as a function of the number of vertices of original randomly generated graphs for chosen graph classes using a greedy pathwidth reduction algorithm.

Figure 11

An example 2D restricted-connectivity graph and reduction to UDG-MWIS. (a) A particular topology of bits (vertices) and quadratic terms (edges). The original graph can be mapped into a UDG-MWIS using some gadgets. (b) Two bits can be represented by a clique of four vertices, with each state $(\pm \pm )$ represented by a single vertex of the clique. Linear and quadratic interactions are represented by biasing the weights of the clique. (c) Interactions between neighbors can be represented by adding ancilla vertices. (d) The original restricted-connectivity QUBO problem as mapped to a UDG-MWIS problem, where the ground state encodes the solution to the QUBO problem. Here, quadratic QUBO weights are chosen to be $\pm J$. This example graph has 50 bits in the original graph and an extent of $13\times 13$ in the mapped UDG graph, which naturally fits onto today’s Rydberg atom array hardware.

Figure 12

The two basic components of the factoring gadget. The gadget in (a) is a crossing gadget. Besides its use in routing effective variables $a$ and $b$, it also serves as a tool to access the value of the product of the variables, $z=ab$, at the indicated interior vertex. The gadget in (b) is the MWIS representation of the constraint $z+c+d=2e+f$.