Revision as of 07:47, 22 September 2020 edit Vecr (talk \| contribs) 216 edits Respond to integer size question. ← Previous edit		Revision as of 00:09, 25 April 2021 edit undo 2601:647:500:406:e844:3188:155b:9e60 (talk) →Time complexity of Shor's algorithm Next edit →
Line 15: :Of course we want to give the most precise estimate possible; but if the postprocessing is O((log n)^3), we might as well summarize it as such. [[User:Dcoetzee\|Dcoetzee]] 21:19, 25 September 2008 (UTC) :To clarify (13 years later...), the O((log n)^2 (log log n) (log log log n)) figure is using the Schonhage-Strassen algorithm to perform multiplication, which is asymptotically optimal but not practical (and also seems to require a superlinear number of qubits). In practice, one expects to run the algorithm in O((log N)^3) time with a qubit cost linear in n. [[Special:Contributions/2601:647:500:406:E844:3188:155B:9E60\|2601:647:500:406:E844:3188:155B:9E60]] ([[User talk:2601:647:500:406:E844:3188:155B:9E60\|talk]]) 00:09, 25 April 2021 (UTC)

Talk:Shor's algorithm: Difference between revisions