2026/04/21 by Arianne Meijer-van de Griend · 1 voice
Computer Science · Physics and Astronomy · #Controlled NOT gate #Cryptography and Data Security #Hadamard transform #Overhead (engineering) #Polynomial and algebraic computation #Quantum Computing Algorithms and Architecture #Qubit #Routing (electronic design automation) #Topology (electrical circuits) #cs.CC #quant-ph
paper · pdf · doi:10.48550/arxiv.2604.19717
openalex publication_date 2026/04/21 · arxiv published 2026/04/21 · arxiv updated 2026/04/21 · openalex created_date 2026/04/23 · openalex updated_date 2026/07/28
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((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) ≤ α≤ O(n log2 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 ≤ α≤ 4 ≃ O(1). Additionally, since phase polynomials and Hadamard gates together form a universal gate set, we get qubit routing for almost free.