From Circuits to Algorithms

I am among those who think that science has great beauty.

Marie Curie

In the last chapter, we became comfortable putting together gates to create circuits for simple algorithms. We’re now ready to look at more advanced quantum algorithms and consider how and when to use them.

Our target in this chapter is Peter Shor’s 1995 algorithm for factoring large integers, which is almost exponentially faster than classical methods. To get there, we need more tools, such as the Quantum Fourier Transform, phase kickback, eigenvalue and phase estimation, and function order and period finding. These are essential techniques in their own right but are necessary in combination for quantum factoring.

We also return to the idea of complexity that we first saw for classical algorithms in section 2.8. This allows us to understand what “almost exponentially faster” means.

This chapter contains more mathematics and equations...

Topics covered in this chapter

1. 10.1. Quantum Fourier Transform
   1. 10.1.1. Roots of unity
   2. 10.1.2. The formula
   3. 10.1.3. The circuit
   4. 10.1.4. The inverse Quantum Fourier Transform
2. 10.2. Factoring
   1. 10.2.1. The factoring problem
   2. 10.2.2. Big integers
   3. 10.2.3. Classical factoring: basic methods
   4. 10.2.4. Classical factoring: advanced methods
3. 10.3. How hard can that be, again?
   1. 10.3.1. Time is not always on your side
   2. 10.3.2. Complexity classes
4. 10.4. Phase kickback
5. 10.5. Eigenvalue and phase estimation
6. 10.6. Order and period finding
   1. 10.6.1. Modular exponentiation
   2. 10.6.2. The circuit
   3. 10.6.3. The continued fraction part
   ...

10.1 Quantum Fourier Transform

The Quantum Fourier Transform (QFT) is widely used in quantum computing. We need it in this chapter to estimate eigenvalues via the function order and period finding algorithm in section 10.5. We then use that in Shor’s factoring algorithm in section 10.7. If that weren’t enough, the Hadamard H is the 1-qubit QFT, and we’ve seen many examples of its use. algorithm$Quantum Fourier Transform Quantum Fourier Transform

Other applications of the QFT include quantum Monte Carlo, 77 and the Harrow-Hassidim-Loyd (HHL) algorithm for solving systems of linear equations under restrictive conditions. 105 63 algorithm$Monte Carlo Monte Carlo algorithm algorithm$Harrow-Hassidim-Loyd Harrow-Hassidim-Loyd algorithm algorithm$HHL HHL algorithm

Most treatments of the QFT start by comparing it to the classical Discrete Fourier Transform and then the Fast Fourier Transform. If you don’t know either of these, don’t worry...

10.2 Factoring

It is hard to do a web search and find “practical” applications of factoring integers. Many results say things such as “factoring integers is a tool for factoring polynomials” and “factoring integers is useful for solving some differential equations.” These examples are fine, but it seems like math to do more math. factoring integer$factoring

One area where factoring comes into play is cryptography. Some cryptographic protocols assume you cannot easily factor some large numbers because those factors are related to encryption and decryption methods. Shor, Peter algorithm$Shor’s factoring Shor’s factoring algorithm

In this section, we examine several classical methods for factoring. Although they involve some sophisticated mathematics, they are currently insufficient for breaking arbitrary large integers into their prime components. This discussion sets us up for the final section of this chapter...

10.3 How hard can that be, again?

In section 2.8, we first saw and used the O() notation for sorting and searching. Bubble sort runs in O(n²) time, and merge sort is O(n log(n)). A brute force search is O(n), but adding sorting and random access allows a binary search to be O(log(n)).

We now look at complexity again to understand why Shor’s factoring algorithm is a big improvement on known classical methods.

10.3.1 Time is not always on your side

All algorithms are of polynomial time because we can bound them, in this case, by O(n²). More precisely, there is a hierarchy of time complexities. For the examples above, polynomial$time algorithm$polynomial time complexity$polynomial time complexity

Polynomial time is higher than all of these, but we can say each runs in at least polynomial time. exponential$growth growth$exponential

We are concerned with this because there is a special distinction between polynomial...

10.4 Phase kickback

In section 9.8.2, we saw an example of phase kickback while working with oracles. In this section, we look at the concept again in the context of controlled z-rotation gates. We need this within Shor’s factoring algorithm to estimate eigenvalues. phase$kickback

Consider the circuit in Figure 10.8.

Figure 10.8: A circuit with a Hadamard and controlled z-rotation gate

As we saw in section 7.6.6, |1⟩ is an eigenvector of R_φ^z with eigenvalue e ^φi:

The initial quantum state in Figure 10.8 is |00⟩ = |0⟩⊗|0⟩. We apply H⊗X, yielding

We apply the CR_φ^z:

We began with q₀ as the control qubit. The phase from the R_φ^z gate conditionally applied to q₁ ends up causing the phase e ^φi to appear in the state of q₀. The state of q₁ was not changed from |1⟩. This is the phase...

10.5 Eigenvalue and phase estimation

The next tool we need for Shor’s factoring algorithm is a way to estimate the eigenvalues of a special unitary operation we construct.

Let U be an n-by-n square matrix with complex entries. From section 5.10, the solutions λ of the equation algorithm$phase estimation

are the eigenvalues {λ₁, …, λ_N} of U. Some of the λ_j may be equal. If a particular eigenvalue λ_j shows up k times among the N values, we say λ_j has multiplicity k. multiplicity

Each eigenvalue λ_j corresponds to an eigenvector v_j so that

We can take each v_j to be a unit vector. When U is unitary, each λ_j is a complex unit.

We have so far represented an eigenvalue λ of a unitary matrix as e^φi with 0 ≤ φ < 2π. We now, instead, think of the eigenvalue as e^2πφi with 0 ≤ φ < 1.

This change allows...

10.6 Order and period finding

The next tool we need for Shor’s algorithm is an algorithm to find out when certain types of functions start repeating themselves. algorithm$order-finding

Consider the function k ↦ a^k on whole numbers k for a fixed a in N greater than 1. For example, if a = 3, the first 12 values are

or in Python:

[3**n for n in range(12)]
    

[1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147]
    

As we look at larger exponents k, the values of 3^k will get larger and larger.

If we instead use modular arithmetic, as we saw in section 3.7, 3^k cannot get arbitrarily large. For example, modulo M = 13, the values we get for the function k ↦ a^k mod 13 are number$modular integer integer$modular modulo

[3**n % 13 for n in range(12)]

[1, 3, 9, 1, 3, 9, 1, 3, 9, 1, 3, 9]

Here, “%” is the Python “remainder operator,” and it implements...

10.7 Shor’s factoring algorithm

We now have the tools we need for Shor’s factoring algorithm to factor integers in polynomial time on a sufficiently large quantum computer. The is a near-exponential improvement over the best known classical methods we described in section 10.2. algorithm$Shor’s factoring Shor’s factoring algorithm factoring$Shor’s algorithm

The complete algorithm has both classical and quantum components. Work is done on both kinds of machines to get to the answer. The quantum portion drops us down to polynomial complexity in the number of gates using phase estimation, order finding, modular exponentiation, and the QFT.

Let odd M in Z be greater than 3 for which you have already tried the basic tricks from section 10.2.3 to check that it is not a multiple of 3, 5, 7, and so on. So that you don’t waste your time, you should also try trial division using a small list of primes, although this is not necessary...

10.8 Summary

In this chapter, we did some hard math to understand how to factor integers much faster than we can classically. Along the way, we delved deeply into several nontrivial quantum algorithms used in other quantum applications. These algorithms include the Quantum Fourier Transform, phase estimation, and order finding. These form a sound basis for understanding other quantum algorithms and their circuits.

Next, we turn our attention to the connections between the slightly abstract concepts we have seen and the physical quantum computers we can build today.

To learn more

Although we have covered several of the most common quantum algorithms, there are many other quantum algorithms. Techniques such as order finding are part of advanced algorithms in addition to Shor’s factorization. 4 135 151 171 116