11 Shor’s algorithm

 

This chapter covers

  • Understanding Shor’s algorithm and why it is relevant
  • Solving integer factorization with classical and quantum computing techniques

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.

11.1 A quick example

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:

11.2 The marketing hype

 
 
 
 

11.3 Classic factorization vs. quantum factorization

 
 

11.4 A multidisciplinary problem

 

11.5 Problem description

 

11.6 The rationale behind Shor’s algorithm

 
 
 
 

11.6.1 Periodic functions

 
 
 
 

11.6.2 Solving a different problem

 

11.6.3 Classic period finding

 
 

11.6.4 The post-processing step

 
 

11.7 The quantum-based implementation

 
 
 

11.8 Creating a periodic function using quantum gates

 
 
 

11.8.1 The flow and circuit

 
 
 

11.8.2 The steps

 
 

11.9 Calculating the periodicity

 
 
 

Summary

 
 
 
 
sitemap

Unable to load book!

The book could not be loaded.

(try again in a couple of minutes)

manning.com homepage
test yourself with a liveTest