In what follows, I am mostly interested inexact arbitrary-precision arithmetic.Quantum arithmetic is an active research topic. Of course any classical algorithm for arithmetic can be expressed as a reversible circuit and therefore run on a quantum computer with the same asymptotic complexity (in terms of number of elementary operations). A subset of that work focuses on implementations of arithmetic operations based on the QFT. In the surveys I have seen (seehere andhere, for example), the proposed algorithm runtimes scale as$O(n^2)$ elementary operations (and sometimes this even ignores classical work needed), even for operations that classically cost$O(n)$.
Seeing as the best implementations of the QFT (either exact or approximate with sufficient precision) cost$O(M(n)\log n)$, where$M(n)$ is the cost of multiplying two$n$-bit integers classically, is there any hope of QFT-based arithmetic ever beating classical arithmeticin terms of number of operations?
Are there even any works where a QFT-based approach for arithmetic at leastmatches classical performancein terms of number of operations?
It seems like for QFT-based arithmetic to become competitive, a$\log n$ factor in the$O(M(n) \log n)$ scaling of the QFT would have to be shaved off somehow. Are there any hopes of that happening? Or is there a no-go result that suggests this might be optimal?
1 Answer1
Are there even any works where a QFT-based approach for arithmetic at least matches classical performance in terms of number of operations?
Not that I'm aware of. Actually, when I'm asked to make a QFT circuit, the way I do the phasing operations inside of it is typicallyvia phase kickback from Toffoli-based additions into a phase gradient state. So if you looked inside the my QFTs you'd find classical adders, rather than finding QFTs inside the adders.
QFT based adders tend to come up when squeezing on things other than gate count. For example, trying to minimize depth or minimize ancilla count orallowing approximations. For example,Beauregard's implementation of Shor's algorithm used QFT based adders to reduce workspace. But this increased its gate count bythree orders of magnitude compared to other implementations (table 1 of this paper), and it was later figured out how to get the same workspace without QFT based adders:
That said, I think thecurrent best quantum Karatsuba multiplier uses QFT adders.
Explore related questions
See similar questions with these tags.