notesum.ai

Published at November 27

Parallel Token Swapping for Qubit Routing

cs.DS

cs.DM

quant-ph

Released Date: November 27, 2024

Authors: Ishan Bansal¹, Oktay Günlük², Richard Shapley³

Aff.: ¹Amazon; ²Industrial and Systems Engineering, Georgia Institute of Technology; ³Operations Research and Information Engineering, Cornell University

Arxiv: http://arxiv.org/abs/2411.18581v1

	(PTS)	stretch	colored (PTS)
Line Graphs	$OPT+1$ [12]	$\mathbf{2}$	$OPT+1$ [12]
Even Cycle Graphs	$\mathbf{2OPT}$	$\mathbf{n}$	$\mathbf{2OPT}$ incomplete (PTS)
Odd Cycle Graphs	$\mathbf{2OPT+1}$	$\mathbf{n}$	$\mathbf{2OPT+1}$ incomplete (PTS)
Subdivided Stars Graphs	$\mathbf{4OPT+\min\{OPT,h}+1\}$	$\mathbf{\Theta(h)}$	$\mathbf{4OPT+\min\{OPT,h\}+1}$
Ladder Graphs	$\mathbf{2OPT+1}$	—	$\mathbf{2OPT+1}$
Grid Graphs	$\mathbf{2OPT+2h}$	—	$\mathbf{2OPT+2h}$