This chapter explored Shor's algorithm, a quantum algorithm that is used to find the prime factorization of a number. It goes over what prime factorization is, which is the classical implementation of an algorithm to perform prime factorization compared to the quantum implementation as given by Shor's algorithm. Shor's algorithm has a large classical component, with just one portion, a period finding subroutine that can be run on a quantum computer. The chapter first showed an implementation of this subroutine on a classical computer. We then traced through Shor's algorithm with a variety of different factorizations, step by step, to develop an understanding of how Shor's algorithm functions. Finally, for a specific subcase, this chapter provided a full implementation of the quantum period-finding subroutine, along with its integration into a higher-level function that, given N, factors N on a quantum computer. We looked at specific N examples as well as the skills to extend the algorithm to work for more general cases.
In the next chapter, we will go over ways to avoid errors in our quantum algorithms via quantum error correction algorithms.