Qubit Routing for (Almost) Free

• URL: http://arxiv.org/abs/2604.19717v1
• Date: Tue, 21 Apr 2026 17:43:44 GMT
• Title: Qubit Routing for (Almost) Free
• Abstract summary: CNOT gates are required to synthesize an $n$ qubit with $g$ terms to be at least $O(fracgnmax (log g, 1))$.<n>When targeting restricted hardware, not all CNOTs are allowed.<n>Phases and Hadamard gates together form a universal gate set, we get qubit routing for almost free.
• Score: 2.0305676256390934
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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.

Related papers

• Efficient Fuzzy Private Set Intersection from Secret-shared OPRF [41.88845480337768]
  Fuzzy PSI (FPSI) is a PSI variant where the receiver learns the items $q in Q$ for which there exists some $w in W$ under a given distance metric.<n>We propose efficient FPSI protocols for $L_p in [1, infty]$ distance metrics.<n>Our protocols achieve linear communication and computation complexity in the set sizes $m,n$, the dimension $d$, and the distance threshold $$.
  arXiv  Detail & Related papers  (2026-04-16T11:51:25Z)
• Multi-qubit Toffoli with exponentially fewer T gates [3.5887330421214063]
  We show how to get away with exponentially fewer $T$ gates, at the cost of incurring a tiny $1/mathrmpoly(n)$ error.<n>More precisely, the $n$-qubit Toffoli gate can be implemented to within error $epsilon$ in the diamond distance by a randomly chosen Clifford+$T$ circuit.
  arXiv  Detail & Related papers  (2025-10-08T16:56:23Z)
• Multi-Controlled Quantum Gates in Linear Nearest Neighbor [0.0]
  Multi-controlled single-target (MC) gates are crucial building blocks for varied quantum algorithms.<n>Here we describe a method which implements MC gates using no more than $sim 4k+8n$ CNOT gates.<n>Our method provides circuits that tend to require fewer CNOT gates than our upper bound for almost any given instance of MC gates.
  arXiv  Detail & Related papers  (2025-05-31T20:01:21Z)
• On Exact Sizes of Minimal CNOT Circuits [2.831145157553215]
  We consider circuits of CNOT gates, which are fundamental binary gates in reversible and quantum computing.<n>We develop a new approach for computing distances in $G_n$, allowing us to synthesize minimum circuits that were previously beyond reach.<n>We also confirm a conjecture that long cycle permutations lie at distance $3(n-1)$, for all $nleq 8$, extending the previous bound of $nleq 5$.
  arXiv  Detail & Related papers  (2025-03-03T12:20:48Z)
• Efficient Circuit-Based Quantum State Tomography via Sparse Entry Optimization [0.6008132390640295]
  We propose an efficient circuit-based quantum state tomography scheme to reconstruct $n$-qubit states with $k$ nonzero entries. We provide an upper limit on the number of CNOT gates based on the nonzero entries' positions in $|psirangle$.
  arXiv  Detail & Related papers  (2024-07-29T02:59:13Z)
• Efficient Fault-Tolerant Single Qubit Gate Approximation And Universal Quantum Computation Without Using The Solovay-Kitaev Theorem [0.0]
  A recent improvement of the Solovay-Kitaev theorem implies that to approximate any single-qubit gate to an accuracy of $epsilon > 0$ requires $textO(logc[1/epsilon)$ quantum gates with $c > 1.44042$. Here I give a partial answer to this question by showing that this is possible using $textO(log[/epsilon] loglog[/epsilon] cdots)$ FT gates chosen from a finite set depending on the value of $
  arXiv  Detail & Related papers  (2024-06-07T11:21:05Z)
• Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates [40.56175933029223]
  We propose two types of constant-depth constructions for implementing Uniformly Controlled Gates. We obtain constant-depth circuits for the quantum counterparts of read-only and read-write memory devices.
  arXiv  Detail & Related papers  (2023-08-16T17:54:56Z)
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
  We show that a novel deterministic method for preparing arbitrary quantum states requires fewer quantum resources than previous methods. We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations.
  arXiv  Detail & Related papers  (2023-03-03T18:23:20Z)
• Universal qudit gate synthesis for transmons [44.22241766275732]
  We design a superconducting qudit-based quantum processor. We propose a universal gate set featuring a two-qudit cross-resonance entangling gate. We numerically demonstrate the synthesis of $rm SU(16)$ gates for noisy quantum hardware.
  arXiv  Detail & Related papers  (2022-12-08T18:59:53Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  For every $delta>0,$ we construct CNF and formulas of size with approximate degree $Omega(n1-delta),$ essentially matching the trivial upper bound of $n. We show that for every $delta>0$, these models require $Omega(n1-delta)$, $Omega(n/4kk2)1-delta$, and $Omega(n/4kk2)1-delta$, respectively.
  arXiv  Detail & Related papers  (2022-09-04T10:01:39Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.