Skip to 0 minutes and 4 seconds The goal for this activity is to understand Shor’s algorithm for factoring large numbersin polynomial time. Before we get into the details of Shor’s algorithm itself, let’s flush out our understanding of the problem and its relationship to other problems a little bit more. Earlier in this course, we discussed the basic idea of factoring, its importance and difficulty and why it’s hard for a human or classical computer to factor large numbers as they get large. Recall there are simple classical algorithm for factoring takes order of the square root of 10 to n time to factor an n digit number. The fastest known classical algorithm is called the general number field sieve and in fact it is significantly faster than that.
Skip to 0 minutes and 43 seconds Its run time is much more complicated expression. We don’t need to go into the details of that, but I bring it up for a particular reason that we have been putting off talking about, the generality of solving problems. It’s important to understand what factoring does and does not do for us. One of the most important techniques in computer science and mathematics is to take a problem you don’t know how to solve and rewrite it so that it is like another problem that you do know how to solve. In particular, we worry about how the difficulty grows as the problems get bigger. We saw the beginnings of these ideas when we talked about the computational complexity better for the quantum computers.
Skip to 1 minute and 22 seconds In computer science, the two most important classes of problems are P and NP. There are hundreds more and they all help us understand what it means to computer as well as to help us find efficient solutions to specific problems, but we aren’t going to go into that level of theory in this course. The P class stands for polynomial, that is, we can solve the problem in order of N to the K time where N represents the size of the problem and K is some constant number. For a lot of problems, K is 2 or 3 or 4 but it could be anything as long as it’s a number that doesn’t depend on N itself. NP is non-deterministic polynomial.
Skip to 2 minutes and 3 seconds We don’t need to go into the details of the definition, but the best known solutions to problems in NP and outside of P are exponential. We don’t have any proof that this is the best we can do, but many people think we can do better and interestingly, a whole group of them known as NP complete problems can map to each other so that if you know how to solve one, you know how to solve them all. Of course, any exponential grows very fast, so problems that take exponential time are considered to be hard to solve. So what about factoring, where does it fall? Well, it turns out, in neither of these classes so far as we know for classical computers.
Skip to 2 minutes and 44 seconds The complicated expression we saw a minute ago, it’s harder than polynomial, but not as hard as exponential. It’s in a group we call super polynomial or sub-exponential and importantly we don’t know how to map it during the other important problem, so being able to solve it efficiently doesn’t directly solve a huge class of problems, so it’s rather specific task. So, why are we so excited about Shor’s algorithm then? Three big reasons; first, even though the problem is rather specific, it’s important. As we discussed earlier, it impacts cryptography and therefore security on the internet. Second, the potential gain and performance is exciting, going from super polynomial to polynomial time is a very big deal.
Skip to 3 minutes and 29 seconds Shor’s announcement of his algorithm really put the field of quantum computing on the map bringing in attention and research funding because it suggests that maybe quantum computers will bring us huge performance gains. Third, the specific techniques used in Shor’s algorithm are incredibly exciting. They point to new ways of solving problems. In particular, a technique known as the quantum Fourier transform or QFT appears to be a very fundamental tool. In this course, this is the only algorithm we are going to study in detail. Grover’s algorithm is more general, but harder to discuss in detail because it’s more of a framework than a complete algorithm. Shor, in contrast, is complete and self-contained.
Skip to 4 minutes and 10 seconds Shor also appears to offer a much larger speed up than Grover from super polynomial to polynomial time, so let’s take a look at the algorithm.
Basic Goal: Factoring
In computer science, the two most important classes of problems are P and NP. The P class stands for polynomial, that is, we can solve the problem in order of \(N\) to the \(k\) time (\(O(N^k)\)) where \(N\) represents the size of the problem and \(k\) is some constant number. NP is non-deterministic polynomial.
The best known solutions to problems in NP and believed to be outside of P are exponential. Of course, any exponential grows very fast, so problems that take exponential time are considered to be hard to solve. So what about factoring, where does it fall?
Factoring is, so far as we know, harder than polynomial, but not as hard as exponential. Because Shor’s algorithm shows that a quantum computer can factor in polynomial time, it is exciting for three big reasons:
- the problem is important;
- the performance gains are exciting; and
- techniques are exciting and valuable.
© Keio University