Robust Qubit Mapping Algorithm via Double-Source Optimal Routing on Large Quantum Circuits

2025-05-03 0 0 2.24MB 26 页 10玖币

侵权投诉

Robust bit Mapping Algorithm via Double-Source Optimal

Routing on Large antum Circuits

CHIN-YI CHENG, Department of Electrical Engineering, National Taiwan University, Taiwan (R.O.C.)

CHIEN-YI YANG, Department of Computer Science and Engineering, University of California San Diego,

USA

YI-HSIANG KUO, Graduate Institute of Electronics Engineering, National Taiwan University, Taiwan (R.O.C.)

REN-CHU WANG, College of Computing, The Georgia Institute of Technology, USA

HAO-CHUNG CHENG

∗†‡

,Department of Electrical Engineering and Graduate Institute of Communica-

tion Engineering, National Taiwan University, Taiwan (R.O.C.)

CHUNG-YANG (RIC) HUANG

,Graduate Institute of Electronics Engineering, National Taiwan

University, Taiwan (R.O.C.)

Qubit Mapping is a critical aspect of implementing quantum circuits on real hardware devices. Currently, the

existing algorithms for qubit mapping encounter diculties when dealing with larger circuit sizes involving

hundreds of qubits. In this paper, we introduce an innovative qubit mapping algorithm, Duostra, tailored to

address the challenge of implementing large-scale quantum circuits on real hardware devices with limited

connectivity. Duostra operates by eciently determining optimal paths for double-qubit gates and inserting

SWAP gates accordingly to implement the double-qubit operations on real devices. Together with two heuristic

scheduling algorithms, the Limitedly-Exhausitive (LE) Search and the Shortest-Path (SP) Estimation, it yields

results of good quality within a reasonable runtime, thereby striving toward achieving quantum advantage.

Experimental results showcase our algorithm’s superiority, especially for large circuits beyond the NISQ era.

For example, on large circuits with more than 50 qubits, we can reduce the mapping cost on an average 21.75%

over the virtual best results among QMAP, t

|𝑘𝑒𝑡⟩

, Qiskit and SABRE. Besides, for mid-size circuits such as

the SABRE-large benchmark, we improve the mapping costs by 4.5%, 5.2%, 16.3%, 20.7%, and 25.7%, when

compared to QMAP, TOQM, t|𝑘𝑒𝑡 ⟩, Qiskit, and SABRE, respectively.

CCS Concepts: •Computer systems organization

→

Quantum computing;•Hardware

→

Physical

synthesis.

Additional Key Words and Phrases: Quantum Compilation, Qubit Mapping, Scalability, Local Optimal Solution

∗Also with Center for Quantum Science and Engineering, National Taiwan University.

†Also with Physics Division and Mathematics Division, National Center for Theoretical Sciences.

‡Also with Hon Hai (Foxconn) Quantum Computing Center.

§Also with Department of Electrical Engineering, National Taiwan University.

Authors’ addresses: Chin-Yi Cheng, Department of Electrical Engineering, National Taiwan University, Taiwan (R.O.C.),

r10921132@ntu.edu.tw; Chien-Yi Yang, Department of Computer Science and Engineering, University of California San

Diego, USA, chy036@ucsd.edu; Yi-Hsiang Kuo, Graduate Institute of Electronics Engineering, National Taiwan University,

Taiwan (R.O.C.), r12943104@ntu.edu.tw; Ren-Chu Wang, College of Computing, The Georgia Institute of Technology,

USA, rentruewang@gatech.edu; Hao-Chung Cheng, Department of Electrical Engineering and Graduate Institute of

Communication Engineering, National Taiwan University, Taiwan (R.O.C.), haochung.ch@gmail.com; Chung-Yang (Ric)

Huang, Graduate Institute of Electronics Engineering, National Taiwan University, Taiwan (R.O.C.), cyhuang@ntu.edu.tw.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee

