{"id":"arxiv/2604.19717","url":"https://arxiv.org/abs/2604.19717","tags":["quant-ph","cs.CC"],"score":0,"title":"Qubit Routing for (Almost) Free","domain":"quant-ph","source":"arxiv","authors":["Arianne Meijer-van de Griend"],"reviews":0,"subject":"quant-ph","summary":"In this paper, we give a mathematical proof that bounds the number of CNOT gates required to synthesize an $n$ qubit phase polynomial with $g$ terms to be at least $O(\\frac{gn}{\\max (\\log g, 1)})$ and at most $O(gn)$. However, when targeting restricted hardware, not all CNOTs are allowed. If we were to use SWAP-based methods to route the qubits on the architecture such that the earlier synthesized gates are natively allowed, we increase the number of CNOTs by a routing overhead factor of $O(\\log n) \\leq α\\leq O(n \\log^2 n)$. However, if we only synthesize allowed gates, we do not need to…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-04-21","reactions":{}}