8
$\begingroup$

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?

$\endgroup$
23
$\begingroup$

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.1 Again, we won't know how much slower until quantum computers exist.

1 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.

| cite | improve this answer | |
$\endgroup$
  • 22
    $\begingroup$ A question about Shor's algorithm, answered by Peter Shor himself. Neat. $\endgroup$ – adrianN Nov 4 '13 at 9:55
  • 2
    $\begingroup$ There are probably better estimates around by now, actually. $\endgroup$ – Peter Shor Mar 30 '18 at 13:10
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.