Optimized Qubit Routing for Commuting Gates via Integer Programming
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909691458617344 |
|---|---|
| author | Stargalla, Moritz Wagner, Friedrich |
| author_facet | Stargalla, Moritz Wagner, Friedrich |
| contents | Quantum computers promise to outperform their classical counterparts at certain tasks. However, existing quantum devices are error-prone and restricted in size. Thus, effective compilation methods are crucial to exploit limited quantum resources. In this work, we address the problem of qubit routing for commuting gates, which arises, for example, during the compilation of the well-known Quantum Approximate Optimization Algorithm. We propose a two-step decomposition approach based on integer programming, which is guaranteed to return an optimal solution. To justify the use of integer programming, we prove NP-hardness of the underlying optimization problem. Furthermore, we derive asymptotic upper and lower bounds on the quality of a solution. We develop several integer programming models and derive linear descriptions of related polytopes, which generalize to applications beyond this work. Finally, we conduct a computational study showing that our approach outperforms existing heuristics in terms of quality and exact methods in terms of runtime. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_12199 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimized Qubit Routing for Commuting Gates via Integer Programming Stargalla, Moritz Wagner, Friedrich Optimization and Control Quantum Physics Quantum computers promise to outperform their classical counterparts at certain tasks. However, existing quantum devices are error-prone and restricted in size. Thus, effective compilation methods are crucial to exploit limited quantum resources. In this work, we address the problem of qubit routing for commuting gates, which arises, for example, during the compilation of the well-known Quantum Approximate Optimization Algorithm. We propose a two-step decomposition approach based on integer programming, which is guaranteed to return an optimal solution. To justify the use of integer programming, we prove NP-hardness of the underlying optimization problem. Furthermore, we derive asymptotic upper and lower bounds on the quality of a solution. We develop several integer programming models and derive linear descriptions of related polytopes, which generalize to applications beyond this work. Finally, we conduct a computational study showing that our approach outperforms existing heuristics in terms of quality and exact methods in terms of runtime. |
| title | Optimized Qubit Routing for Commuting Gates via Integer Programming |
| topic | Optimization and Control Quantum Physics |
| url | https://arxiv.org/abs/2507.12199 |