Parallel token swapping for qubit routing

DOI10.1016/J.DAM.2025.08.005MaRDI QIDQ6927976zbMATH OpenFDO

Authors Ishan Bansal, Oktay Günlük, Richard Shapley

Publication date 17 September 2025

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2025.08.005

zbMATH Keywords

approximation algorithmscombinatorial reconfigurationqubit routingtoken swapping

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Cites work

• Approximation and hardness of token swapping
• Complexity of token swapping and its variants
• Coordinated motion planning: reconfiguring a swarm of labeled robots with bounded stretch
• Hardness of token swapping on trees
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 1339500 (Why is no real title available?)
• scientific article; zbMATH DE number 7559364 (Why is no real title available?)
• Improving quantum computation by optimized qubit routing
• On the qubit routing problem
• Optimal Bounds for Matching Routing on Trees
• Quantum computation and quantum information. 10th anniversary edition
• Routing Permutations on Graphs via Matchings
• Swapping labeled tokens on graphs
• The complexity of finding minimum-length generator sequences
• The time complexity of the token swapping problem and its parallel variants
• Whitney numbers of the second kind for the star poset

This page was built for publication: Parallel token swapping for qubit routing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6927976)