Rydberg blockade based parity quantum optimization Martin Lanthaler1Clemens Dlaska1Kilian Ender1 2and Wolfgang Lechner1 2 1Institute for Theoretical Physics University of Innsbruck A-6020 Innsbruck Austria

2025-04-24 0 0 1.38MB 10 页 10玖币

侵权投诉

Rydberg blockade based parity quantum optimization

Martin Lanthaler,1, ∗Clemens Dlaska,1, ∗Kilian Ender,1, 2 and Wolfgang Lechner1, 2

1Institute for Theoretical Physics, University of Innsbruck, A-6020 Innsbruck, Austria

2Parity Quantum Computing GmbH, A-6020 Innsbruck, Austria

We present a scalable architecture for solving higher-order constrained binary optimization prob-

lems on current neutral-atom hardware operating in the Rydberg blockade regime. In particular,

we formulate the recently developed parity encoding of arbitrary connected higher-order optimiza-

tion problems as a maximum-weight independent set (MWIS) problem on disk graphs, that are

directly encodable on such devices. Our architecture builds from small MWIS modules in a problem-

independent way, crucial for practical scalability.

Introduction.— With the recent advances in experi-

ments, programmable arrays of Rydberg atoms have be-

come a versatile platform for quantum computing and

quantum simulation [1–5]. In particular, the platform has

been identiﬁed as a prime candidate for tackling combi-

natorial optimization problems using quantum annealing

and variational quantum algorithms [6,7]. Many combi-

natorial optimization problems are known to be hard to

solve for classical computers and thus current quantum

computing eﬀorts are directed toward exploring potential

quantum speedups.

A key challenge to reach this goal, especially in the

current era of noisy intermediate scale quantum (NISQ)

devices [8], is to make eﬃcient use of the available phys-

ical resources. To this end, it is of crucial importance to

match the strengths of a particular physical platform to

the computational problem under consideration. In the

realm of quantum optimization, it was recently shown

that the Rydberg platform provides a natural, overhead-

free match for encoding maximum-weight independent

set (MWIS) problems on disk graphs [6,9] based on the

so-called Rydberg blockade mechanism [10–12]. Even

though solving this “Rydberg-encoded” MWIS problem

has been shown to be NP-hard [13], it remains challeng-

ing to extend this approach restricted to disk graphs for

encoding arbitrary optimization problems. This is espe-

cially true for problems that go beyond quadratic binary

optimization (QUBO), i.e., allowing for higher-order in-

teraction terms (hypergraphs) and side conditions (hard

constraints).

Here, we propose a scheme to overcome these limi-

tations by utilizing the recently introduced parity en-

coding of arbitrary combinatorial optimization prob-

lems [14,15]. Our scheme allows one to construct

the problem-deﬁning spin model from small, problem-

independent MWIS blocks on a two-dimensional lattice

geometry, paving the way for straightforward scalabil-

ity. Furthermore, we equip our approach with a lo-

cal compensation routine minimizing unwanted Rydberg-

interaction-induced crosstalk and numerically demon-

strate, that our procedure faithfully encodes the solution

∗These authors contributed equally to this work. Corresponding

author: martin.lanthaler@uibk.ac.at

(a)

(c)

∝r−6

Ω

∆

|gi

|ri

345

234

134

235

(b)

MWIS

2α

∆ = α+J67

FIG. 1. Rydberg parity MWIS protocol. Arbitrary combinato-

rial optimization problems (a) can be parity-transformed to

a spin model utilizing only local-ﬁelds and quasi-local inter-

actions (indicated by blue squares and triangles) (b). The

resulting plaquette logic can be realized as a MWIS problem

on disk graphs, readily implementable in state-of-the-art neu-

tral atom devices (c). There, each vertex is represented by

an atom, with states |0iand |1iencoded in electronic ground

|giand strongly interacting Rydberg states |ri, coherently

driven by Rabi frequency Ω and detunings ∆. Strong van

der Waals interactions energetically unfavour conﬁgurations

where atoms in state |riare closer than rB.

to the optimization problem as a MWIS ground state.

Maximum-weight independent set with Rydberg atom

arrays.— A paradigmatic NP-complete problem is the

so-called maximal independent set (MIS) problem [16].

Given a graph G= (V, E), an independent set S⊆Vis

a subset of vertices where no pair is connected via an edge

e∈E. The problem of ﬁnding the independent set with

maximal cardinality is called MIS problem. Assigning a

weight ∆v>0 to each vertex generalizes the MIS problem

to the MWIS problem that asks for the independent set

with maximal total weight W=Pv∈S∆v. The MWIS

problem can be formulated as a spin model

arXiv:2210.05604v1 [quant-ph] 11 Oct 2022

HMWIS =−X

v∈V

∆vˆnv+X

(v,w)∈E

Uvw ˆnvˆnw,(1)

where each vertex is associated to a spin-1/2 system (with

states |0iand |1i) and ˆnv=|1ivh1|. For Uvw >∆v>0,

HMWIS energetically favors spin conﬁgurations to be in

the state |1iand penalizes adjacent spins whenever they

are in state |1i. Hence, the ground state of HMWIS is

the sought-after MWIS. For disc graphs, these problems

have been shown to be native to programmable arrays of

neutral atoms [6,9], where individual atoms are trapped

in optical tweezers and deterministically placed in two

dimensions. Each atom realizes a qubit where the elec-

tronic ground state represents the state |0iand a highly

excited Rydberg state represents the state |1i. These

states can be coherently coupled via laser light and in-

duce strong dipolar interactions between pairs of atoms

in state |1i.

The corresponding Hamiltonian describing this system

is given by

HRyd =X

iΩi

2ˆσ(i)

x−∆iˆni+X

i<j

V(|xi−xj|)ˆniˆnj,

(2)

where Ωiand ∆idenote the Rabi frequency and laser

detuning of atoms at position xi, respectively. Coher-

ent laser coupling induces ﬂips among the computational

states, i.e., ˆσx=|0ih1|+|1ih0|, and the interaction is

assumed to be of isotropic van der Waals (vdW) form

V(|xi−xj|) = C6/|xi−xj|6. The vdW interaction in-

duces a strong energy penalty on nearby atoms in the

Rydberg state. This gives rise to the so-called Ryd-

berg blockade [1,10,11] which prevents Rydberg excita-

tions around a Rydberg-excited atom positioned at xv

within a characteristic distance called blockade radius

rB(∆v)=(C6/∆v)1/6. The blockade mechanism directly

corresponds to disk graphs [17], i.e., intersection graphs

of a set of disks in the Euclidian plane, where the vth disk

radius can be identiﬁed as the blockade radius rB(∆v).

Neglecting the long-range tails of the dipolar interaction,

HRyd(Ωi= 0,∆i>0) is able to directly realize Eq. (1)

for disk graphs [see Fig. 1(c)]. In order to solve the opti-

mization problem one can for example devise a quantum

annealing algorithm [18] that adiabatically connects the

ground state of HRyd(Ωi= 0,∆i<0), where all atoms

are in state |0i, to the solution-encoding ground state of

HRyd(Ωi= 0,∆i>0).

Parity encoding as MWIS.— As stated above, a remain-

ing challenge is to utilize the Rydberg platform operat-

ing in the Rydberg blockade regime for tackling generic

combinatorial optimization problems. These optimiza-

tion problems can be cast in the form of an energy min-

(a)

(b)

=α

= 2α

120◦

MWIS

FIG. 2. Basic parity MWIS building blocks. (a) Two-body

constraint nA⊕nB= 0 as three-node MWIS problem with so-

lutions. (b) The three-body parity constraint nA⊕nB⊕nC=

1 can be recast as a MWIS problem on six nodes. The four

MWISs {A, B, C},{A, a},{B, b}and {C, c}are in one-to-one

correspondence with the corresponding parity-constraint ful-

ﬁlling assignments.

imization of (classical) N-spin Hamiltonians

Hproblem =X

Jisi+X

i<j

Jij sisj

i<j<k

Jijksisjsk+. . . , (3)

where si=±1 denote spin variables and the coeﬃ-

cients {Ji, Jij , Jijk, . . . }describe local ﬁelds and arbi-

trarily long-ranged and higher-order interactions between

spins [see Fig. 1(a)]. Direct experimental implementa-

tions of Eq. (3) with Rydberg atoms are, however, lim-

ited to rather speciﬁc optimization graphs due to the

dependency on the hardware geometry and the polyno-

mially decaying interaction strengths. The parity ar-

chitecture [14,15] deals with this diﬃculty by encod-

ing the relative orientation of original problem spins

into parity-qubits, e.g., Jijk sisjsk7→ Jmˆnm, where

each parity qubit is labeled by the corresponding prob-

lem spin indices m= (i, j, k) with binary eigenvalues

nm= (1 + Qi∈msi)/2∈ {0,1}. This transformation re-

duces multibody interactions to local ﬁelds which in-

creases the number of qubits to the number K≥Nof

interactions present in the optimization problem. In or-

der to stabilize the original N-spin code space, quasi-local

three- or four-qubit constraints on 2 ×2 plaquettes are

introduced [see Fig. 1(b)]. They are required to fulﬁll

C:(nA⊕nB⊕nC= 1

nA⊕nB⊕nC⊕nD= 0,(4)

where ⊕denotes addition modulo two. Our goal now

is to formulate the logic imposed by Cas a MWIS

spin-Hamiltonian HMWIS [cf. Eq. (1)] commensurate with

the Rydberg platform operating in the blockade regime.

The parity-encoded optimization problem then also cor-

responds to a MWIS problem providing the advantage of

practical scalability in a problem-independent and mod-

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

RydbergblockadebasedparityquantumoptimizationMartinLanthaler,1,ClemensDlaska,1,KilianEnder,1,2andWolfgangLechner1,21InstituteforTheoreticalPhysics,UniversityofInnsbruck,A-6020Innsbruck,Austria2ParityQuantumComputingGmbH,A-6020Innsbruck,AustriaWepresentascalablearchitectureforsolvinghigher-ordercon...

展开>> 收起<<

Rydberg blockade based parity quantum optimization Martin Lanthaler1Clemens Dlaska1Kilian Ender1 2and Wolfgang Lechner1 2 1Institute for Theoretical Physics University of Innsbruck A-6020 Innsbruck Austria.pdf

共10页,预览2页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Rydberg blockade based parity quantum optimization Martin Lanthaler1Clemens Dlaska1Kilian Ender1 2and Wolfgang Lechner1 2 1Institute for Theoretical Physics University of Innsbruck A-6020 Innsbruck Austria

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: