arxiv: 2604.19717 · v1 · submitted 2026-04-21 · 🪐 quant-ph · cs.CC

Recognition: unknown

Qubit Routing for (Almost) Free

Arianne Meijer-van de Griend

Authors on Pith no claims yet

Pith reviewed 2026-05-10 02:53 UTC · model grok-4.3

classification 🪐 quant-ph cs.CC

keywords qubit routingCNOT synthesisphase polynomialsquantum hardwaregate overheaduniversal quantum gatescircuit synthesis

0 comments

The pith

Synthesizing phase polynomials using only allowed CNOTs eliminates qubit routing with constant overhead.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes bounds on the number of CNOT gates needed to synthesize an n-qubit phase polynomial with g terms, showing a lower bound of Omega(gn over max(log g, 1)) and an upper bound of O(gn). On quantum hardware with restricted connectivity, using SWAPs to route qubits for non-allowed CNOTs would multiply the gate count by a factor alpha that can be as large as O(n log squared n). By instead synthesizing the circuit using only the CNOTs that are directly allowed by the hardware, the need for routing disappears entirely and alpha is bounded between 1 and 4. Because phase polynomials together with Hadamard gates form a universal gate set, this technique provides qubit routing for almost free in general quantum computations.

Core claim

The central claim is that when phase polynomials are synthesized exclusively from CNOT gates that are native to the target hardware architecture, no qubit routing via SWAPs is required. In this restricted synthesis, the overhead factor alpha satisfies 1 less than or equal to alpha less than or equal to 4, remaining constant with respect to the number of qubits n. This stands in contrast to unrestricted synthesis followed by routing, which incurs overhead up to O(n log squared n). The result follows from the existence of a synthesis procedure achieving the O(gn) upper bound while respecting the allowed CNOT restrictions, and the fact that phase polynomials augmented by Hadamard gates suffice

What carries the argument

Synthesis of phase polynomials restricted to hardware-allowed CNOT gates, which directly produces implementable circuits without separate routing.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

This approach could simplify quantum circuit compilation for devices with fixed topologies like nearest-neighbor interactions.
Extending the synthesis to include other gates might further reduce overhead in practice.
Empirical tests on real hardware could verify if the factor of 4 is achieved or can be improved.

Load-bearing premise

A synthesis procedure exists that generates only the hardware-allowed CNOTs for any given phase polynomial while maintaining a total gate count of O(gn).

What would settle it

Discovery of a phase polynomial requiring more than four times the minimum number of allowed CNOTs in any direct synthesis, or one that cannot be synthesized within the O(gn) bound using only allowed gates.

read the original 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 \alpha \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 \alpha \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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives new combinatorial bounds on CNOT count for phase-polynomial synthesis and claims you can avoid SWAP routing entirely by synthesizing only hardware-allowed gates with constant overhead, but the restricted-case construction is not shown in detail.

read the letter

The main things to know are the lower bound of O(gn / max(log g, 1)) and upper bound of O(gn) on CNOTs for an n-qubit phase polynomial with g terms, plus the assertion that direct synthesis on the hardware graph keeps total overhead at most a factor of 4 instead of the usual log n or worse from SWAP routing. Phase polynomials plus Hadamards being universal is the hook for calling it routing for almost free.

Referee Report

1 major / 2 minor

Summary. The manuscript proves that synthesizing an n-qubit phase polynomial with g terms requires at least O(gn / max(log g, 1)) and at most O(gn) CNOT gates when arbitrary CNOTs are permitted. For hardware graphs with restricted CNOT connectivity, it asserts that directly synthesizing only allowed CNOTs incurs a constant overhead factor 1 ≤ α ≤ 4 (hence O(1)) with no separate SWAP routing required; combined with Hadamard gates this yields a universal set and therefore qubit routing for almost free.

Significance. If the restricted-synthesis claim holds with the stated constant factor, the result would be significant for quantum compilation: it replaces the typical O(log n) or worse routing overhead with an O(1) factor for an important class of circuits, while the mathematical proofs for the unrestricted bounds constitute a clear technical contribution.

major comments (1)

[Abstract and the section discussing hardware-restricted synthesis] The central claim that restricting synthesis to hardware-allowed CNOTs preserves an O(gn) upper bound with α ≤ 4 is load-bearing for the 'almost free' routing conclusion, yet the manuscript provides neither an explicit modified synthesis procedure nor a proof that the linear dependencies over GF(2) can still be realized without exceeding the constant factor when CNOT targets are constrained by the graph. The unrestricted O(gn) construction appears to rely on free choice of targets; the text does not demonstrate how the restriction is enforced while keeping the total count within 4× the unrestricted bound.

minor comments (2)

[Abstract] The notation for the overhead factor α is introduced without a precise definition of how it is computed from the gate counts before and after restriction; a short equation or example would improve clarity.
[Proofs section] The lower-bound proof is stated to exist but its key combinatorial argument is not reproduced in the provided text; including a brief outline or reference to the relevant lemma would strengthen the presentation.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and constructive feedback on our manuscript. The major comment correctly identifies that the hardware-restricted synthesis requires more explicit detail to support the constant-factor claim. We will revise the manuscript to address this.

read point-by-point responses

Referee: [Abstract and the section discussing hardware-restricted synthesis] The central claim that restricting synthesis to hardware-allowed CNOTs preserves an O(gn) upper bound with α ≤ 4 is load-bearing for the 'almost free' routing conclusion, yet the manuscript provides neither an explicit modified synthesis procedure nor a proof that the linear dependencies over GF(2) can still be realized without exceeding the constant factor when CNOT targets are constrained by the graph. The unrestricted O(gn) construction appears to rely on free choice of targets; the text does not demonstrate how the restriction is enforced while keeping the total count within 4× the unrestricted bound.

Authors: We agree that the current presentation lacks sufficient detail on adapting the synthesis to restricted connectivity. The unrestricted O(gn) upper bound is obtained by realizing a basis of linear dependencies over GF(2) via a sequence of CNOTs. For a connected hardware graph, the same dependencies can be realized by restricting target choices to adjacent qubits and propagating information along paths; because each dependency requires only a bounded number of such local operations (at most four per original CNOT in the worst case, via a fixed-depth gadget on the graph), the total count remains at most 4× the unrestricted bound. We will add an explicit subsection describing this modified procedure, including the gadget construction and the proof that the overhead factor α ≤ 4 holds for any connected graph. The abstract and introduction will be updated to reference this construction. revision: yes

Circularity Check

0 steps flagged

No circularity; bounds derived from explicit combinatorial arguments

full rationale

The paper states explicit lower and upper bounds O(gn / max(log g, 1)) and O(gn) on CNOT counts for phase-polynomial synthesis, then asserts that restricting synthesis to hardware-allowed CNOTs yields routing overhead 1 ≤ α ≤ 4 without separate routing steps. These are presented as direct consequences of the synthesis construction and the universality of phase polynomials plus Hadamards. No equation reduces the claimed overhead factor to a quantity defined by the result itself, no parameters are fitted to data and then renamed as predictions, and no load-bearing self-citations or imported uniqueness theorems appear in the derivation chain. The central claims remain independent of the target result.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard quantum circuit identities and the known universality of phase polynomials plus Hadamards; no free parameters are fitted, no new entities are postulated, and the axioms invoked are ordinary linear algebra over GF(2) and basic graph connectivity assumptions.

axioms (2)

domain assumption Phase polynomials together with Hadamard gates form a universal gate set for quantum computation.
Invoked in the final sentence to conclude that the method covers essentially all circuits.
domain assumption Any n-qubit phase polynomial can be synthesized using only CNOT gates that respect a given hardware connectivity graph.
Central to the claim that routing overhead stays bounded by 4; the abstract asserts existence but does not prove the construction.

pith-pipeline@v0.9.0 · 5470 in / 1524 out tokens · 37753 ms · 2026-05-10T02:53:45.035300+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

30 extracted references · 13 canonical work pages

[1]

Improved simulation of stabilizer circuits

Scott Aaronson and Daniel Gottesman. “Improved simulation of stabilizer circuits”. In:Physical Review A—Atomic, Molecular, and Optical Physics 70.5 (2004), p. 052328

2004
[2]

An 0(n log n) sorting network

M. Ajtai, J. Koml´ os, and E. Szemer´ edi. “An 0(n log n) sorting network”. In:Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing. STOC ’83. New York, NY, USA: Association for Comput- ing Machinery, 1983, pp. 1–9.isbn: 0897910990.doi:10.1145/800061. 808726.url:https://doi.org/10.1145/800061.808726. 12

work page doi:10.1145/800061 1983
[3]

On the controlled- NOT complexity of controlled-NOT–phase circuits

Matthew Amy, Parsiad Azimzadeh, and Michele Mosca. “On the controlled- NOT complexity of controlled-NOT–phase circuits”. In:Quantum Science and Technology4.1 (2019), p. 015002

2019
[4]

Sorting networks and their applications

K. E. Batcher. “Sorting networks and their applications”. In:Proceedings of the April 30–May 2, 1968, Spring Joint Computer Conference. AFIPS ’68 (Spring). Atlantic City, New Jersey: Association for Computing Ma- chinery, 1968, pp. 307–314.isbn: 9781450378970.doi:10.1145/1468075. 1468121.url:https://doi.org/10.1145/1468075.1468121

work page doi:10.1145/1468075 1968
[5]

On the qubit routing problem.arXiv preprint arXiv:1902.08091, 2019

Alexander Cowtan et al. “On the qubit routing problem”. In:arXiv preprint arXiv:1902.08091(2019)

work page arXiv 1902
[6]

Efficient LCU block encodings through Dicke states preparation

Filippo Della Chiara et al. “Efficient LCU block encodings through Dicke states preparation”. In:arXiv preprint arXiv:2507.20887(2025)

work page arXiv 2025
[7]

Linear depth qft over ibm heavy-hex architecture

Xiangyu Gao et al. “Linear depth qft over ibm heavy-hex architecture”. In:arXiv preprint arXiv:2402.09705(2024)

work page arXiv 2024
[8]

Annealing optimisation of mixed ZX phase circuits

Stefano Gogioso and Richie Yeung. “Annealing optimisation of mixed ZX phase circuits”. In:arXiv preprint arXiv:2206.11839(2022)

work page arXiv 2022
[9]

Architecture-aware syn- thesis of phase polynomials for NISQ devices

Arianne Meijer-van de Griend and Ross Duncan. “Architecture-aware syn- thesis of phase polynomials for NISQ devices”. In:arXiv preprint arXiv:2004.06052 (2020)

work page arXiv 2004
[10]

Quantum circuits are just a phase

Chris Heunen et al. “Quantum circuits are just a phase”. In:Proceedings of the ACM on Programming Languages10.POPL (2026), pp. 2586–2613

2026
[11]

An efficient quantum compiler that reduces T count

Luke E Heyfron and Earl T Campbell. “An efficient quantum compiler that reduces T count”. In:Quantum Science and Technology4.1 (2019), p. 015004

2019
[12]

Redefining lexicographical ordering: Optimizing pauli string decompositions for quantum compiling

Qunsheng Huang et al. “Redefining lexicographical ordering: Optimizing pauli string decompositions for quantum compiling”. In:2024 IEEE In- ternational Conference on Quantum Computing and Engineering (QCE). Vol. 1. IEEE. 2024, pp. 885–896

2024
[13]

Algorithmic theory of qubit routing

Takehiro Ito et al. “Algorithmic theory of qubit routing”. In:Algorithms and Data Structures Symposium. Springer. 2023, pp. 533–546

2023
[14]

Scalable spider nests (... or how to graphically grok transversal non-clifford gates)

Aleks Kissinger and John van de Wetering. “Scalable spider nests (... or how to graphically grok transversal non-clifford gates)”. In:arXiv preprint arXiv:2404.07828(2024)

work page arXiv 2024
[15]

The Quantum Circuit Model is not a Practical Representation of Quantum Software

Arianne Meijer-Van De Griend. “The Quantum Circuit Model is not a Practical Representation of Quantum Software”. In:2024 IEEE Inter- national Conference on Software Analysis, Evolution and Reengineering- Companion (SANER-C). IEEE. 2024, pp. 146–148

2024
[16]

A comparison of quantum compilers using a DAG-based or phase polynomial-based intermediate representation

Arianne Meijer-van de Griend. “A comparison of quantum compilers using a DAG-based or phase polynomial-based intermediate representation”. In: Journal of Systems and Software221 (2025), p. 112224

2025
[17]

Advances in quantum compilation in the nisq era

Arianne Meijer-van de Griend. “Advances in quantum compilation in the nisq era”. PhD thesis. Doctoral Dissertation, University of Helsinki, 2024. 13

2024
[18]

Nontrivial multi- product commutation relation for reducing T-count in sequential Pauli- based computation

Yusei Mori, Hideaki Hakoshima, and Keisuke Fujii. “Nontrivial multi- product commutation relation for reducing T-count in sequential Pauli- based computation”. In:arXiv preprint arXiv:2509.20052(2025)

work page arXiv 2025
[19]

NISQ circuit compi- lation is the travelling salesman problem on a torus

Alexandru Paler, Alwin Zulehner, and Robert Wille. “NISQ circuit compi- lation is the travelling salesman problem on a torus”. In:Quantum Science Technology6.2 (2021), p. 025016

2021
[20]

THE PAIRWISE SORTING NETWORK

IAN PARBERRY. “THE PAIRWISE SORTING NETWORK”. In:Par- allel Processing Letters02.02n03 (1992), pp. 205–211.doi:10 . 1142 / S0129626492000337. eprint:https://doi.org/10.1142/S0129626492000337. url:https://doi.org/10.1142/S0129626492000337

work page doi:10.1142/s0129626492000337 1992
[21]

Efficient synthesis of linear reversible circuits

Ketan N Patel, Igor L Markov, and John P Hayes. “Efficient synthesis of linear reversible circuits”. In:arXiv preprint quant-ph/0302002(2003)

work page arXiv 2003
[22]

Optimal ancilla-free Clifford+ T ap- proximation of z-rotations

Neil J Ross and Peter Selinger. “Optimal ancilla-free Clifford+ T ap- proximation of z-rotations.” In:Quantum Inf. Comput.16.11&12 (2016), pp. 901–953

2016
[23]

Lower T-count with faster algorithms

Vivien Vandaele. “Lower T-count with faster algorithms”. In:Quantum9 (2025), p. 1860

2025
[24]

Phase polynomials synthesis algorithms for NISQ architectures and be- yond

Vivien Vandaele, Simon Martiel, and Timoth´ ee Goubault de Brugi` ere. “Phase polynomials synthesis algorithms for NISQ architectures and be- yond”. In:Quantum Science & Technology7.4 (2022), p. 045027

2022
[25]

Optimal num- ber of parametrized rotations and Hadamard gates in parametrized Clif- ford circuits with non-repeated parameters

Vivien Vandaele, Simon Perdrix, and Christophe Vuillot. “Optimal num- ber of parametrized rotations and Hadamard gates in parametrized Clif- ford circuits with non-repeated parameters”. In:arXiv preprint arXiv:2407.07846 (2024)

work page arXiv 2024
[26]

Optimal Hadamard gate count for Clifford+ T synthesis of Pauli rotations sequences

Vivien Vandaele et al. “Optimal Hadamard gate count for Clifford+ T synthesis of Pauli rotations sequences”. In:ACM Transactions on Quan- tum Computing5.1 (2024), pp. 1–29

2024
[27]

Optimal compilation of parametrised quan- tum circuits

John van de Wetering et al. “Optimal compilation of parametrised quan- tum circuits”. In:Quantum9 (2025), p. 1828

2025
[28]

A recur- sively partitioned approach to architecture-aware ZX polynomial synthesis and optimization

David Winderl, Qunsheng Huang, and Christian B Mendl. “A recur- sively partitioned approach to architecture-aware ZX polynomial synthesis and optimization”. In:2023 IEEE International Conference on Quantum Computing and Engineering (QCE). Vol. 1. IEEE. 2023, pp. 837–847

2023
[29]

Architecture-Aware Synthesis of Stabilizer Circuits from Clifford Tableaus,

David Winderl et al. “Architecture-aware synthesis of stabilizer circuits from clifford tableaus”. In:arXiv preprint arXiv:2309.08972(2023)

work page arXiv 2023
[30]

Optimization of CNOT circuits on limited-connectivity architecture

Bujiao Wu et al. “Optimization of CNOT circuits on limited-connectivity architecture”. In:Physical Review Research5.1 (2023), p. 013065. 14

2023