Manuel Kauers Hagenberg, May 7, 2003 RISC-Linz

Factoring Integers in Polynomial Time

An Introduction to Quantum Computing

Contents

1 Introduction 1 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2 Quantum Basics 2 2.1 Physical Background . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.2 Quantum Information . . . . . . . . . . . . . . . . . . . . . . . . 3 2.3 Quantum Gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

3 Quantum Algorithms 5 3.1 Deutsch-Jozsa Algorithm . . . . . . . . . . . . . . . . . . . . . . 5 3.2 Quantum Fourier Transform . . . . . . . . . . . . . . . . . . . . . 7 3.3 Factoring Integers . . . . . . . . . . . . . . . . . . . . . . . . . . 9

4 Conclusion 11

1 Introduction

1.1 Motivation

Many algorithms in Computer Algebra suffer from a very high complexity. A famous challange problem of high complexity is the factorisation of integers. The best known classical algorithm for integer factorisation runs in time exp(O(1)n^{1/3} log^{2/3} n) where n is the length of the integer to be factored, i.e., the number of bits needed to encode it in binary. However, by deviating from the classical concept of computation, and by allowing quantum steps in the algorithm, algorithms can be developed which are a great deal faster than their classical counter parts. Such an algorithm for integer factorisation has been discovered by Peter Shor and the main purpose of this paper is to outline the basic ideas of his algorithm together with a description of the necessary amount of underlying quantum computing concepts. It is hardly possible to give an introduction to quantum computing within a 90 minutes talk or in a paper of corresponding length — a one semester course would be much more appropriate. As a result, we will have to leave out a lot of details. More rigorous introductions into quantum computing, including also an explanation of Shor’s algorithm, can be found in [3, 4, 5, 6]. This paper was based on these sources.

1.2 Notation

Quantum computing has to do with quantum mechanics which in turn has to do with physics. Physicists are known to like strange notation, and the physicists’ notation has become standard in the field of quantum computing. We will stick to this notation for the sake of consistency to the literature. It will turn out later that the vector space ℂ^{2} plays an important role in quantum computing. Once and for all, we single out an orthonormal basis B = {b_{0}, b_{1}} of ℂ^{2}. Using ket notation, we will write |0⟩ := b_{0} and |1⟩ := b_{1}. More general, we will write |x⟩ = a|0⟩ + b|1⟩ for any vector in ℂ^{2}, and ⟨x| for the transpose of |x⟩. ⟨x|y⟩ := ⟨x| · |y⟩ consequently denotes the standard skalar product of |x⟩ with |y⟩. The ket notation is used also in the spaces V = ℂ^{2} ⊗ ⋯ ⊗ ℂ^{2} where A ⊗ B denotes the tensor product of A with B. If {a_{1}, …, a_{n}} is a basis of A and {b_{1}, …, b_{m}} is a basis of B, then A ⊗ B can be viewed as the vector space to the basis {a_{i} ⊗ b_{j} : i = 1, …, n; j = 1, …, m} where a_{i} ⊗ b_{j} is simply a formal product. In ket notation, we will often use notations like

|00 … 0⟩ := |0⟩|0⟩ … |0⟩ := |0⟩ ⊗ |0⟩ ⊗ ⋯ ⊗ |0⟩.

for the basis vectors in ℂ^{2} ⊗ ⋯ ⊗ ℂ^{2}.

2 Quantum Basics

2.1 Physical Background

Wolfang Pauli said that it is an inherent property of quantum mechanics that it cannot be understood; it can only be accepted. Following this “paradigm” we will not try to understand physical underpinnings of what is going on in the still hypothetical device of a quantum computer, especially we will not say anything about how a quantum computer can be implemented in real world. Rather, we want to remind the reader of some spectacular effects in quantum physics which (s)he might have heard about in high school, mainly to develop some kind of intuition. What is the behaviour of an electron in the hull of an atom? First physical models believed that electrons are flying around the nucleus on well defined orbits just as planets deterministically revolve around their star. Quantum physics tells us that this is an oversimplified model. Rather, the electron is smoothly distributed around the nucleus. Like with photons, it appears in both wave and particle form. When we leave it in peace, it will at the same time be somehow everywhere and somehow nowhere in the hull, but when we make a measurement, it “flips” to the particle state and can be located.

