Shor factoring cost-accounting branches

Fix a promised input integer $N\ge 4$, set $n=\lceil {\log }_{2}N\rceil$, and let an order-finding phase register have width $m\ge 1$ and size $Q=2^m$. A work wire is an auxiliary circuit wire outside the stated input and output registers; its presence and use are charged as part of the supplied circuit. Classical bit transitions use the convention of Classical bit-operation cost. The cost report for Shor factoring keeps the following branches separate.

• Explicit reversible arithmetic. A supplied reversible circuit for multiplication by a fixed residue modulo $N$ is charged by its actual gate occurrences and work wires. Each use of that circuit is also counted in a separate modular-multiplier-call coordinate. The circuit, its inverse, and any controlled version must be supplied; this definition assigns none of them zero cost. It asserts no finite circuit-description generator or generation-time bound.
• Ideal exact-angle QFT. In this named ideal submodel, each Hadamard, exact controlled-phase rotation, and swap in the supplied $m$-bit QFT circuit counts as one ideal gate. The standard exact cyclic QFT has $m$ Hadamards, $m(m-1)\mathrm{/}2$ controlled-phase rotations, and $\lfloor m\mathrm{/}2\rfloor$ swaps, hence $O(m^2)$ ideal gates. This submodel permits exact real angles as unit-cost gates. It supplies no finite gate alphabet, finite binary description, approximation, compiler, or uniform-family claim.
• Bare controlled-unitary access. If only a controlled call to $U_x:\mathrm{\mid }z⟩\mapsto \mathrm{\mid }xz<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>N⟩$ is supplied, implementing the controlled power $U_x^{2^j}$ by repetition costs $2^j$ oracle calls. Across $j=0,\dots ,m-1$ this is ${\sum }_j{2}^j=Q-1$ calls per phase-estimation sample. These oracle-query counts are separate from gate counts.
• Classical bit work. Integer inputs are binary, elementary arithmetic is charged in bit operations, and schoolbook multiplication of two $b$-bit integers costs $O(b^2)$. A rejection sampler's random-bit cost is reported in expectation separately from deterministic bit operations.

The four coordinates used by the factoring cost theorem are ideal or explicit quantum gates, modular-multiplier calls, bare controlled-unitary oracle queries, and classical bit operations. An inapplicable branch is not reported as a zero-cost implementation.

This is a cost convention for the stated algorithmic comparison. In particular, the ideal exact-angle QFT count is not a finite-alphabet or uniform-circuit theorem.