11 Shor’s Algorithm

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.

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:

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