Performance scaling of Shor's algorithm with a banded quantum Fourier transform
Yunseong Nam, R. Blümel · Physical Review A · 2012
In excellent agreement with our numerical simulations of Shor's algorithm, equipped with a truncated quantum Fourier transform of bandwidth $b$, we find that its performance scales $\ensuremath{\sim}$${2}^{\ensuremath{-}{\ensuremath{\xi}}_{b}n}$, where $n$ is the number of qubits, ${\ensuremath{\xi}}_{b}=1.1\ifmmode\times\else\texttimes\fi{}{2}^{\ensuremath{-}2b}$, and the bandwidth $b$ is the number of quantum states coupled by the quantum Fourier transform. Nonexponential behavior is observed for small $n$ and explained analytically. The large-$n$ exponential scaling implies that $b=7$ is sufficient to operate a 1000-qubit quantum computer running Shor's algorithm on the $95%$ performance level and implies hardware savings of the order of half a million rotation gates.