Parallel Token Swapping for Qubit Routing
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912962051047424 |
|---|---|
| author | Bansal, Ishan Günlük, Oktay Shapley, Richard |
| author_facet | Bansal, Ishan Günlük, Oktay Shapley, Richard |
| contents | In this paper we study a combinatorial reconfiguration problem that involves finding an optimal sequence of swaps to move an initial configuration of tokens that are placed on the vertices of a graph to a final desired one. This problem arises as a crucial step in reducing the depth of a quantum circuit when compiling a quantum algorithm. We provide the first known constant factor approximation algorithms for the parallel token swapping problem on graph topologies that are commonly found in modern quantum computers, including cycle graphs, subdivided star graphs, and grid graphs. We also study the so-called stretch factor of a natural lower bound to the problem, which has been shown to be useful when designing heuristics for the qubit routing problem. Finally, we study the colored version of this reconfiguration problem where some tokens share the same color and are considered indistinguishable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_18581 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Parallel Token Swapping for Qubit Routing Bansal, Ishan Günlük, Oktay Shapley, Richard Data Structures and Algorithms Discrete Mathematics Optimization and Control Quantum Physics In this paper we study a combinatorial reconfiguration problem that involves finding an optimal sequence of swaps to move an initial configuration of tokens that are placed on the vertices of a graph to a final desired one. This problem arises as a crucial step in reducing the depth of a quantum circuit when compiling a quantum algorithm. We provide the first known constant factor approximation algorithms for the parallel token swapping problem on graph topologies that are commonly found in modern quantum computers, including cycle graphs, subdivided star graphs, and grid graphs. We also study the so-called stretch factor of a natural lower bound to the problem, which has been shown to be useful when designing heuristics for the qubit routing problem. Finally, we study the colored version of this reconfiguration problem where some tokens share the same color and are considered indistinguishable. |
| title | Parallel Token Swapping for Qubit Routing |
| topic | Data Structures and Algorithms Discrete Mathematics Optimization and Control Quantum Physics |
| url | https://arxiv.org/abs/2411.18581 |