In this chapter, we discuss one of the most famous quantum algorithms currently known. More important than the results of this algorithm is the approach taken to reach the algorithm. The mental model shown in figure 11.1 outlines the chapter.
Figure 11.1 Mental model for this chapter. We gradually develop a Java application that uses quantum computing to factor 15 into 5 and 3.

Before we explain and discuss Shor’s algorithm, let’s look at some real Java code that invokes Shor’s algorithm on a quantum computer simulator. The example in ch11/quantumfactor has everything you need. We discuss the example later; for now, it is important to know that we use Strange to simulate the behavior of a real quantum computer. If you run the example, you will see the following output:
Factored 15 in 3 and 5
That’s it. The main application in the last chapter of this book factors 15 into 3 and 5. While that is something you could easily do with a classical computer, or even in your head, it is a great example of where quantum computers can make a real difference, and why. As we said before, the results of the code in this chapter are not impressive. But there are two important reasons we put so much emphasis on this algorithm: