Curator's Take
This research tackles one of quantum computing's most persistent practical challenges: the overhead cost of moving qubits around to perform operations on hardware with limited connectivity. The authors demonstrate that by synthesizing quantum circuits to directly use only the gates natively allowed by the hardware architecture, they can achieve near-constant routing overhead rather than the logarithmic to polynomial scaling typical of SWAP-based approaches. This "routing for almost free" approach could significantly reduce gate counts in real quantum algorithms, making better use of today's noisy intermediate-scale quantum devices where every extra gate matters. The work is particularly valuable because it applies to phase polynomials combined with Hadamard gates, which form a universal gate set capable of implementing any quantum algorithm.
— Mark Eatherly
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 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.