{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiccz5czlswzhgcgzaljd3ujb2djxtw7f67cummhwraqnfmjzous6u",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mk2qjxkunkr2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.19717v1",
  "publishedAt": "2026-04-22T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Arianne Meijer-van de Griend"
  ],
  "textContent": "**Authors:** Arianne Meijer-van de Griend\n\nIn 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.",
  "title": "Qubit Routing for (Almost) Free"
}