provided that copies are not made or distributed for prot or commercial advantage and that copies bear this notice and

the full citation on the rst page. Copyrights for components of this work owned by others than ACM must be honored.

Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires

prior specic permission and/or a fee. Request permissions from permissions@acm.org.

ACM 2643-6817/2024/8-ART

https://doi.org/10.1145/3680291

ACM Trans. Quantum Comput., Vol. , No. , Article . Publication date: August 2024.

arXiv:2210.01306v5 [quant-ph] 3 Aug 2024

2 Chin-Yi Cheng, Chien-Yi Yang, Yi-Hsiang Kuo, Ren-Chu Wang, Hao-Chung Cheng, and Chung-Yang (Ric) Huang

Fig. 1. The topology of ibmq_washington, retrieved from [8]

ACM Reference Format:

Chin-Yi Cheng, Chien-Yi Yang, Yi-Hsiang Kuo, Ren-Chu Wang, Hao-Chung Cheng, and Chung-Yang (Ric)

Huang. 2024. Robust Qubit Mapping Algorithm via Double-Source Optimal Routing on Large Quantum

Circuits. ACM Trans. Quantum Comput. , (August 2024), 26 pages. https://doi.org/10.1145/3680291

1 INTRODUCTION

The ultimate goal of quantum computing is to outperform the classical algorithms exponentially

in solving real-world intractable problems [

], including Quantum Communication [

], Quantum

Cryptography [

], and Quantum Machine Learning [

], etc. Recent progress in quantum computing

devices has sparked hope for this dream to become a reality. For instance, IBM Condor has reached

a milestone of 1,121 qubits, tripling its previous generation, Osprey, from the previous year. This is

only about 1

2of the 2048 qubits needed for the Quantum Fourier Transform (QFT) to break the

RSA-1024 encryption [

], and approximately 1

30 of the 255

6qubits required for the discrete

logarithms over elliptic curves (e.g., Curve25519) to solve the Bitcoin encryption [7].

However, the dream of achieving the quantum advantage can be seriously deferred by the

“connectivity constraints” of modern quantum computing devices. Taking the ibmq_washington

quantum computer of which the topology is shown in Fig. 1 as an example, each of its qubits (i.e.

a vertex in the graph) is connected to at most three adjacent qubits. Therefore, when a quantum

algorithm involves a quantum operation between two non-adjacent qubits, say qubits 0 and 126 at

the extreme, we will need a long sequence of swap operations to bring the computation to a pair of

adjacent qubits, say qubits 61 and 62. This will signicantly increase the demand for the number of

qubits and, even worse, lead to a much longer execution time for the quantum circuit. Therefore,

intelligently mapping the quantum circuit to the physical qubits, known as the “qubit mapping

problem,” will be one of the most crucial steps in achieving the quantum advantage.

The qubit mapping problem involves an initial placement of the logical qubits to the physical

ones, and subsequent SWAP insertions to bring the computations of multiple qubit gates to adjacent

qubits. The objective is to improve the circuit delity. Common approaches include reducing the

number of SWAPs and thus optimizing the execution time of the quantum circuit and mitigating

the error of each gate and qubit. Siraichi et al. [

] have shown qubit mapping to be an NP-complete

problem.

Earlier algorithms [

–

] attempted to minimize the number of additional SWAP gates with

the mapping of qubits to the Linear Nearest Neighbor (LNN) structure. Booth et al. [

] even

ACM Trans. Quantum Comput., Vol. , No. , Article . Publication date: August 2024.

Robust bit Mapping Algorithm via Double-Source Optimal Routing on Large antum Circuits 3

transformed the mapping into a mathematical problem and utilized solvers to obtain feasible results.

However, modern quantum computing devices in the NISQ era are mostly in lattice structures, which

oer higher routing exibility than the LNN structure. Therefore, the aforementioned approaches

could only achieve sub-optimal solutions for the qubit mapping problem.

To realize the qubit mapping on the NISQ devices, Siraichi et al. [

] introduced a straightforward

heuristic approach that worked on the lattice structure of the earlier generations of the IBM

quantum computers. de Almeida et al. [

] relied on the matrix cost to solve CNOT mappings on

IBM QX device. However, as the qubit interaction of these early-day machines is unidirectional, their

algorithms are not suitable for modern quantum devices that pose bidirectional qubit interactions.

There were studies focusing on reducing depth overheads besides the number of SWAP gates.

Venturelli et al. [

] used exhaustive-search temporal planners to schedule gates. Zulehner et al.

[

] and Matsuo et al. [

] then proposed a multi-step approach with a depth-based layer

partitioning and A* as the underlying search algorithm. Additionally, Peham et al. [

] explored the

sub-architectures of the quantum devices in order to devise a suitable initial placement strategy for

the qubit mapping problem. Notably, [

] and [

] have been integrated into the QMAP framework

[

], which delivered high-quality results for relatively small quantum circuits (less than 50 qubits).

However, when applied to larger circuits, QMAP will suer in lengthier program runtime and thus

the mapping outcomes are not as eective. Li et al. [

] introduced SABRE

, employing a heuristic

based on shortest path costs and look-ahead techniques to minimize the circuit depth of the quantum

circuits. Zhu et al. [

] and Jiang et al. [

] improved SABRE by lookahead methods. In addition to

SABRE-inspired research, Guerreschi et al. [

] also introduced a technique aimed at minimizing the

overhead of inserted SWAPs. This method involved initially organizing quantum operations based

on logical dependencies, followed by rescheduling according to physical constraints. Nonetheless,

when compared to the subsequent advancements, their program runtime and/or the quality of the

solution are inferior.

To counter the solution quality problems of the above-mentioned heuristic-based methods,

several researchers proposed methodologies that rendered the exact solution for the optimal

result with respect to the number of inserted SWAPs. In addition to the straightforward heuristic

approach, Siraichi et al. [

] also presented an exhaustive computation based on the dynamic

programming algorithm. However, it comes with the complexity of

𝑂((𝑄

)2)

, where

𝑄

is the

number of qubits, and thus is not applicable for larger quantum circuits. Some other exact-solution

approaches formulated the qubit mapping problem into a satisability problem. Wille et al. et al.

[

] utilized the Satisability Modulo Theories (SMT) solver together with the pseudo-Boolean

optimizer to minimize the inserted SWAP gates. Tan and Cong [

] constructed a gate-dependency

graph and guaranteed optimality for objectives either in circuit depths or SWAP counts via an SMT

solver named OLSQ. Their follow-up works, namely OLSQ-GA [

] and OLSQ2 [

], claimed to

enlarge the scalability to 54 qubits. Moreover, Molavi et al. [

] utilized maximum satisability

(MaxSAT) to minimize the mapping cost. However, these exact methods, although being able to

achieve optimality for small circuits, are inferior to the heuristic methods in large circuits. It is

often that they will abort on large circuits due to the complex exhausting search process.

Another technique to improve the solution quality of the qubit mapping is to dene the timing

model for distinct gate types so that the mapping cost can better approximate the execution time

of the quantum circuit on the real device. Consequently, the optimal qubit mapping solution can

ensure the better delity of the quantum computation. Deng et al. [

] proposed a timing model for

super-conducting devices that dened the timing costs of the single-qubit, double-qubit, and SWAP

gates to be 1, 2, and 6 units, respectively. The mapping cost is therefore calculated based on these

1SWAP-based BidiREctional heuristic search algorithm

ACM Trans. Quantum Comput., Vol. , No. , Article . Publication date: August 2024.

4 Chin-Yi Cheng, Chien-Yi Yang, Yi-Hsiang Kuo, Ren-Chu Wang, Hao-Chung Cheng, and Chung-Yang (Ric) Huang

timing costs. They further introduced the concept of lock time for the busy qubits and presented it

as the CODAR

algorithm to optimize the total circuit execution time. On the other hand, Zhang

et al. in [

] adopted a similar timing model

and devised an improved algorithm, Time-Optimal

Qubit Mapping (TOQM), with estimated cost to achieve better results for the mapping. Lao et al.

[

] proposed a Qmap

algorithm for Surface-17, a 17-qubit quantum computer. To accommodate

the specic controlling mechanism of this device, they imposed frequency constraints into mapping

costs and minimized the execution time by exhaustive search on the potential routings. However,

their runtime complexity can be as high as

𝑂(𝑔√𝑛

√𝑛)

, where

𝑔

and

𝑛

are numbers of gates and

qubits respectively. Although the above-mentioned algorithms claimed to achieve optimal mapping

solutions, the runtime of these algorithms was very long due to the fact that they needed to

calculate the costs of all the potential swapping candidates in each iteration when selecting a SWAP.

Consequently, they could only handle mapping problems up to 50 qubits, which is much smaller

than the number of required qubits for achieving quantum advantage.

This paper introduces a robust qubit mapping framework designed for large circuits with hun-

dreds of qubits and beyond. Our key contributions are two-fold:

(1)

While many previous approaches such as [

], [

], and [

] have exponential or sub-

exponential complexities in nding the optimal SWAP insertion sequence, we propose a

qubit mapping framework that decomposes the optimization ow into three components: an

𝑂(𝑛)

initial mapping strategy, an

𝑂(𝑛log 𝑛)

Duostra router that can guarantee the optimal

mapping solution for a given double-qubit gate, and a heuristic scheduler that can either

exploit a limited-depth exhaustive search or a shortest-path estimation. The overall algorithm

strikes a good balance that it can obtain the near-optimal solution for smaller circuits as well

as scale up to handle very large-scale circuits.

(2)

Unlike other previous algorithms that optimize the mapping solutions by considering static

costs derived from the device topologies (e.g. SABRE), our proposed Duostra algorithm

dynamically computes the “occupied time” (dened in section 3.2.1) during the nding of

the routing paths. It can not only ensure the qubit mapping optimality for a double-qubit

gate, but also update the coupling constraints for the other double-qubit gates so that the

scheduler can further optimize the mapping for the subsequent routing paths.

The experimental results indicate that in the mid-size test cases within the SABRE-large test

suite [

], our approach achieves an average cost improvement by 4.5%, 5.2%, 16.3%, 20.7%, and

25.7%, when compared to QMAP, TOQM, t

|𝑘𝑒𝑡 ⟩

, Qiskit, and SABRE, respectively. Additionally,

those results are generated within a runtime of 5 minutes. Regarding scalability, Duostra surpasses

IBM Qiskit, QMAP, t

|𝑘𝑒𝑡 ⟩

, and SABRE on mapping cost for most large quantum circuits, including

Galois Field (GF), inst, classical Electronic Design Automation (EDA) benchmark circuits [

], adder,

and qugan. Our framework exhibits an average improvement of 21.75% over the best results among

IBM Qiskit, QMAP, t

|𝑘𝑒𝑡 ⟩

, and SABRE across 39 large circuits (i.e. qubits > 50), with nearly the

shortest runtime. Furthermore, our method can handle problem sizes up to 11,969-qubit QFT within

3 hours (with time complexity

𝑂(𝑛2.8)

, where

𝑛

denotes the numbers of qubits). In summary, our

proposed qubit mapping framework oers a solution for large-scale quantum circuits by eciently

implementing local-optimal quantum algorithms on a non-fully connected quantum device.

The rest of the paper is organized as follows. We rst explain the qubit mapping problem in

Section 2. The proposed framework is detailed in Section 3, and specically the proof for the

optimality of the Duostra algorithm is provided in Section 4. We present the experiment results in

2COntext-sensitive and Duration-Aware Remapping algorithm

31, 1, and 3 units for the single-qubit, double-qubit, and SWAP gates

4Note: Qmap [39] and QMAP [27] are two dierent studies.

ACM Trans. Quantum Comput., Vol. , No. , Article . Publication date: August 2024.

Robust bit Mapping Algorithm via Double-Source Optimal Routing on Large antum Circuits 5

G4 G5

(a) An example of a logical circuit

Q0Q1Q2Q3

(b) An example of a topology

Fig. 2. An example of the qubit mapping problem

Section 5, and conclude the paper in Section 6. The source code

of our method is embedded in the

tool Qsyn [41].

2 QUBIT MAPPING PROBLEM

The qubit mapping problem is to schedule the operations of a quantum circuit and then assign them

to the qubits of a quantum computer with a given topology (e.g. Fig. 1). The circuit is composed of

gates from a quantum cell library (e.g. Cliord+T library). However, we need to insert additional

SWAP gates to bring the inputs, which are logically connected but physically apart, of a double-

qubit

gate to the adjacent qubits. This is because the computation of a double-qubit gate can only

be applied on adjacent qubits on the actual hardware device (called “coupling constraint”), and

the topology of the physical device often limits its qubits to interact with only a small number of

adjacent neighbors (e.g. 1to 3for ibmq_washington quantum computer as shown in Fig. 1).

Taking Fig. 2 as an example of the qubit mapping problem, we denote the logical qubits (i.e.

the qubits for a quantum circuit) in lowercase as

𝑞0

𝑞6

in Fig. 2a, and the physical qubits (i.e.

the qubits on the actual device) in uppercase as

𝑄0

𝑄7

in Fig. 2b. Let’s assume that after the

initial mapping, the inputs of the double-qubit gate

𝐺

5, that is,

𝑞1

and

𝑞2

, are mapped to two

non-adjacent physical qubits,

𝑄2

and

𝑄6

(explained later in Section 3.1 for details). We can insert

SWAPs along a path, for example,

𝑄2, 𝑄3, 𝑄4, 𝑄5, 𝑄6

, to bring these two inputs to adjacency. Clearly,

there is another path

𝑄2, 𝑄1, 𝑄0, 𝑄7, 𝑄6

to resolve the coupling constraint of

𝐺

5. By choosing one of

these two paths, we will employ dierent numbers of SWAPs and thus relocate the inputs of the

subsequent double-qubit gates

𝐺

6and

𝐺

7to dierent physical qubits. This will lead to dierent

execution time of the circuit and therefore dierent error probabilities.

A SWAP is composed of three consecutive CX gates, where the middle CX possesses opposite

control and target qubits with respect to the other two CX gates. The insertion of the SWAP gates

greatly increases the gate counts and execution time of the quantum circuit. Therefore, the objective

5https://github.com/DVLab-NTU/qsyn

6Without loss of generality, we assume there are only single- and double-qubit gates in the quantum cell library.

ACM Trans. Quantum Comput., Vol. , No. , Article . Publication date: August 2024.

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

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

10 玖币 0人已下载

立即下载

摘要：

RobustQubitMappingAlgorithmviaDouble-SourceOptimalRoutingonLargeQuantumCircuitsCHIN-YICHENG,DepartmentofElectricalEngineering,NationalTaiwanUniversity,Taiwan(R.O.C.)CHIEN-YIYANG,DepartmentofComputerScienceandEngineering,UniversityofCaliforniaSanDiego,USAYI-HSIANGKUO,GraduateInstituteofElectronicsEng...

展开>> 收起<<

Robust Qubit Mapping Algorithm via Double-Source Optimal Routing on Large Quantum Circuits.pdf

共26页,预览5页

还剩页未读，继续阅读

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

Robust Qubit Mapping Algorithm via Double-Source Optimal Routing on Large Quantum Circuits

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: