chapter eleven

11 Shor’s Algorithm

 

This chapter covers:

  • An explanation of Shor’s Algorithm and why it is relevant
  • A classical approach to solve integer factorization
  • The quantum approach to solve integer factorization, implemented in a classical way
  • The same approach, implemented using quantum computing techniques.

In this chapter, we will discuss one of the most famous quantum algorithms that is currently known. More important than the results from this algorithm is the approach that is taken to come to this algorithm. The mental model shown in Figure 11.1, outlines the chapter.

Figure 11.1. Mental model for this chapter. We will gradually develop a Java application that leverages quantum computing to factor 15 in 5 and 3.

ch11 mentalmodel small

11.1. A quick sample

Before we explain Shor’s algorithm and discuss it, let’s have a look at some real Java code that invokes Shor’s algorithm on a quantum computer simulator.

The sample in ch11/quantumfactor has everything you need. We will discuss the sample later, for now it is important to know that the sample uses Strange to simulate the behavior of a real quantum computer. If you run it, you will see the following output:

Factored 15 in 3 and 5

11.2 The marketing hype

11.3 Classic factorization versus quantum factorization

11.4 A multi-disciplinary problem

11.5 Problem description

11.6 The rationale behind Shor’s algorithm

11.7 The quantum-based implementation.

11.7.1 Creating the periodic function

11.7.2 Calculate the periodicity

11.8 Implementation challenges

11.9 Summary