PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum optimization with arbitrary connectivity using Rydberg atom arrays

Minh-Thi Nguyen, Jin-Guo Liu, Jonathan Wurtz, Mikhail D. Lukin, Sheng-Tao Wang, Hannes Pichler

arXiv:2209.03965v2quant-phcond-mat.dis-nncond-mat.quant-gascs.CCphysics.atom-ph

TL;DR

Rydberg arrays efficiently encode independent-set problems on unit-disk graphs, but their geometric restriction limits the range of directly encodable problems. This paper maps broadly connected optimization problems to unit-disk-graph MWIS with at most quadratic overhead; small-system simulations report correlated adiabatic timescales for original and mapped MWIS problems.

  • Problem

    The unit-disk-graph restriction limits the applicability of Rydberg-array optimization to problems with broader connectivity.

    Source: §I · p. 2

  • Method

    A crossing-lattice construction with encoding gadgets maps general-graph MWIS, arbitrary-connectivity QUBO/Ising, and integer factorization into UDG-MWIS with at most O(N^2) overhead.

    Source: §II · p. 2

  • Results

    Numerical simulations on small systems indicate strong correlation between adiabatic timescales for original non-UDG MWIS problems and their mapped counterparts.

    Source: §VI · p. 12

  • Takeaways & Limitations

    The explicit mapping provides a blueprint for encoding a range of arbitrary-connectivity computation problems in Rydberg atom arrays.

    Source: §VII · p. 13

Abstract

from arXiv · show

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.

I. INTRODUCTION

Rydberg arrays naturally encode maximum independent set on unit-disk graphs, but that geometric restriction limits the problems directly accessible to the hardware. The paper presents a systematic mapping from broadly connected problems to unit-disk-graph MWIS, with at most quadratic qubit overhead, and reports correlated adiabatic timescales in small simulations.

I. INTRODUCTION

  • Rydberg blockade directly supports independent-set encoding on unit-disk graphs, but that graph restriction limits applicability to broader optimization problems.Earlier extensions were described as graph-specific or requiring three-dimensional arrays, while other approaches demand more experimentally challenging interactions.Source: §I · pp. 1–2
  • Small-system simulations find strong correlation between adiabatic timescales for original non-UDG MWIS problems and their mapped counterparts.The authors note the limited data range prevents reliable fitting.Source: §I · p. 2

II. OVERVIEW OF MAIN RESULTS

  • The mapping covers general-graph MWIS, arbitrary-connectivity QUBO/Ising, and integer factorization, with at most O(N^2) qubit overhead.The authors describe the overhead as optimal for arbitrary connectivity.Source: §II · p. 2
  • A crossing lattice and copy, crossing, and crossing-with-edge gadgets encode pairwise interactions while producing a unit-disk graph whose MWIS represents the original problem.For factoring, a factoring gadget maps an optimization formulation of the factorization task into UDG-MWIS.Source: §II · p. 2

A. Rydberg Atom Arrays

Rydberg blockade penalizes nearby atoms being simultaneously excited, yielding the independent-set constraint that underlies the hardware encoding. With vertex weights represented by detunings, the classical-limit ground state of a unit-disk-graph array corresponds to a maximum-weight independent set, subject to the stated interaction-tail approximation.

A. Rydberg Atom Arrays

  • At Ω = 0, the Rydberg blockade imposes the independent-set constraint on low-energy states by penalizing nearby atoms that are simultaneously excited.The blockade radius is defined by V_Ryd(r_B) = max_v(∆_v) in this classical limit.Source: A. Rydberg Atom Arrays · p. 4

B. Unit Disk Graphs

  • A unit-disk graph connects vertices exactly when their planar separation is below the unit radius, matching atom positions when the blockade radius is identified with that radius.Each atom represents a graph vertex; low-energy configurations at Ω_v = 0 correspond to large independent sets.Source: B. Unit Disk Graphs · p. 4

C. Maximum Weight Independent Sets

  • For UDG-MWIS, the array Hamiltonian at Ω = 0 matches the MWIS Hamiltonian when each local detuning equals its vertex weight and interaction tails beyond the blockade radius are neglected.Under these conditions, the ground state represents the MWIS.Source: C. Maximum Weight Independent Sets · p. 4

IV. ENCODING GADGETS

The paper constructs weighted-graph gadgets whose maximum-weight independent sets represent satisfying assignments, including when auxiliary vertices are needed. Combining such gadgets provides a route from elementary constraints toward UDG-MWIS encodings.

A. Constraint Satisfaction Problems as MWIS

  • Constraint-satisfaction problems are represented by weighted graphs whose MWIS configurations correspond to satisfying assignments on the problem variables.The graph may contain extra vertices, so the correspondence is required only on vertices representing the original variables.Source: A. Constraint Satisfaction Problems as… · p. 4

1. Single Constraints

  • For n1 = n2, two equally weighted adjacent vertices have degenerate MWIS states matching the two satisfying assignments.Violations incur at least the minimum energy penalty δgap = min(U − δ, δ) > 0.Source: §1 · p. 5
  • The constraint n1n2 = 0 is represented by a three-vertex complete graph, with one ancillary vertex and three degenerate MWIS states matching assignments on the two relevant bits.The paper also notes that a NOR gadget represents basic Boolean operations.Source: §1 · p. 5

2. Conjunction of Constraints

Combining individual constraint encodings yields an MWIS representation of their conjunction; the paper also introduces gadgets for transforming general graphs into unit-disk graphs.

2. Conjunction of Constraints

  • The conjunction is encoded by taking the union of the individual constraint graphs and adding their vertex weights, so ground states correspond to satisfying assignments.The example combines two constraint encodings and recovers the satisfying assignments on vertices 1, 2, and 3.Source: §2 · pp. 5–6
  • Combining NOT and NOR constraints is universal, allowing any circuit satisfiability problem to be encoded as MWIS with constant overhead.Source: §2 · p. 6

B. Gadgets for Unit Disk Transformation

1. Copy Gadget and Effective Bits

Copy gadgets represent an effective bit along a unit-disk line, while crossing gadgets let such lines intersect without coupling their encoded variables.

1. Copy Gadget and Effective Bits

  • A copy gadget is a weighted one-dimensional chain whose two staggered MWIS configurations encode effective bit values 1 and 0.The bit is copied to odd-indexed vertices and can be accessed where needed along the line.Source: §1 · p. 6, Figure 4 · p. 6
  • An effective weight can be assigned by biasing an odd-indexed vertex, provided the weights keep defect states below the two valid staggered configurations.Source: §1 · pp. 6–7

2. Crossing Gadget

  • The crossing gadget replaces crossing constraints with a unit-disk graph whose four MWIS configurations correspond to the four assignments of the original variables.Combined with copy gadgets, it lets effective binary variables occupy crossing lines without interactions between them.Source: §2 · p. 7, Figure 5 · p. 7

3. Crossing-with-edge Gadget

The crossing-with-edge gadget introduces an independence constraint between effective variables whose lines cross; the broader construction uses these gadgets to encode arbitrary-connectivity problems as UDG-MWIS.

3. Crossing-with-edge Gadget

  • The crossing-with-edge gadget replaces a non-unit-disk crossing with a unit-disk graph whose three MWIS configurations satisfy the required independence constraint.The allowed effective-variable assignments are (0, 0), (0, 1), and (1, 0).Source: §3 · pp. 7–8

V. ARBITRARY CONNECTIVITY

  • The paper applies copy, crossing, and crossing-with-edge gadgets to encode arbitrary-connectivity problems as UDG-MWIS for Rydberg atom arrays.Source: §V · p. 8

A. The Crossing Lattice

The crossing lattice and its replacement gadgets map general-graph MWIS and QUBO problems to UDG-MWIS, with quadratic-size constructions and direct solution readout.

A. The Crossing Lattice

  • A crossing lattice represents each graph vertex by a copy-gadget line, with a crossing for every pair of variables and gadgets encoding edges or decoupling nonedges.The construction uses at most 4N^2 vertices, while more sophisticated lattices can reduce overhead for sparse connectivity.Source: A. The Crossing Lattice · pp. 8–9

B. Maximum Weight Independent Set

  • For arbitrary weighted-graph MWIS, crossing gadgets decouple nonedges and crossing-with-edge gadgets impose edge constraints; boundary vertices reveal the original solution.The construction is embedded on a square lattice, and its weights must satisfy 2wv ≤ δ to ensure valid line configurations.Source: B. Maximum Weight Independent Set · p. 9

C. Quadratic Unconstrained Binary Optimization

  • QUBO linear terms are encoded by line-boundary weights and pair interactions by biased crossing-gadget vertices, with normalization preserving defect-free ground states.The normalized construction has a one-to-one correspondence between zero-defect weights and the original QUBO spectrum.Source: C. Quadratic Unconstrained Binary… · p. 10
  • Any QUBO on N variables can be encoded as UDG-MWIS with at most 4N^2 + O(N) vertices, with lower overhead possible for restricted connectivity.Source: C. Quadratic Unconstrained Binary… · p. 10

D. Integer Factorization

Integer factorization is expressed as coupled binary constraints, then mapped onto a unit-disk maximum weighted independent set (UDG-MWIS) instance using a square lattice of factoring gadgets. The MWIS of the constructed graph reveals factor bits satisfying the constraints.

D. Integer Factorization

  • Because k is unknown, the construction considers each k from 1 through n/2, or instead uses n-bit representations for both factors.Source: D. Integer Factorization · p. 10
  • Factoring an n-bit composite reduces to satisfying k(n −k) coupled equations over factor bits and partial-sum and carry bits, with specified boundary values.The integer bits m_i set boundary conditions, and the ancillary variables s_i,j and c_i,j represent partial sums and carries.Source: D. Integer Factorization · p. 10
  • Copy constraints distribute factor bits across the lattice, where each local factoring constraint involves neighboring or diagonally neighboring variables and each variable enters two constraints except at the boundary.Source: D. Integer Factorization · pp. 10–11
  • A weighted 32-vertex factoring gadget represents each constraint; repeating it across the k(n −k) lattice makes the remaining MWIS encode factor bits satisfying the equations.The gadget is designed so every MWIS agrees with a valid constraint solution on its variable vertices, and every valid solution is represented by at least one MWIS.Source: D. Integer Factorization · p. 11, Figure 8 · p. 11

VI. NUMERICAL SIMULATIONS

Numerical simulations compare adiabatic performance on small original graphs and their mapped unit-disk graphs. For the sampled instances, the mapped and original Landau-Zener timescales appear correlated, but the data do not establish asymptotic behavior.

VI. NUMERICAL SIMULATIONS

  • The study sampled 54 of 112 non-isomorphic six-vertex graphs, excluding instances whose mapped graphs exceeded 25 vertices and graphs directly embeddable as square-lattice UDGs without overhead.Source: §VI · p. 11
  • The simulations initialize at Ω=Ω0 and Δ=0, then linearly ramp Ω to zero and detunings to their final values over time T.Source: §VI · p. 12
  • Simulations assume strong Rydberg blockade and neglect long-range interactions because the original graphs lack a geometric description.Source: §VI · p. 12
  • Adiabatic timescales are estimated by fitting long-time ground-state probabilities to the Landau-Zener form, using points where PMIS ≫0.99.The authors use this timescale rather than the minimum gap alone to compare performance.Source: §VI · p. 12
  • For the graphs considered, mapped and original Landau-Zener timescales appear linearly correlated, but the limited data preclude reliable fitting or conclusions about asymptotic performance.The figure compares extracted timescales; the spread shows no clear dependence on mapped-graph vertex count.Source: §VI · p. 12, Figure 9 · p. 12
  • The small-instance results provide little insight into larger-graph performance; the authors call for Rydberg-array experiments on larger graphs.Source: §VI · pp. 12–13

VII. CONCLUSIONS AND OUTLOOK

The paper presents an explicit mapping from arbitrary-connectivity computation problems to UDG-MWIS, with at most quadratic overhead and examples spanning general-graph MWIS, QUBO, and integer factorization. Simulations find correlated adiabatic timescales for mapped and original problems, while approximate optimization and larger-scale performance remain open questions.

VII. CONCLUSIONS AND OUTLOOK

  • The explicit mapping converts arbitrary-connectivity computation problems to UDG-MWIS with at most quadratic overhead and a procedure suited to square-lattice embedding.Source: §VII · p. 13
  • Examples include general-graph MWIS, QUBO, and integer factorization; simulations indicate mapped and original problems have correlated quantum-algorithm performance.Source: §VII · p. 13
  • If the linear Landau-Zener-time correlation persists asymptotically, a quadratic quantum speedup on the original graph may transfer to the unit-disk graph.Source: §VII · p. 13
  • The work focuses on exact ground-state solutions; how encoding affects approximate optimization and excitations into higher-energy states remains to be investigated.Source: §VII · p. 13

Appendix A: Overhead Reduction

Appendix A presents ways to reduce the overhead of mapping problems to UDG-MWIS, including vertex reordering and simplification rules. Reordering can make the crossing lattice smaller, while weight normalization must preserve valid encoded solutions.

a. Pathwidth Reduction

  • Reordering vertices can reduce crossing-lattice depth, allowing the final mapping to scale with the original graph’s pathwidth; for sparse graphs, pathwidth is usually much smaller than vertex count.A 3-regular graph has pathwidth asymptotically bounded by n/6, while a tree graph has pathwidth logarithmic in n.Source: a. Pathwidth Reduction · pp. 13–14

b. Vertex Reordering

  • For the MWIS example on K2,3, bipartition and vertex reordering yield a simplified unit-disk mapping of 9 vertices, versus 92 nodes for the direct mapping, reducing mapping overhead.Optimal vertex reordering requires an optimal path decomposition, an NP-hard problem; heuristic algorithms can find good path decompositions for larger graphs.Source: b. Vertex Reordering · p. 14

2. Simplification Gadgets

  • Simplification rules and gadgets can reduce mapped-graph overhead while preserving the mapping’s integrity and weight constraints.The appendix notes these are especially useful for MWIS, where node weights are more uniform.Source: §2 · p. 14
  • Biases must be normalized so that constraint violations cost more than the benefits of satisfying weighted terms, keeping the MWIS solution valid and zero-defect.The safest normalization is too conservative, scaling as 1/N for MWIS and 1/N^2 for QUBO; larger valid biases can be found by inspecting the copy gadget and crossing lattice.Source: Appendix B · pp. 15–16

Appendix C: Restricted QUBO Connectivity

Restricted two-dimensional QUBO connectivity can be encoded as UDG-MWIS with constant overhead. The construction uses clique and interaction gadgets, with weights chosen to ensure valid solutions.

Appendix C: Restricted QUBO Connectivity

  • A restricted 2D QUBO problem maps to UDG-MWIS with constant overhead, whereas arbitrary QUBO connectivity carries practical encoding overhead.The example in Fig. 11 has 50 bits and a mapped extent of 13 × 13, which the passage says fits current Rydberg atom array hardware.Source: Appendix C · p. 16, Figure 11 · p. 16
  • A four-vertex clique represents the four states of two bits, with vertex weights encoding their linear and quadratic QUBO terms.For neighboring bit cliques, ancilla vertices encode interactions: one for J < 0 and two for J > 0.Source: Appendix C · p. 16
  • The clique’s zero-bias weight must be sufficiently large to ensure the ground state represents a valid assignment; one guaranteed offset is U = 8J.The stated condition uses J as the largest coupling strength between adjacent bit cliques.Source: Appendix C · p. 17
  • Rydberg arrays can reconstruct graph connectivity shot by shot, unlike superconducting-qubit architectures with fixed connectivity and lengthy topology modification.The described local-connectivity construction is one example; many encodings of different restricted-connectivity graphs may be used.Source: Appendix C · p. 17

Appendix D: Factoring Gadget

The factoring gadget represents the multiplication-and-addition constraint through two simpler constraints. Their MWIS representations are joined at a shared variable to encode the original constraint.

Appendix D: Factoring Gadget

  • The factoring gadget is designed so its MWIS configurations correspond to satisfying assignments of the factoring constraints.The constraint si,j + 2ci,j = pi,jqi,j + si+1,j−1 + ci−1,j is rewritten using z = ab and z + c + d = 2e + f.Source: Appendix D · p. 17
  • The crossing gadget represents z = ab: its interior vertex z belongs to the MWIS exactly when both boundary vertices a and b belong to it.This supplies the MWIS representation of the product constraint.Source: Appendix D · p. 17, Figure 12 · p. 17
  • Joining the MWIS graphs for z = ab and z + c + d = 2e + f at their shared vertex z represents ab + c + d = 2e + f.The shared vertex’s total weight is the sum of its weights in the two component graphs.Source: Appendix D · pp. 17–18

Related papers

Loading 2209.03965v2…