If the life of a cat in a black box is made dependent of some effects from quantum mechanics, we will not be able to predict for a certain time if the cat is dead or alive. (Schrödinger’s cat.) We only know when we open the box to check, i.e., again when we do a measurement. Before the measurement, the cat is actually both dead and alive. To see that the state of the cat is indeed a superposition of dead and alive rather than “either dead or alive, we just don’t know”, consider the Mach-Zehnder interferometer depicted in the following diagram.

Two beam splitters B_{1} and B_{2} leave half of the light through without disturbing, and half of the light is perfectly reflected. Now, if a photon is emitted from source A it may be found with equal probability p = \frac{1}{2} at one of the positions M_{1} and M_{2} if a measurement is done there. However, if we measure only after the second beam splitter B_{2}, we will find the electron with probability p = 1 in M_{3} and with probability p = 0 in M_{4}. It is therefore better to imagine that the photon takes both ways the same time. It does not decide at B_{1} which way to take, but rather it decides at M_{1} and M_{2} which way it has taken.

2.2 Quantum Information

The smallest amount of classical data is the bit. Such a classical bit B always has exactly one value, either B = 0 or B = 1. In a string (B_{1}, …, B_{n}) of n bits each bit takes either the value 0 or the value 1. The value of the entire string can be viewed as an element of

\{0, 1\}^{n} = \underbrace{\{0, 1\} × ⋯ × \{0, 1\}}_{n times},

hence a string of n bits can altogether take 2^{n} different values. The main difference between classical information and quantum information is the possibility of superposition. Like the electron and the cat and the photon, a quantum bit or qubit can take two states at the same time, i.e., it can be both 0 and 1. Mathematically, we model a qubit as an element on the unit sphere in ℂ^{2}, or equivalently as a vector in the projective space of ℂ^{2} factoring out the length of the vectors. The classical bit values 0 and 1 will correspond to the designated basis vectors |0⟩ and |1⟩. The general value of a qubit |q⟩ is of the form

|q⟩ = α|0⟩ + β|1⟩

where α^{2} + β^{2} = 1. By slight abuse of notation, we may state the state of Schrödinger’s cat as

|cat⟩ = \frac{1}{\sqrt{2}}(|dead⟩ + |alive⟩)

for supporting the intuition. Deep physical reasons suggest that an adequate model for systems of n qubits is the tensor product ℂ^{2} ⊗ ⋯ ⊗ ℂ^{2} of n copies of ℂ^{2}. Its basis

{|00 … 000⟩, |00 … 001⟩, |00 … 010⟩, |00 … 011⟩, … |11 … 110⟩, |11 … 111⟩}

will be refered to as the computational basis. When we do a computation, we are usually also interested in its result. This means that we have to measure the physical state of a system. In the classical setting, there is nothing special about this step, but in the quantum world there is. We have seen in the example of the Mach-Zehnder interferometer that the measurement of a quantum system necessarily influences the system. In our mathematical model, we will regard a measurement as a projection of a vector to the computational basis. A measurement of a state α|0⟩ + β|1⟩ will return the value |0⟩ with probability α^{2} and the value |1⟩ with probability β^{2}. (Again, compare this to the example of Schrödinger’s cat.) Note that in a system of more than one qubit, the individual bits might be entangled. This means that the measurement of one of the bits also determines the value of the other bits. For instance, when measuring the first qubit of the state |q⟩ = α|00⟩ + β|11⟩, the measurement of the second qubit will yield the same value with probability 1. This is clear in the mathematical model since

α|00⟩ + β|11⟩ = α|00⟩ + β|11⟩ + 0|01⟩ + 0|10⟩

and hence the states |01⟩ and |10⟩ are observed only with probability 0, however, the physical intuition behind may suggest something else at first glance.

2.3 Quantum Gates

