Shor's Algorithm speed

Question

I'm a fledgling computer science scholar, and I'm being asked to write a paper which involves integer factorization. As a result, I'm having to look into Shor's algorithm on quantum computers.

For the other algorithms, I was able to find specific equations to calculate the number of instructions of the algorithm for a given input size (from which I could calculate the time required to calculate on a machine with a given speed). However, for Shor's algorithm, the most I can find is its complexity: O( (log N)^3 ).

Is there either some way I can find its speed/actual complexity from its Big-O Notation? If not, is there someone who can tell me what I want, or how to find it?

Answer 1

The best estimate I know of can be found in Efficient networks for quantum factoring, by David Beckman, Amalavoyal N. Chari, Srikrishna Devabhaktuni, and John Preskill, which gives $72 (\log N)^3$.

Having said that, a straight comparison of number of steps on a quantum computer versus number of steps on a classical computer is problematic for various reasons. First, as D.W.'s answer says, the number of steps depends on the exact architecture of the quantum computer, which we won't have until one is built. Second, the time required for a single step on a quantum computer is likely to be quite a bit slower than a single step on a classical computer.¹ Again, we won't know how much slower until quantum computers exist.

¹ If it was faster, you could use the same architecture to build a classical computer that would be at least as fast, and probably faster because for a classical computer, you don't need to worry about maintaining quantum coherence.

Answer 2

What you are asking for does not exist, for good reasons.

Today there is no existing computer that can execute Shor's algorithm. To run Shor's algorithm, you need a quantum computer, which doesn't exist yet. Therefore, you shouldn't expect precise estimates of its speed or running time, as that will depend upon the details of the computer that the algorithm is run on -- and we can't possibly know those details until we've successfully built one.