A C OMPARATIVE STUDY ONSOLVING OPTIMIZATION PROBLEMS WITHEXPONENTIALLY FEWER QUBITS David Winderl Nicola Franco Jeanette Miriam Lorenz

2025-04-30 0 0 477.94KB 6 页 10玖币

侵权投诉

A COMPARATIVE STUDY ONSOLVING OPTIMIZATION

PROBLEMS WITH EXPONENTIALLY FEWER QUBITS

David Winderl, Nicola Franco, Jeanette Miriam Lorenz

Fraunhofer Institute for Cognitive Systems IKS,

Hansastrasse 32, 80686

Munich, Germany

{name.middlename.surname}@iks.fraunhofer.de

ABSTRACT

Variational Quantum optimization algorithms, such as the Variational Quantum Eigensolver (VQE)

or the Quantum Approximate Optimization Algorithm (QAOA), are among the most studied quan-

tum algorithms. In our work, we evaluate and improve an algorithm based on VQE, which uses

exponentially fewer qubits compared to the QAOA. We highlight the numerical instabilities gen-

erated by encoding the problem into the variational ansatz and propose a classical optimization

procedure to ﬁnd the ground-state of the ansatz in less iterations with a better or similar objective.

Furthermore, we compare classical optimizers for this variational ansatz on quadratic unconstrained

binary optimization and graph partitioning problems.

Keywords Quantum Computing ·Optimization ·Hybrid Algorithms.

1 Introduction & Related Work

Since the emergence of Variational Quantum Algorithms (VQAs) [Cerezo et al., 2021] and their subclasses, such as

the Variational Quantum Eigensolver (VQE) [Abrams and Lloyd, 1999] and the Quantum Approximate Optimization

Algorithm (QAOA) [Farhi et al., 2014], the amount of research contributions towards the practical utility of quantum

computers has increased every year. Applications of mathematical optimization are of particular interest, and QAOA

is widely adopted in this context. Although QAOA is an heuristic method, researchers are constantly advancing

with slight improvements and precise adjustments to achieve better performance on narrow optimization problems.

The most frequently studied problems are the Travelling Salesman Problem (TSP) [Gavish and Graves, 1978] and

graph partitioning problems, such as MaxCut [Commander]. These NP-hard problems can be reduced to Quadratic

Unconstrained Binary Optimization (QUBO) [Glover et al., 2022] or Ising [Lucas, 2014] formulations.

As pointed out in Guerreschi and Matsuura [2019], because of the ﬂaws of current Noisy Intermediate-Scale Quantum

computers (NISQs), we may only see an actual speedup of large-scale optimization problems with QAOA for devices

with several hundred qubits. Hence recent contributions, have offered decomposition methods to overcome this issue

and decompose the original problem to a size matching of NISQ devices. In this context, decomposition methods, such

as Li et al. [2021] and Zhou et al. [2022], offer solutions to overcome these limitations by splitting the original problem

into smaller subproblems with sizes matching the requirements of NISQ hardware. In Li et al. [2021], after dividing

a graph into two subgraphs that share common nodes, to obtain a possible candidate, the solutions of the respective

subgraphs must overlap exactly. In this regard, the complexity of their approach increases with the number of common

nodes, making it more difﬁcult to ﬁnd a good candidate solution. Extending this, a new encoding strategy in Ranˇ

ci´

[2021] opens a new perspective as it requires exponentially fewer qubits to solve MaxCut with a VQE ansatz. To

achieve this advantage, a continuous differentiable function maps the multi-dimensional binary optimization problem

to a one-dimensional multi-modal continuous variable optimization problem. In this work, after summarizing the

approach of Ranˇ

ci´

c [2021], we highlight its limitations and suggest improvements in form of a proposal of new

functions for encoding the problem. We conduct experiments on structured and random QUBO problems either in

simulated and real quantum devices to demonstrate the viability of our improved approach.

arXiv:2210.11823v1 [quant-ph] 21 Oct 2022

A Comparative Study On Solving Optimization Problems With Exponentially Fewer Qubits

2 Background

2.1 Preliminaries

Considering a weighted graph G= (V, E), we denote as V={1, . . . , n}the set of vertices, and E={(i, j)|(i, j)∈

V×V}the set of edges, with weights wij ∈Rfor (i, j)∈E. In the weighted MaxCut problem, a cut is deﬁned as a

partition of the original set Vinto two subsets. Given a binary vector x∈R|V|, the cost function to be maximized is

given by ˜

C(x) = Pi,j wij xi(1 −xj). It represents the sum of weights of edges connecting points in the two different

subsets, i.e. crossing the cut. MaxCut is a speciﬁc case of a more general class of optimization problems that fall under

the QUBO umbrella. In the context of QUBO, one wants to minimize the following cost function: f(x) = xTQx,

where x∈ {0,1}nis a binary vector and Q∈Rn×nis a square matrix of real values. We can rewrite a QUBO

problem to its Ising variant by setting xi=1

2vi+1

2where vi∈ {−1,1}denotes an Ising spin, and further reduce it to

MaxCut [Barahona et al., 1989].

2.2 MaxCut with exponentially less qubits

0π

2π3π

22π

α1

0.00

0.25

0.50

0.75

1.00

Rf(α1, q, m = 8)

q= 0 q= 1 q= 2

(a) Rf(α1, q, m = 6)

0π

2π3π

22π

α1

10−26

10−17

10−8

101

1010

1019

1028

exp(2m−qsin(2qα1+α0(q, m)))

q= 0 q= 1 q= 2

(b) exp(2m−qsin(2qα1+α0(q, m)))

Figure 1: Rf(α1, q, m = 6) for q∈ {0,1,2}.

We start by considering that the number of cuts in MaxCut can be ex-

pressed as NCU T S =1

4vTL(G)v, where v∈ {−1,1}|V|and L(G)

describes the Laplacian matrix of a graph. As presented in Ranˇ

ci´

[2021], it is possible to map a continuous vector α∈Rk, with

0≤αi≤2π∀i∈N+, and 1≤k≤ |V| − 1, into the spins vector

vby utilizing a continuous differentiable function Rf:R→[0,1]

deﬁned as:

Rf(αi, q, m) = exp(−exp(2m−qsin(2qαi+α0(q, m)))),(1)

where α0(q, m) = arcsin(log2(−log2(0.5))

/2m−q)and m, q ∈N+

with m≥ |V|and 0≤q≤ |V| − 2. In Figure 1a we see

that for different values of q, the function alters between 0 and 1

with different frequencies when changing α1from 0to 2π. Fol-

lowing Ranˇ

ci´

c [2021], we ﬁx mand construct the vector of spins

vas output of Rfby enumerating all qvalues: v(αi, m) =

(eiπRf(αi,0,m),...eiπRf(αi,di,m)). One can create such vectors v∈

{0,1}difor each αi, where Pk

i=1 di=|V|−1, which leads towards

the diagonal gate U(α), speciﬁed as follows:

U(α) = diag(v(α1),...v(αk),1, . . . 1)

=diag(eiπRf(α1,0,m), . . . , eiπRf(αk,dk,m),1, . . . 1),

where the size of U(α)is 2dlog2(|V|)e.U(α)can be realized using

multiplexor gates as outlined in Shende et al. [2004]. Next, assuming that the Laplacian is a d-sparse matrix and can

be effectively embedded on a quantum device Pothen et al. [1990]1, the variational ansatz is given by:

NCU T S =1

4vTL(G)v= 2n−2h0|HU (α)L(G)U(α)H|0i,(2)

where, Hdescribes the Hadamard transform and L(G)is represented as a sum of tensor products of unitary matrices,

and denoted as L(G)in such form.

The Rffunction in Equation 1 serves as a key point for the exponential qubits reduction presented in Ranˇ

ci´

c [2021].

Despite this advantage, the function is highly numerically unstable for larger graphs. To make this clear, let us assume

a graph with |V|= 6, then set m= 6 (since according to Ranˇ

ci´

c [2021], m≥ |V|) and compute Rffor α1=π

and q= 0. In Figure 1b one can see, that partially evaluating exp(26−0·sin (20π

2+α0(0,6))) ≈6.2×1027 already

results in a large number. Hence computing this function for large graphs with not enough dimensions for αis not

feasible.

1Note that while this is possible, we used a less efﬁcient method and just decomposed the matrix as a tensor-product of pauli

matrices

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

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

10 玖币 0人已下载

立即下载

摘要：

ACOMPARATIVESTUDYONSOLVINGOPTIMIZATIONPROBLEMSWITHEXPONENTIALLYFEWERQUBITSDavidWinderl,NicolaFranco,JeanetteMiriamLorenzFraunhoferInstituteforCognitiveSystemsIKS,Hansastrasse32,80686Munich,Germany{name.middlename.surname}@iks.fraunhofer.deABSTRACTVariationalQuantumoptimizationalgorithms,suchastheVar...

展开>> 收起<<

A C OMPARATIVE STUDY ONSOLVING OPTIMIZATION PROBLEMS WITHEXPONENTIALLY FEWER QUBITS David Winderl Nicola Franco Jeanette Miriam Lorenz.pdf

共6页,预览2页

还剩页未读，继续阅读

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

A C OMPARATIVE STUDY ONSOLVING OPTIMIZATION PROBLEMS WITHEXPONENTIALLY FEWER QUBITS David Winderl Nicola Franco Jeanette Miriam Lorenz

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: