# on the complexity of Shor's factoring aglorithm with three quantum registers

#1
Sat, 08/05/2010 - 00:46

#### on the complexity of Shor's factoring aglorithm with three quantum registers

It is well-known that the Shor’s factoring algorithm uses two quantum registers. Recently, by investigating the algorithm with three registers, the authors (http://doi.ieeecomputersociety.org/10.1109/ISISE.2009.86) argued the claim that the Shor’s algorithm runs in polynomial time is false, because Shor had wrongly treated a joint probability as a conditional probability. The argument is very short, and seems sound to me. If so, that’s big news.

Who can refute the argument of http://doi.ieeecomputersociety.org/10.1109/ISISE.2009.86

## It would be nice if it weren

It would be nice if it weren't pay-walled.

Anyway this is silly. We can simulate quantum computers. While obviously our simulations take exponential time, it isn't to hard to keep track of how much time it would take on a real quantum machine. Spoiler: it comes out polynomial.