QParallel Explicit Parallelism for Programming Quantum Computers Thomas H aner Vadym Kliuchnikovy Martin Roettelery Mathias Soekenand Alexander Vaschilloy

2025-05-02 0 0 501.34KB 9 页 10玖币

侵权投诉

QParallel: Explicit Parallelism for Programming

Quantum Computers

Thomas H¨

aner∗, Vadym Kliuchnikov†, Martin Roetteler†, Mathias Soeken∗and Alexander Vaschillo†

∗Microsoft Quantum, Switzerland

†Microsoft Quantum, USA

Abstract—We present a language extension for parallel quan-

tum programming to (1) remove ambiguities concerning paral-

lelism in current quantum programming languages and (2) fa-

cilitate space-time tradeoff investigations in quantum computing.

While the focus of similar libraries in the domain of classical

computing (OpenMP, OpenACC, etc.) is to divide a computation

into multiple threads, the main goal of QParallel is to keep the

compiler and the runtime system from introducing parallelism-

inhibiting dependencies, e.g., through reuse of qubits in automatic

qubit management. We describe the syntax and semantics of the

proposed language extension, implement a prototype based on

Q#, and present several examples and use cases to illustrate

its performance beneﬁts. Moreover, we introduce a tool that

guides programmers in the placement of parallel regions by

identifying the subroutines that proﬁt most from parallelization,

which is especially useful if the programmer’s knowledge of the

source code is limited. Support for QParallel can be added to

any multithreading library and language extension, including

OpenMP and OpenACC.

Index Terms—quantum computing parallel quantum comput-

ing space-time tradeoffs

I. INTRODUCTION

Quantum computers promise exponential speedups for cer-

tain computational tasks, including problems in chemistry [1]

and cryptography [2]. This applications require the use of

thousands of (error-corrected) qubits and millions of gates.

Multiple software frameworks and programming languages for

quantum computing have emerged [3]–[9] to assess whether

such speedups translate to an advantage of quantum computers

over classical supercomputers in practice.

These frameworks allow users to implement, test, and debug

quantum algorithms, before using the resulting implementation

to obtain estimates, e.g., for the number of quantum bits

(qubits) or operations required by the algorithm. Such resource

estimates are then used to focus algorithmic optimizations on

computational bottlenecks.

The compiler must make several choices when mapping the

high-level quantum program to the instruction set architecture

(ISA) of the target device. Examples are which quantum error

correction (QEC) procedure to employ and how many magic-

state factories to use. In particular, these choices result in

space-time tradeoffs, since (1) a longer computation requires

a larger-distance QEC code and therefore a larger physical-

per-logical qubit ratio, and (2) using more factories (to reduce

runtime) limits the space that is left on the quantum chip to

place algorithmic qubits. Moreover, since the rate at which

magic states are consumed is not constant throughout the

execution of a quantum program a priori, additional space-

time optimizations are necessary to ensure proper usage of

available resources.

For example, while peaks in magic state consumption rate

may be handled by magic state buffers, the buffer size required

may severely reduce the number of available algorithmic

qubits which, in turn, may prohibit other optimizations. In

such cases, it would thus be preferable to modify the quantum

program such that the magic state consumption rate is (closer

to) constant. Given these constraints, automatic parallelization

is a hard task and convenient mechanism for manual control

are preferable. This has also been observed in classical com-

puting which motivated solutions such as OpenMP [10].

Quantum programming languages should therefore make

space-time tradeoffs as straightforward as possible. In addition,

they have to work for applications that require thousands

of qubits and millions of gates. This is a challenge for

frameworks that ﬁrst create a data-structure describing a full

quantum circuit and run various optimizations on such data

structure. To this end, we propose an extension for quantum

programming languages that gives programmers ﬁne-grained

control over which parts of the quantum program run in

parallel and works for large scale applications.

Contributions: We introduce a language extension akin

to OpenMP that allows quantum programmers to investigate

various space-time tradeoffs more efﬁciently through explicit

parallelization. We implement our proposal as a Q# [3]

preprocessor and present several algorithmic benchmarks to

illustrate the beneﬁts of our language extension. Speciﬁcally,

our contributions are as follows.

•We introduce the QParallel language extension for

explicitly-parallel quantum programming. QParallel al-

lows programmers to remove ambiguities concerning

parallelism in current quantum programming languages

(see related work below).

•We provide a detailed description of the syntax and

semantics of our proposed language extension.

•We implement a prototype of QParallel in Q# to allow

programmers to deﬁne parallel regions explicitly based

on a language feature proposal [11].

•We present several examples and use cases that leverage

our language extension to achieve improvements in space-

time volume.

•We show how to improve the integration of our language

extension with the quantum software stack using a tool

arXiv:2210.03680v1 [quant-ph] 7 Oct 2022

that ﬁnds and visualizes critical paths in the quantum pro-

gram. This is especially valuable when the programmer

adding explicit parallelism has limited knowledge of the

codebase.

Related work: Existing high-level quantum programming

languages and frameworks [3]–[5], [7], [8] have been designed

under the assumption that parallelism is implicit. This leads to

1) unpredictable performance and space-time requirements,

and

2) unexpected interaction with features of the programming

language such as quantum memory management.

Moreover, this assumption makes it difﬁcult for programmers

to inﬂuence the parallelization strategy. We discuss these

points in more detail in the next section. Our work addresses

these issues by introducing a way for programmers to be

explicit about which sections of a quantum program should

be executed in parallel.

Our language extension is closely related to classical

libraries and language extensions for multithreading such

as OpenMP [10], OpenACC [12], and Thread Building

Blocks [13]. However, our extension is targeted at quantum

programming languages and thus addresses several quantum-

speciﬁc issues that arise in this context, including the interac-

tion of parallel constructs with quantum resource management

and the controlled execution of quantum subroutines.

Finally, recent work has introduced QMPI, an extension

of MPI supporting communication of quantum data, together

with a performance model to develop and analyze distributed

quantum programs [14]. Similarly, we show that some of

the existing work in classical high-performance computing

can be leveraged and adapted to solve problems in quantum

computing.

II. PARALLELISM AND PROGRAMMING LANGUAGES

In classical programming languages such as C++, loops

are sequential by default: No programmer would expect the

following code snippet (in C++) to run loop iterations in

parallel.

for (auto b : bits) {

f(b);

}

In contrast, for a very similar code fragment written in a

quantum programming language such as Q#, all loop iterations

may be executed in parallel on a quantum computer:

for (q in qubits) {

H(q);

}

While this may seem surprising, we believe that the reason for

this implicit assumption has its origin in so-called quantum

circuit diagrams (see below), which are often used to describe

simple quantum algorithms and which are inherently parallel.

In the evolution from quantum circuits to high-level pro-

gramming languages, this implicit assumption has remained

intact, resulting in discord between classical and quantum

programming.

|0i

Rφ

Rθ

Fig. 1: Example of a quantum circuit: Qubits are represented

by wires with time advancing from left to right. Operations on

qubits correspond to boxes and other symbols on the respective

wire(s).

A. From quantum circuits to code

In a quantum circuit, qubits are represented by horizontal

lines, with time advancing from left to right. Operations on

these qubits are depicted as boxes and symbols that are placed

on the respective lines, see Fig. 1 for an example. While

quantum circuits can be used to describe simple algorithms,

their capabilities concerning measurement feedback and other

classical control ﬂow are severely limited.

Quantum assembly languages such as OpenQASM were

introduced [15] to enable expressing simple mixed quantum-

classical programs such as quantum teleportation [16]. How-

ever, their support for classical control ﬂow is limited to con-

ditional gate applications (e.g., conditional on a measurement

outcome). In the meantime, multiple higher-level quantum

programming languages have been proposed [3], [4], [7], [8],

[17], [18] that, among other useful features, support a more

general classical control ﬂow.

B. Quantum memory management and parallelism

One of the main advantages of a high-level quantum pro-

gramming language is automatic memory management: In-

stead of having to allocate one array of qubits at the beginning

and then passing along the right qubits to every subroutine,

memory management allows programmers to allocate and

deallocate qubits inside subroutines.

There is, however, a crucial interaction between parallelism

and memory management in quantum computing: Depending

on the memory management strategy, the compiler (or the

run-time system) may introduce artiﬁcial dependencies, e.g.,

among loop iterations that would otherwise be subject to par-

allelism. As an example, consider the following code snippet:

for (q in qubits) {

Op(q);

}

Op is some quantum operation that takes a qubit as input.

If Op is in the native gate set of the target architecture, for

example, then this loop may be executed in parallel.

However, if Op temporarily allocates and then deallocates a

helper qubit, quantum memory management may decide to

reuse the same helper qubit for all iterations of the loop.

An example of this is given in Fig. 2 in which on the right

implementation of a controlled rotation gate is shown that uses

one helper qubit to avoid doubling the number of single-qubit

rotations, which induces a large overhead when implemented

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

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

10 玖币 0人已下载

立即下载

摘要：

QParallel:ExplicitParallelismforProgrammingQuantumComputersThomasH¨aner,VadymKliuchnikovy,MartinRoettelery,MathiasSoekenandAlexanderVaschilloyMicrosoftQuantum,SwitzerlandyMicrosoftQuantum,USAAbstractWepresentalanguageextensionforparallelquan-tumprogrammingto(1)removeambiguitiesconcerningparal-le...

展开>> 收起<<

QParallel Explicit Parallelism for Programming Quantum Computers Thomas H aner Vadym Kliuchnikovy Martin Roettelery Mathias Soekenand Alexander Vaschilloy.pdf

共9页,预览2页

还剩页未读，继续阅读

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

QParallel Explicit Parallelism for Programming Quantum Computers Thomas H aner Vadym Kliuchnikovy Martin Roettelery Mathias Soekenand Alexander Vaschilloy

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: