Algorithmic Theory of Qubit Routing

Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto

doi:10.1007/978-3-031-38906-1_35

Algorithmic Theory of Qubit Routing

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

Department of Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Citations (Scopus)

Abstract

The qubit routing problem, also known as the swap minimization problem, is a (classical) combinatorial optimization problem that arises in the design of compilers of quantum programs. We study the qubit routing problem from the viewpoint of theoretical computer science, while most of the existing studies investigated the practical aspects. We concentrate on the linear nearest neighbor (LNN) architectures of quantum computers, in which the graph topology is a path. Our results are three-fold. (1) We prove that the qubit routing problem is NP-hard. (2) We give a fixed-parameter algorithm when the number of two-qubit gates is a parameter. (3) We give a polynomial-time algorithm when each qubit is involved in at most one two-qubit gate.

Original language	English
Title of host publication	Algorithms and Data Structures - 18th International Symposium, WADS 2023, Proceedings
Editors	Pat Morin, Subhash Suri
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	533-546
Number of pages	14
ISBN (Print)	9783031389054
DOIs	https://doi.org/10.1007/978-3-031-38906-1_35
Publication status	Published - 2023
Event	18th International Symposium on Algorithms and Data Structures, WADS 2023 - Montreal, Canada Duration: 2023 Jul 31 → 2023 Aug 2

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	14079 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	18th International Symposium on Algorithms and Data Structures, WADS 2023
Country/Territory	Canada
City	Montreal
Period	23/7/31 → 23/8/2

Keywords

Fixed-parameter tractability
Qubit allocation
Qubit routing

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-031-38906-1_35

Cite this

Ito, T., Kakimura, N., Kamiyama, N., Kobayashi, Y., & Okamoto, Y. (2023). Algorithmic Theory of Qubit Routing. In P. Morin, & S. Suri (Eds.), Algorithms and Data Structures - 18th International Symposium, WADS 2023, Proceedings (pp. 533-546). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14079 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-38906-1_35

Algorithmic Theory of Qubit Routing. / Ito, Takehiro; Kakimura, Naonori; Kamiyama, Naoyuki et al.
Algorithms and Data Structures - 18th International Symposium, WADS 2023, Proceedings. ed. / Pat Morin; Subhash Suri. Springer Science and Business Media Deutschland GmbH, 2023. p. 533-546 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14079 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Ito, T, Kakimura, N, Kamiyama, N, Kobayashi, Y & Okamoto, Y 2023, Algorithmic Theory of Qubit Routing. in P Morin & S Suri (eds), Algorithms and Data Structures - 18th International Symposium, WADS 2023, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14079 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 533-546, 18th International Symposium on Algorithms and Data Structures, WADS 2023, Montreal, Canada, 23/7/31. https://doi.org/10.1007/978-3-031-38906-1_35

Ito T, Kakimura N, Kamiyama N, Kobayashi Y, Okamoto Y. Algorithmic Theory of Qubit Routing. In Morin P, Suri S, editors, Algorithms and Data Structures - 18th International Symposium, WADS 2023, Proceedings. Springer Science and Business Media Deutschland GmbH. 2023. p. 533-546. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-38906-1_35

Ito, Takehiro ; Kakimura, Naonori ; Kamiyama, Naoyuki et al. / Algorithmic Theory of Qubit Routing. Algorithms and Data Structures - 18th International Symposium, WADS 2023, Proceedings. editor / Pat Morin ; Subhash Suri. Springer Science and Business Media Deutschland GmbH, 2023. pp. 533-546 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{7581c18fa11444bb928aac67da62d6d8,

title = "Algorithmic Theory of Qubit Routing",

abstract = "The qubit routing problem, also known as the swap minimization problem, is a (classical) combinatorial optimization problem that arises in the design of compilers of quantum programs. We study the qubit routing problem from the viewpoint of theoretical computer science, while most of the existing studies investigated the practical aspects. We concentrate on the linear nearest neighbor (LNN) architectures of quantum computers, in which the graph topology is a path. Our results are three-fold. (1) We prove that the qubit routing problem is NP-hard. (2) We give a fixed-parameter algorithm when the number of two-qubit gates is a parameter. (3) We give a polynomial-time algorithm when each qubit is involved in at most one two-qubit gate.",

keywords = "Fixed-parameter tractability, Qubit allocation, Qubit routing",

author = "Takehiro Ito and Naonori Kakimura and Naoyuki Kamiyama and Yusuke Kobayashi and Yoshio Okamoto",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2023.; 18th International Symposium on Algorithms and Data Structures, WADS 2023 ; Conference date: 31-07-2023 Through 02-08-2023",

year = "2023",

doi = "10.1007/978-3-031-38906-1_35",

language = "English",

isbn = "9783031389054",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "533--546",

editor = "Pat Morin and Subhash Suri",

booktitle = "Algorithms and Data Structures - 18th International Symposium, WADS 2023, Proceedings",

}

TY - GEN

T1 - Algorithmic Theory of Qubit Routing

AU - Ito, Takehiro

AU - Kakimura, Naonori

AU - Kamiyama, Naoyuki

AU - Kobayashi, Yusuke

AU - Okamoto, Yoshio

N1 - Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Switzerland AG 2023.

PY - 2023

Y1 - 2023

N2 - The qubit routing problem, also known as the swap minimization problem, is a (classical) combinatorial optimization problem that arises in the design of compilers of quantum programs. We study the qubit routing problem from the viewpoint of theoretical computer science, while most of the existing studies investigated the practical aspects. We concentrate on the linear nearest neighbor (LNN) architectures of quantum computers, in which the graph topology is a path. Our results are three-fold. (1) We prove that the qubit routing problem is NP-hard. (2) We give a fixed-parameter algorithm when the number of two-qubit gates is a parameter. (3) We give a polynomial-time algorithm when each qubit is involved in at most one two-qubit gate.

AB - The qubit routing problem, also known as the swap minimization problem, is a (classical) combinatorial optimization problem that arises in the design of compilers of quantum programs. We study the qubit routing problem from the viewpoint of theoretical computer science, while most of the existing studies investigated the practical aspects. We concentrate on the linear nearest neighbor (LNN) architectures of quantum computers, in which the graph topology is a path. Our results are three-fold. (1) We prove that the qubit routing problem is NP-hard. (2) We give a fixed-parameter algorithm when the number of two-qubit gates is a parameter. (3) We give a polynomial-time algorithm when each qubit is involved in at most one two-qubit gate.

KW - Fixed-parameter tractability

KW - Qubit allocation

KW - Qubit routing

UR - http://www.scopus.com/inward/record.url?scp=85172737649&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85172737649&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-38906-1_35

DO - 10.1007/978-3-031-38906-1_35

M3 - Conference contribution

AN - SCOPUS:85172737649

SN - 9783031389054

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 533

EP - 546

BT - Algorithms and Data Structures - 18th International Symposium, WADS 2023, Proceedings

A2 - Morin, Pat

A2 - Suri, Subhash

PB - Springer Science and Business Media Deutschland GmbH

T2 - 18th International Symposium on Algorithms and Data Structures, WADS 2023

Y2 - 31 July 2023 through 2 August 2023

ER -