Optimal Stochastic Resource Allocation for Distributed Quantum Computing Napat Ngoenriang Minrui Xuy Sucha Supittayapornpong Dusit Niyatoy Han Yuy Xuemin Sherman Shenz

2025-04-29 0 0 536.96KB 6 页 10玖币

侵权投诉

Optimal Stochastic Resource Allocation for

Distributed Quantum Computing

Napat Ngoenriang∗, Minrui Xu†, Sucha Supittayapornpong∗, Dusit Niyato†, Han Yu†, Xuemin (Sherman) Shen‡

∗School of Information Science and Technology, Vidyasirimedhi Institute of Science and Technology, Thailand

†School of Computer Science and Engineering, Nanyang Technological University, Singapore

‡Department of Electrical and Computer Engineering, University of Waterloo, Waterloo, ON, Canada

Abstract—With the advent of interconnected quantum com-

puters, i.e., distributed quantum computing (DQC), multiple

quantum computers can now collaborate via quantum networks

to perform massively complex computational tasks. However,

DQC faces problems sharing quantum information because it

cannot be cloned or duplicated between quantum computers.

Thanks to advanced quantum mechanics, quantum computers

can teleport quantum information across quantum networks.

However, challenges to utilizing efﬁciently quantum resources,

e.g., quantum computers and quantum channels, arise in DQC

due to their capabilities and properties, such as uncertain qubit

ﬁdelity and quantum channel noise. In this paper, we propose

a resource allocation scheme for DQC based on stochastic pro-

gramming to minimize the total deployment cost for quantum re-

sources. Essentially, the two-stage stochastic programming model

is formulated to handle the uncertainty of quantum computing

demands, computing power, and ﬁdelity in quantum networks.

The performance evaluation demonstrates the effectiveness and

ability of the proposed scheme to balance the utilization of

quantum computers and on-demand quantum computers while

minimizing the overall cost of provisioning under uncertainty.

Index Terms—Distributed Quantum Computing, Quantum

Networks, Resource Allocation, Stochastic Programming

I. INTRODUCTION

To date, quantum computing is tremendously fast and efﬁ-

cient, being able to do computations in a matter of seconds

which would take decades for older supercomputers [1]. In

2019, a prototype of Google’s quantum computer was able to

ﬁnish the computation and demonstrate the effectiveness of

quantum mechanics [2]. Breakthroughs in quantum comput-

ing are essential and inﬂuence various applications, such as

artiﬁcial intelligence (AI), molecular modelling, weather fore-

casting, and drug development [3]. Since the development of

quantum computers is still in its infancy, distributed quantum

computing (DQC) has emerged in signiﬁcance to solve more

complex computational tasks. In the next quantum computing

era, IBM [4] and Google [5] aim to introduce a practical DQC,

which is anticipated in 2025. Although the advent of DQC has

also advanced processing speed for a variety of heterogeneous

tasks, quantum resources are still limited and need to be

managed effectively while performing computations.

The basis for the development of quantum computing is

formed based on properties of quantum mechanics, i.e., super-

position, entanglement, and interference, as shown in Fig. 1.

Superposition permits encoding in a mixture of two states

(i.e., qubits). A qubit offers more information storage and

computation choices than binary bits in classical computers.

In quantum mechanics, entanglement describes a correlation

between two qubits in which the values of one qubit may

depend on another. To observe the values of qubits, measure-

ment, often referred to as interference, can be used to interrupt

the processing of quantum computers.

Quantum algorithms enable qubits in quantum computers

by utilizing quantum mechanics. For instance, Shor’s [6]

and Grover’s [7] algorithms were developed to deal with

factorization and the search for unstructured data, respectively,

which are highly challenging for classical computers. To tackle

these tasks with quantum computers, at least the order of 106

physical qubits are required [6]. However, a recently devel-

oped quantum computer can only contain tens of qubits [8].

Therefore, it becomes increasingly challenging to handle and

control information in quantum computers due to the limited

number of qubits, the instability of qubits, and the amount of

information required for complex computational tasks. As a

result, the concept of DQC has been presented.

In DQC, quantum teleportation, or the transfer of qubits, is

required for quantum computers to connect and collaborate.

In this regard, multiple quantum computers can work col-

laboratively to compute a large-scale complex computational

task at quadratic or exponential speed-up. Moreover, most of

common quantum algorithms can beneﬁt from their distributed

equivalents. For example, distributed Shor’s algorithm can

reduce computational complexity compared to original Shor’s

algorithm [9]. Additionally, distributed Grover’s algorithm has

a considerably lower query time than Grover’s algorithm [10].

Therefore, distributed quantum algorithms can enhance prac-

tical feasibility of quantum computers in tackling complex

computational tasks in practice.

Although DQC and distributed quantum algorithms have

evolved and accelerated to handle complex computational

tasks, quantum resources, e.g., quantum computers and quan-

tum channels, must be optimally allocated to perform hetero-

geneous computational tasks. However, the efﬁcient utilization

of quantum resources in DQC is still facing challenges.

First, the utilization of quantum resources depends on the

demands of computational tasks, which are not known pre-

cisely at the time of quantum computer deployment. Second,

quantum computers’ availability and computing power may

arXiv:2210.02886v1 [cs.DC] 16 Sep 2022

Quantum

computer operator

Provision of the deployed

quantum computers

Provision of on-demand

quantum computers

Minimize the total

deployment cost

Perform distributed

quantum computing

Entanglement

Superposition

Properties of quantum mechanics

Measurement/Interference

Computational Tasks

Fig. 1: The illustration of system model of distributed quantum computing.

or may not be available to compute computational tasks.

Third, ﬁdelity degradation occurs when performing quantum

teleportation and transferring qubits over quantum networks,

which degrades the efﬁcacy of the entangled qubits. Due to the

uncertainty, allocating quantum resources in DQC may result

in both under and over-deployment of quantum computers.

In addition, because of the limitations of quantum resources,

quantum computers can be purchased or outsourced from

other organizations such as Amazon Braket [11] to complete

complex computational tasks. However, the cost of on-demand

quantum computers is relatively more expensive.

To address the aforementioned challenges, in this paper, we

propose a resource allocation scheme based on stochastic pro-

gramming to minimize the total deployment cost to compute

computational tasks in DQC. The main contributions of this

paper can be summarized as follows:

•We propose an optimal resource allocation scheme to

compute computational tasks in DQC. In particular, the

optimal resource allocation are jointly obtained under the

uncertainties of future demands of computational tasks

and instability of quantum characteristics.

•We conduct extensive experiments to demonstrate the

importance and effectiveness of the proposed optimal

resource allocation scheme, which achieves the lowest

total deployment cost.

II. RELATED WORK

Quantum computing was developed to increase the capabil-

ity of existing computational resources [12]. One of challenges

in quantum computing is quantum algorithms implemented on

quantum computers, for example, Shor’s [6] and Grover’s [7]

algorithms are requiring a massive number of qubits to exe-

cute. For instance, Shor’s algorithm was developed to handle

a factorization problem with around 106qubits, which is too

complex for classical computers [6]. In addition, Grover’s

algorithm was presented to search unordered data by encoding

inputs with dimension Nas superposition with √Nqubits,

which gives a quadratic computing speed-up [7] to search op-

erations in non-structure databases. These quantum algorithms

can be adopted to outperform existing conventional algorithms

with quadratic or exponential speed-up computations [13].

However, due to challenges in scaling up the number

of qubits, quantum computers are not yet ready to replace

traditional computers [14]. Therefore, DQC was introduced to

combine several quantum computers to handle more complex

computational tasks [14], [15]. Most existing works look at

distributed quantum mechanics and algorithms to be the basis

in DQC [14], [15]. Similar to quantum algorithms, distributed

Shor’s [9] and Grover’s [10] algorithms were widely used. The

distributed Shor’s algorithm has a computing complexity of

O((logN )2), which outperforms the original Shor’s algorithm,

i.e., O((logN )2log(logN )log(log(logN ))), where Nis the

number to be factored [9]. Grover’s algorithm incurs expensive

query time due to its use of superpositions as inputs. Accord-

ing to [9], the distributed Grover’s algorithm was devised to

improve the original Grover’s algorithm by reducing the query

times from π

4√2nto π

4√2n−k, where nis the number of input

bits of the original problem, whereas n−kis the number of

input bits for the decomposed subfunctions.

Next, we discuss resource allocation problems in distributed

computing, quantum computing, and DQC, which is the mo-

tivation for our work, as follows:

1) Resource Allocation in Distributed Computing: To en-

hance the performance of distributed computing, the au-

thors [16] reviewed existing resource allocation schemes

under dynamic environments in distributed computing

with various types of classical resources, e.g., computing,

power, and storage resources. In particular, the authors

in [17] formulated the problem of resource allocation in

cloud computing as a stochastic programming model by

considering the uncertainty of user requirements.

2) Resource Allocation in Quantum Computing: The authors

in [18], [19] proposed and analyzed the signiﬁcance of re-

source allocation problems and adaptive resource alloca-

tion problems, respectively, in quantum cloud computing,

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

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

10 玖币 0人已下载

立即下载

摘要：

OptimalStochasticResourceAllocationforDistributedQuantumComputingNapatNgoenriang,MinruiXuy,SuchaSupittayapornpong,DusitNiyatoy,HanYuy,Xuemin(Sherman)ShenzSchoolofInformationScienceandTechnology,VidyasirimedhiInstituteofScienceandTechnology,ThailandySchoolofComputerScienceandEngineering,NanyangTec...

收起<<

Optimal Stochastic Resource Allocation for Distributed Quantum Computing Napat Ngoenriang Minrui Xuy Sucha Supittayapornpong Dusit Niyatoy Han Yuy Xuemin Sherman Shenz.pdf

共6页,预览2页

还剩页未读，继续阅读

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

Optimal Stochastic Resource Allocation for Distributed Quantum Computing Napat Ngoenriang Minrui Xuy Sucha Supittayapornpong Dusit Niyatoy Han Yuy Xuemin Sherman Shenz

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: