Quantum Optimisation for Continuous Multivariable Functions by a Structured Search Edric Matwiejewy Jason Pye Jingbo B. Wang

2025-04-26 0 0 5.06MB 16 页 10玖币

侵权投诉

Quantum Optimisation for Continuous

Multivariable Functions by a Structured Search

Edric Matwiejew†, Jason Pye, Jingbo B. Wang

1Department of Physics, The University of Western Australia, Perth, WA 6009, Australia

†edric.matwiejew@uwa.edu.au

Solving optimisation problems is a promising near-term application of quantum computers. Quan-

tum variational algorithms leverage quantum superposition and entanglement to optimise over

exponentially large solution spaces using an alternating sequence of classically tunable unitaries.

However, prior work has primarily addressed discrete optimisation problems. In addition, these

algorithms have been designed generally under the assumption of an unstructured solution space,

which constrains their speedup to the theoretical limits for the unstructured Grover’s quantum

search algorithm. In this paper, we show that quantum variational algorithms can efﬁciently opti-

mise continuous multivariable functions by exploiting general structural properties of a discretised

continuous solution space with a convergence that exceeds the limits of an unstructured quantum

search. We introduce the Quantum Multivariable Optimisation Algorithm (QMOA) and demon-

strate its advantage over pre-existing methods, particularly when optimising high-dimensional and

oscillatory functions.

Quantum computing promises to solve problems that are classically intractable [1]. One potential application is

optimisation over high-dimensional spaces, which suffers from the long-fought ‘curse of dimensionality’ [2].

Quantum computers may help overcome this by leveraging quantum superposition and entanglement on exponentially

large solution spaces. For this reason, much attention has been applied to the development of quantum optimisation

algorithms [3, 4, 5, 6]. Quantum Variational Algorithms (QVAs) belong to a class of hybrid quantum-classical al-

gorithms in which a classically parameterised quantum system accelerates a search through a ﬁnite problem solution

space [3, 7, 5, 8]. These algorithms have a ﬂexible structure and are inherently resilient to error [9, 10]. As such, they

are predicted to be an early practical use of quantum computing in the Noisy Intermediate-Scale Quantum (NISQ)

era [11].

QVA development has primarily focused on Combinatorial Optimisation Problems (COPs). These include al-

gorithms for unconstrained optimisation, such as the widely studied Quantum Approximate Optimisation Algorithm

(QAOA), and constrained optimisation [3, 7, 5, 4]. Most COPs of practical concern lack identiﬁable structure [7, 5].

Consequently, QVAs for COPs strive for an unbiased search over the space of valid solutions. In this regard, they are

fundamentally related to Grover’s search algorithm [12], a well-known quantum algorithm for deterministic search in

an unstructured solution space. Grover’s search is optimal for the number of required solution space evaluations and

thus sets an upper bound on the efﬁciency of QVAs for general COPs [13, 14]. The utility of QVAs for COPs arises

from the reality that Grover’s search requires a quantum circuit depth that is not feasible on near-term hardware. How-

ever, as QVAs utilising an unstructured search can provide a sub-Grover speedup at best, there is motivation to develop

algorithms capable of exceeding this limit by exploiting solution space structure. One example is the QAOA for the

case of the max-cut problem on three-regular graphs [15]. There is also recent work adopting an iterative process to

construct general problem-tailored QAOA operators [16].

Structured approaches are ubiquitous in classical algorithms for Continuous Multivariable Optimisation Problems

(CMOPs) with many well-known instances, including the gradient-based Broyden-Fletcher-Goldfarb–Shanno (BFGS)

algorithm and the simplex-based Nelder-Mead algorithm [17, 18]. However, QVAs for CMOPs have received little

attention despite their relevance to optimisation tasks considered in the literature on QVAs for COPs. For example,

the ﬁnancial portfolio optimisation problem typically includes proportion-weighted asset combinations—which are

not accounted for by a combinatorial approach [19, 20]. Various quantum algorithms for gradient descent have been

developed outside of the QVA framework. Some approaches are based on an algorithm of Jordan [21], which provides

a speedup in the computation of gradients in high-dimensional spaces. Measurements of this gradient are then used

in an iteration of a descent algorithm [21, 22, 23, 24, 25]. Another approach is to use amplitude encoding of solution

vectors and leverage quantum speedups in the solution of linear systems [26, 27]. A gradient-descent-inspired QVA for

arXiv:2210.06227v1 [quant-ph] 12 Oct 2022

continuous-variable optimisation was suggested in [28]. The authors numerically demonstrated a wavepacket prop-

agating towards the global minimum of a two-dimensional function with hand-selected variational parameters [28].

A recent experimental implementation is described in [29]. This is referred to here as Quantum Optimisation with

Wavepacket Evolution (QOWE).

Building on this, we have developed the highly efﬁcient Quantum Multivariable Optimisation Algorithm (QMOA),

which adopts a continuous-time quantum walk (CTQW) framework [30]. It solves CMOPs by implementing semi-

independent CTQWs on a composite graph structure which conforms to the structure of the discretised solution space.

Using a circulant operator structure with the quantum Fourier transform makes the QMOA efﬁcient [31, 32, 33], while

supporting independent parameterisation over the solution space dimensions.

Results

This section introduces the main contribution of this work, the QMOA, as an extension of the QAOA and QOWE. We

begin by introducing a quantum encoding of the continuous-variable optimisation problem and the general form of a

QVA. The QMOA is then developed by considering the relative ability of mixing operators in the QAOA and QOWE

to capture structural information and distinguish between unique solutions in the quantum-encoded solution space. We

present numerical results that assess these QVAs in terms of mean error, statistical distance from the global minimum

and maximum ampliﬁcation. To identify efﬁcient exploitation of solution space structure, we compare QVA maximum

ampliﬁcation to the ampliﬁcation produced by a deterministic restricted depth Grover’s search (RDGS) (see App. A).

For the two best-performing QVAs, the QMOA with a complete graph mixer and the QAOA with a hypercube mixer,

we consider the mean error and statistical distance over twenty test-functions (see App. B) and empirically assess their

scalability in terms of the function dimension and grid size in each dimension.

The Continuous Multivariable Optimisation Problem. For a continuous function f:X→Y, where X⊂RD

and Y⊂R, continuous-variable optimisation seeks x∗= (x0, ..., xD−1)∈Xsatisfying,

f(x∗)≤fmin +, (1)

where fmin is the global minimum of fand  > 0deﬁnes a region of accepted xnear fmin.

An encoding of the optimisation problem in a system of qubits consists of evaluating fon a grid of K=ND

points. In each dimension d, the coordinate is discretised as xd,nd=xd,0+nd∆xd, with minimum value xd,0, grid

spacing ∆xd, and nd= 0, . . . , N −1. The complete solution space of discretised coordinates xkis then represented

using O(log K)qubits by states |ki≡|xD−1,nD−1, xD−2,nD−2, . . . , x0,n0i, where k= 0, . . . , ND−1is a vectorised

index for the set (n0, . . . , nD−2, nD−1)∈ {0, . . . , N −1}D. For optimisation over this discrete space, we denote the

global minimum as x∗≡argminkf(xk).

QVAs for Approximate Optimisation. This work considers QVAs of the form

|t,γi= p

i=1

U(ti, γi)!|ψ0i,(2)

where the positive integer pis a ﬁxed number of ansatz iterations, ˆ

Uis the ansatz unitary, tiand γiare real-valued

variational parameters and,

|ψ0i=1

√K

K−1

k=0 |ki,(3)

unless otherwise speciﬁed. The ansatz unitary consists of the so-called alternating phase-shift, ˆ

UQ, and mixing, ˆ

UW,

unitaries, ˆ

U(t, γ) = ˆ

UW(t)ˆ

UQ(γ).(4)

The ﬁrst of these, ˆ

UQ(γ) = exp(−iγˆ

Q),(5)

applies a phase-shift proportional to

K−1

k=0

fk|kihk|,(6)

where fk≡f(xk). The second unitary, ˆ

UW, conforms to some structure speciﬁc to each algorithm. Its role is to drive

the transfer of probability amplitudes between the solution states. During the mixing stage, phase differences encoded

by ˆ

UQresult in interference that is manipulated by varying (t,γ).

A QVA then proceeds by repeated preparation of |t,γi. After each iteration, (t,γ)are tuned using a classical

optimisation algorithm to minimise the expectation value

hQi=ht,γ|ˆ

Q|t,γi.(7)

The intended consequence is an increased probability of measuring solutions satisfying Eq. (1). The possible am-

pliﬁcation increases with pat the expense of a deeper quantum circuit and larger parameter space for the classical

optimiser.

The Quantum Approximate Optimisation Algorithm. The QAOA deﬁnes the mixing unitary as

UW-QAOA(t) = exp(−itˆ

W),(8)

which is deﬁned by the mixing operator

K−1

k,k0=0

wkk0|kihk0|,(9)

where typically wkk0∈ {0,1}. This can be interpreted as implementing a continuous-time quantum walk for time

t≥0over an undirected graph of Kvertices with adjacency matrix wkk0, where wkk0= 1 if vertices kand k0are

connected and k6=k0[4, 7]. For a complete graph ˆ

W, one can write

UW-QAOA(t) = eit 

ˆ

I+ (e−itK −1) 1

K−1

k,k0=0 |kihk0|

.(10)

The action of a single iteration of ˆ

UQAOA(t, γ) = ˆ

UW-QAOA(t)ˆ

UQ(γ)then maps the amplitudes of an arbitrary state

Pkαk|ki(up to a global phase eit) as

αk7→ e−iγfkαk+ (e−iKt −1) 1

K−1

k0=0

e−iγfk0αk0!.(11)

We see that the second term averages the amplitudes over the entire solution space and is the same for all k. Ampli-

ﬁcation of a particular coefﬁcient αkthen depends on how this local information compares with the global average.

This is a useful property in the absence of an identiﬁed solution space structure, since kis distinguished solely by

the locally phase-encoded fk[20, 14]. Notice that the unbiased coupling in Eq. (10) means that amplitudes at any

two points k,k0with fk≈fk0evolve similarly under ˆ

UQAOA(t, γ), and will also respond similarly to variation in t

and γ. This is a potential disadvantage in the context of CMOPs since contours in fresult in many degenerate fk.

Highly degenerate solutions will greatly inﬂuence the sum in Eq. (11), and thus are likely to dominate the optimisation

process.

The QAOA was originally deﬁned with the ˆ

Wstructured according to a hypercube graph, as a hypercube on M

qubits is easily implemented as PM−1

i=0 ˆ

X(i), where superscript (i)denotes action on qubit i[3]. For a hypercube

graph ˆ

W, the QAOA mixing unitary can be written as:

UW-QAOA(t) =

w=0

(cos t)M−w(−isin t)w

K−1

k=0 X

b∈Bw|kihk⊕b|,

where Bwis the set of bit strings of Hamming weight w, and k⊕bdenotes bitwise XOR between the binary represen-

tation of kand b. As opposed to Eq. (10), the hypercube mixer couples points differently according to their respective

Hamming distance. Thus, even if there are many points with similar fkvalues, amplitudes at such points should only

respond similarly to variations in tand γwhen averages of phase-shifted amplitudes at a ﬁxed Hamming distance

away are the same. Given a hypercube embedding of the solution space grid, this is likely to occur primarily when f

has particular structural properties, such as rotational symmetry or periodicity.

In the context of a quantum search over the discretised solution space of a CMOP, the hypercube has the desirable

property of (at least approximate) preservation of the solution space structure, as grids in one, two, and three dimen-

sions can be embedded in a hypercube [34]. Examples of the grid embedding induced by ˆ

UW-QAOA are shown in Fig. 1

(b) and (c). Also, a hypercube graph has a diameter of Mand Mdisjoint paths between any two vertices [34], so the

distance between any two xkis exponentially smaller than K.

Quantum Optimisation with Wavepacket Evolution. The approach to continuous-variable optimisation described

in [28] (also [35, Sec. III.B]) using continuous quantum variables consists of the propagation of an initial Gaussian

wavepacket under a phase-shift followed by the mixing unitary

U(t) =

D−1

d=0

e−itˆp2

d,(12)

where ˆpdis the momentum operator conjugate to the continuous coordinate ˆxd. This choice is inspired by considering

the quantum simulation of a particle evolving under the potential f(x).

Here we examine a discretised form of this algorithm, with the problem solution space encoded in |ki. The state

is initialised to a discretised Gaussian wavepacket,

|ψ0i=1

√A

K−1

k=0

D−1

d=0

e−(x(d)

k−µd)2

2σd2|ki(13)

where x(d)

kis the dth component of xk,µdand σdare the centre and width of the wavepacket in each dimension, and

Ais a normalising constant. Discretising the mixing unitary requires a discrete form of the continuous momentum

operator. For our implementation of QOWE, we construct a discrete analogue of the continuous-variable relationship

ˆpd=F−1ˆxdF(in each dimension), where Fis the continuous Fourier transform. The continuous Fourier transform

along a single dimension can be approximated on the discretised grid as

F ≈ Fd:=

N−1

nd=0

e−ixd,0κd,nd|ndihnd|DFT,(14)

where DFT is the centred discrete Fourier transform, and κd,nd=κd,0+nd∆κdis a momentum-space grid point,

with ∆κd=2π

N∆xd,κd,0= ∆κd(−N+1+bN−1

2c), and nd= 0, . . . , N −1. The corresponding Fourier transform

over the entire discretised solution space is then F:= ⊗D−1

d=0 Fd, and the mixing unitary is

U|κk|2(t) = F−1e−itˆ

WκF(15)

where ˆ

Wκis the diagonal operator,

Wκ=

K−1

k=0 |κk|2|kihk|,(16)

and where κk= (κ0,n0, . . . , κD−1,nD−1)is a momentum space grid point with a similar indexing to xk.

Applying the phase-shift unitary followed by the ﬁrst Fourier transform in Eq. (15) and computational basis mea-

surement is related to Jordan’s algorithm for gradient computation [21]. Here, the gradient information is used co-

herently by following the ﬁrst Fourier transform by the remaining two unitaries in Eq. (15), instead of performing a

measurement.

The Quantum Multivariable Optimisation Algorithm. The QMOA mixer is taken to be a unitary of separable

CTQWs,

UW-QMOA(t) =

D−1

d=0

exp(−itdˆ

Cd),(17)

where t= (t0, ...tD−1)with td≥0and ˆ

Cdis the adjacency matrix of an undirected graph (see Eq. (9)) connecting

vertices along the dimension d. The discretisation of the QOWE mixer is of a similar form if the generator of Eq. (15)

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

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

10 玖币 0人已下载

立即下载

摘要：

QuantumOptimisationforContinuousMultivariableFunctionsbyaStructuredSearchEdricMatwiejewy,JasonPye,JingboB.Wang1DepartmentofPhysics,TheUniversityofWesternAustralia,Perth,WA6009,Australiayedric.matwiejew@uwa.edu.auSolvingoptimisationproblemsisapromisingnear-termapplicationofquantumcomputers.Quan-tumva...

展开>> 收起<<

Quantum Optimisation for Continuous Multivariable Functions by a Structured Search Edric Matwiejewy Jason Pye Jingbo B. Wang.pdf

共16页,预览4页

还剩页未读，继续阅读

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

Quantum Optimisation for Continuous Multivariable Functions by a Structured Search Edric Matwiejewy Jason Pye Jingbo B. Wang

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: