Qubit Routing for (Almost) Free
2026-04-21 • Computational Complexity
Computational Complexity
AI summaryⓘ
The authors mathematically find the minimum and maximum number of CNOT gates needed to build a certain kind of quantum operation called a phase polynomial on multiple qubits. When using real quantum hardware with limits on which gates are allowed, moving qubits around can add extra CNOT gates, making the process less efficient. They show that if you only use gates allowed by the hardware, you can avoid this extra cost. Also, because combining these phase polynomial gates with another set of gates called Hadamards is enough for universal quantum computing, routing qubits doesn’t add much overhead.
CNOT gatesphase polynomialquantum gate synthesisrouting overheadqubit architectureSWAP gatesHadamard gatesuniversal gate setquantum circuitsgate routing
Authors
Arianne Meijer-van de Griend
Abstract
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 route any qubits. Moreover, in that case the routing overhead factor is $1 \leq α\leq 4 \simeq O(1)$. Additionally, since phase polynomials and Hadamard gates together form a universal gate set, we get qubit routing for almost free.