One theoretical model for classical computation is the circuit model. A circuit consists of wires and gates. An (n, m)-gate is an elementary boolean function that maps a tuple of n input values to a tuple of m output values. Typical gates are the (2, 1)-gate AND, or the (1, 1)-gate NOT. A circuit with n input wires and m output wires encodes a boolean function f: {0, 1}^{n} → {0, 1}^{m}. For instance, the following circuit encodes addition in ℤ_{2}.

Classically, to every boolean function f: {0, 1}^{n} → {0, 1}^{m} there exists a circuit implementing it which contains only AND, OR, and NOT gates. We say that {AND, OR, NOT} build a universal set of operators. The complexity of a circuit is the number of gates it contains. The complexity of a boolean function f: {0, 1}^{n} → {0, 1}^{m} is the complexity of the smallest circuit implementing f. Functions f: ℕ → ℕ cannot be described by circuits because the input size for a circuit is fixed. Instead, a family of circuits is needed which contains for each n ∈ ℕ exactly one circuit with n input wires. A function f: ℕ → ℕ is computable if and only if there exists a Turing machine that computes to a given n ∈ ℕ in time polynomial in n a circuit with n input wires that outputs f(i) for every i < 2^{n}.

Quantum computers can be modeled by quantum circuits. A quantum circuit is a circuit whose wires carry qubits instead of bits and whose gates preform quantum operations. Quantum gates may act on either one or two wires and they perform unitary operations on their input. Note that qubits live in ℂ^{2}, so a one-qubit gate is described by a 2 × 2-matrix and two-qubits are described by 4 × 4-matrices. An example for a one-qubit gate is the Hadamard-Transform defined by the matrix

H = \frac{1}{\sqrt{2}} (\begin{matrix}1 & 1 \\ 1 & −1 \end{matrix})

wrt. the computational basis {|0⟩, |1⟩}. An example for a two-qubit gate is the controlled not gate defined by the matrix

cNOT = (\begin{matrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{matrix})

wrt. the computational basis {|00⟩, |01⟩, |10⟩, |11⟩}. Speaking in terms of classical circuits, the cNOT gate flips the second bit if and only if the first bit is 1. The first bit remains unchanged. The cNOT gate together with all one-qubit gate form a universal set of gates, i.e., all functions f: (ℂ^{2})^{n} → (ℂ^{2})^{m} can be implemented in a quantum circuit involving only one-qubit gates and the cNOT gate. To compute functions with varying input length, a family of quantum circuits is employed — as in the classical case. As there, we require the circuits for input size n to be computed in time polynomial in n by a (classical) Turing machine A. In addition, we have to ensure that no uncomputable (or hard-to-compute) functions are hidden in the one-qubit gates used by machine A. Thus, we additionally require another Turing machine which computes the kth digit of the matrix elements of all quantum gates occuring in the output of A in time polynomial in k. Functions are said to be of bounded error probabilistic polynomial quantum complexity if they can be implemented by a family of quantum circuits whose size is polynomial in the length of the input and whose output after measurement is correct with probability greater than 1/2. By BQP we denote the class of these functions.

3 Quantum Algorithms

3.1 Deutsch-Jozsa Algorithm

Before we turn tho the description of the factoring algorithm, we present another small algorithm, mainly in order to get accustumed to the notions introduced in the previous sections, and to see the special features of quantum algorithms first at an easier example. Consider a boolean function f: {0, 1} → {0, 1}, and assume that we are given a quantum circuit that computes f. We are about to decide if f is balanced, i.e. if f(0) ≠ f(1), using as few computations of f(x) as possible. In a classical computer, there is no chance: we have to compute f(0) and f(1) and to compare the results. If we want to solve the problem faster by a quantum computer, we have to answer the query with only one computation of f(x). Somewhat counterintuitively, this is indeed possible. Given f: {0, 1} → {0, 1}, consider the operator U_{f} defined by U_{f}|xy⟩ = |x, y ⊕ f(x)⟩ for x, y ∈ {0, 1} and linearly extended to ℂ^{2} ⊗ ℂ^{2}. U_{f} is a unitary operator and hence an admissible quantum gate. Consider the following quantum circuit

which computes

(H ⊗ I) · U_{f} · (H ⊗ H) · |01⟩.

The first two Hadamard gates produce superpositions of |0⟩ and |1⟩,

(H ⊗ H)|01⟩ = (|0⟩ + |1⟩) ⊗ (|0⟩ − |1⟩) = (|0⟩ + |1⟩)(|0⟩ − |1⟩)

where we omit the constant factors. Application of U_{f} to this state leads to

|0⟩((|0⟩ − |1⟩) ⊕ |f(0)⟩) + |1⟩((|0⟩ − |1⟩) ⊕ |f(1)⟩)  (1)

By considering the special cases f(x) = 0 and f(x) = 1,

(|0⟩ − |1⟩) ⊕ |0⟩ = |0⟩ − |1⟩,
(|0⟩ − |1⟩) ⊕ |1⟩ = |1⟩ − |0⟩ = (−1)(|0⟩ − |1⟩),

we find that we can write

(|0⟩ − |1⟩) ⊕ |f(x)⟩ = (−1)^{f(x)}(|0⟩ − |1⟩).

This allows to write (1) in the form

((−1)^{f(0)}|0⟩ + (−1)^{f(1)}|1⟩)(|0⟩ − |1⟩).

Finally, another Hadamard transform is applied to the first register giving, up to a constant,

H · ((−1)^{f(0)}|0⟩ + (−1)^{f(1)}|1⟩)
= (−1)^{f(0)}(|0⟩ + |1⟩) + (−1)^{f(1)}(|0⟩ − |1⟩)
= ((−1)^{f(0)} + (−1)^{f(1)})|0⟩ + ((−1)^{f(0)} − (−1)^{f(1)})|1⟩.

What happens if we measure this state? If f(0) ≠ f(1) then the coefficient of |0⟩ vanishes and we obtain 1 with certainty. Likewise, if f(0) = f(1) then the coefficient of |1⟩ vanishes and we obtain 0 with certainty. The measurement result indicates if f is balanced, and only one computation of f was sufficient to decide this. The algorithm outlined above is called the Deutsch-Jozsa algorithm. It can be extended to functions f: {0, 1}^{n} → {0, 1} which are called balanced if exactly have of the values are 0 and half of the values are 1. Even here, where a classical computer would need exponential evaluations of f for a decision, only one evaluation suffices in the quantum setting.

3.2 Quantum Fourier Transform

As an important subroutine for the factoring algorithm, we will need to compute a quantum version of the Discrete Fourier Transform that will be introduced in this section. Let q = 2^{l} be a power of two, and fix ω = ω_{q} = exp(2πi/q) as a qth root of unity for defining the Quantum Fourier Transform QFT = QFT_{q}: (ℂ^{2})^{l} → (ℂ^{2})^{l} by

QFT |a⟩ := \frac{1}{\sqrt{q}} ∑_{b=0}^{q−1} ω^{ab}|b⟩ (0 ≤ a < q).

In this definition, as introduced earlier, we use the convention that |n⟩ denotes the tensor

|n⟩ = |b_{l−1}⟩ ⊗ |b_{l−2}⟩ ⊗ ⋯ ⊗ |b_{0}⟩

where b_{l−1}b_{l−2} … b_{0} is the binary representation of n. Comparing this definition of QFT to the usual DFT of size q, defined in familiar notation by

DFT e_{i} = \frac{1}{\sqrt{q}} ∑_{j=0}^{q−1} ω^{ij}e_{j} (i = 0, …, q − 1)

where e_{i} denotes the ith basis vector of an ONB of ℂ^{q}, we see that the two definitions formally coince (up to notational details). The algorithm of Cooley-Tucky allows to perform the DFT on a classical computer in time O(q log q) using a divide and conquer approach. It is based on the decomposition

DFT_{mn} = (DFT_{m} ⊗I_{n}) · T · (I_{m} ⊗ DFT_{n}) · P

with a permutation matrix P and a “Twiddle matrix” T. We don’t care about P because permutations are for free in the circuit model of computation (just reorder the wires). The twiddle matrix T is defined by

T = diag(Δ^{0}, …, Δ^{m−1})

with

Δ = diag(ω^{0}, ω^{1}, …, ω^{n−1}).

The decomposition of q = 2 · (q/2) leads to the well-known classical divide and conquer algorithm. For the quantum algorithm, we will use the decomposition q = (q/2) · 2. First, we note that QFT_{2} = H, so the quantum fourier transform of one single qubit is possible at the cost of one single quantum gate. For the circuits of higher dimension, let the unitary operator

T_{α} := (\begin{matrix}1 \\ & 1 \\ & & 1 \\ & & & α \end{matrix}) (α ≠ 0)

be denoted by the gate symbol

.

The gates T_{α} will be used to implement the twiddle matrix in the decomposition. Consider the case q = 4. Then

QFT_{4} = (QFT_{2} ⊗I_{2}) · T · (I_{2} ⊗ QFT_{2})
with T = diag(1, 1, 1, i),

and this representation can be directly translated into the following circuit.

Larger QFT circuits are build in the same fashion. The circuit for the next size, q = 8 = 2^{3}, has the form

corresponding to the decomposition

QFT_{8} = (QFT_{4} ⊗I_{2}) · T · (I_{4} ⊗ QFT_{4})
with T = diag(1, 1, 1, i, 1, −1, 1, −i).

What might not be obvious at first glance is the correctness of the twiddle matrix’ implementation, but indeed, compare the matrix rows to the corresponding basis vectors (tensors):

\begin{matrix}|000⟩ : & 1 \\ |001⟩ : & 1 \\ |010⟩ : & 1 \\ |011⟩ : & i \\ |100⟩ : & 1 \\ |101⟩ : & −1 \\ |110⟩ : & 1 \\ |111⟩ : & −i \end{matrix}

Indeed, T_{i} applies whenever the second and the third bit are 1, and T_{−1} applies whenever the the first and the third bit are 1. Of course, this can be shown to work in general, giving us the circuit family

for the QFT_{n} (q = n^{l}). Note that this circuits are of size l(l −1)/2 = O(l^{2}) only whereas the complexity of the corresponding classical algorithm is O(n log n), i.e., exponentially higher.

3.3 Factoring Integers

We are now ready to present Shor’s integer factorisation algorithm. Let N be an L-digit number. Suppose further that a > 1 is coprime to N. The residues a^{i} (N) (i ∈ ℕ) form a finite cyclic group. Let r be the order of this group, i.e., let r ∈ ℕ be the least number such that a^{r} ≡ 1 (N). If we are lucky then r is even, and we can rewrite

a^{r} ≡ 1 (N)
⟺  (a^{r/2})^{2} − 1^{2} ≡ 0 (N)
⟺ (a^{r/2} − 1)(a^{r/2} + 1) ≡ 0 (N).

If we have a bit more luck, then a^{r/2} ≠ ±1 (N), and in this case, gcd(a^{r/2}−1, N) gives a nontrivial factor of N. The idea outlined in the previous paragraph is common to many algorithms for factoring integers also for classical computers. For instance, Pollard’s rho method [1] is based on the same trick. Basic number theoretic arguments show that if N is large, then almost every a < N will be coprime to N (if not, we have anyway found a factor when we check gcd(a, N) = 1), and almost every a has an even order. The only problem is to efficiently find the order r. This is the main step of Shor’s algorithm which is depicted in the following circuit.

The machine has two registers, one of length 2L and one of length L. The operation U(a, N) is supposed to map (x, y) to (x, y⊕a^{x} (N)). The “y⊕” is only needed to make U(a, N) unitary, as required, but actually we are only interested in computing a^{x} (N) and output it to the second register. The computation of U(a, N) can be done in time O(l^{3}) using repeated squaring and classical multiplication algorithms which can be implemented on a quantum computer without loss of complexity. The Hadamard transform on the left is meant to be applied to each qubit of this register independently. This leads to a cost of 2l = O(l) gates. The quantum fourier transform at the end can be implemented in a circuit with O(l^{2}) gates as has been shown in the previous section. Let’s see what the circuit computes. Let N ∈ ℕ be an L-bit number, not even (otherwise 2 is a factor), and not power of a prime. Let a > 1 be coprime to N. We denote the content of the two registers by different ket signs, so that the initial state of the machine is |0⟩|0⟩. This means that the first |0⟩ denotes 2L qubits and the second |0⟩ denotes L qubits all of which are set to 0. The first step is to apply Hadamard transforms to each of the qubits in the first register. This transforms the machine into the state

\frac{1}{2^{L/2}} ∑_{x=0}^{2^{L}−1} |x⟩|0⟩.

In the next step, the first register is raised to the power of x modulo N; the result is put into the second register:

\frac{1}{2^{L/2}} ∑_{x=0}^{2^{L}−1} |x⟩|a^{x} (N)⟩.

Now, a quantum fourier transform is applied to the first register, leaving the machine in the state

\frac{1}{2^{L}} ∑_{x=0}^{2^{L}−1} ( ∑_{y=0}^{2^{L}−1} ω^{xy}|y⟩)|a^{x} (N)⟩.

The final step is to measure the two registers. The measurement will result in a pair (y_{0}, a^{x_{0}} (N)). The probability to observe a particular output (y_{0}, a^{x_{0}} (N)) amounts to

|\frac{1}{2^{L}} ∑_{x:a^{x}≡a^{x_{0}} (N)} ω^{xy}|^{2},

because every term a^{x} that is equal to a^{x_{0}} modulo N contributes to the probability. Note once again that the classical view regarding the content of the two registers as independend from each other, does not work in the quantum case. Some manipulation of the probability formula shows that the probability distribution strongly favors values of y_{0} with ry_{0} ≈ k2^{2L} for some integer k. Hence,

\frac{y_{0}}{2^{2L}} ≈ \frac{k}{r} .

The value y_{0} is known from the measurement, and r is known to be less than N. By a continued fraction expansion, k/r can be guessed to be the closest faction to y_{0}/2^{2L} whose denominator is less than N. This finally determines the order r which we were after.

Every quantum algorithm is inherently probabilistic because every measurement of a computational result is necessarily indeterministic. However, there is even more “probabilism” in Shor’s factoring algorithm: Hoping for r to be even, hoping for a^{r/2} ≠ ±1, and hoping for guessing k/r correctly. Anyway, it can be shown that the factoring algorithm has a reasonalbe probability to succeed, and its complexity is only cubic in the length of the number to be factored.

4 Conclusion

Integers can be factored a great deal faster on quantum computers than on classical ones. As many algorithms in symbolic computation are of enormous complexity, it might be worthwhile to investigate how which speed-up can be achived for other problems. For instance, it would be interesting know how fast a Gröbner basis can be computed by a quantum computer. In the case of integer factorisation, the mathematical background is not too involved. However, development of other quantum algorithms for problems of symbolic computation might well also bring new ideas to light that are also interesting for their own. In this sense, it does not really matter whether or not it will ever be possible to build large scale quantum computers.

References

[1] Joachim v.z. Gathen, Jürgen Gerhard. Modern Computer Algebra. Cambridge University Press. 2000.

[2] Peter W. Shor. Polynomial-time Algorithms for Prime Factorisation and Discrete Logarithms. In SIAM J. Computing 26. pp. 1484–1509.

[3] Peter W. Shor. Quantum Computing. In Proceedings of the ICM. 1998.

[4] Artur Ekert, Patrick Hayden and Hitoshi Inamori. Basic Concepts in Quantum Computing. Centre for Quantum Computation. 2000.

[5] Stan Gudder. Quantum Computation. Americal Math Monthly, March 2003.

[6] John Preskill. Quantum Computation. Lecture Notes to course Physics 219/ Computer Science 219. http://www.theory.caltech.edu/people/preskill/ph229/ 1998.