Preface This is a set of lecture notes on quantum algorithms.It is primarily intended for graduate students who have already taken an introductory course on quantum information.Such a course typically covers only the early breakthroughs in quantum algorithms,namely Shor's factoring algorithm (1994)and Grover's searching algorithm(1996).Here we show that there is much more to quantum computing by exploring some of the many quantum algorithms that have been developed over the past twenty-five years. These notes cover several major topics in quantum algorithms.divided into six parts: In Part I,we discuss quantum circuits-in particular,the problem of expressing a quantum algorithm using a given universal set of quantum gates. In Part II,we discuss quantum algorithms for algebraic problems.Many of these algorithms generalize the main idea of Shor's algorithm.These algorithms use the quantum Fourier transform and typically achieve an exponential (or at least superpolynomial)speedup over classical computers.In particular, we explore a group-theoretic problem called the hidden subgroup problem.A solution of this problem for abelian groups leads to several applications;we also discuss what is known about the nonabelian case. In Part III,we explore the concept of quantum walk,a quantum generalization of random walk.This concept leads to a powerful framework for solving search problems,generalizing Grover's search algo- rithm. In Part IV,we discuss the model of quantum query complerity.We cover the two main methods for proving lower bounds on quantum query complexity(the polynomial method and the adversary method),demonstrating limitations on the power of quantum algorithms.We also discuss how the concept of span programs turns the quantum adversary method into an upper bound,giving optimal quantum algorithms for evaluating Boolean formulas. In Part V,we describe quantum algorithms for simulating the dynamics of quantum systems.We also discuss an application of quantum simulation to an algorithm for linear systems. In Part VI,we discuss adiabatic quantum computing,a general approach to solving optimization prob- lems(in a similar spirit to simulated annealing).Related ideas may also provide insights into how one might build a quantum computer. These notes were originally prepared for a course that was offered three times at the University of Waterloo:in the winter terms of 2008 (as CO 781)and of 2011 and 2013 (as CO 781/CS 867/QIC 823).I thank the students in the course for their feedback on the lecture notes.Each offering of the course covered a somewhat different set of topics.This document collects the material from all versions of the course and includes a few subsequent improvements. The material on quantum algorithms for algebraic problems has been collected into a review article that was written with Wim van Dam [34].I thank Wim for his collaboration on that project,which strongly infuenced the presentation in Part II Please keep in mind that these are rough lecture notes;they are not meant to be a comprehensive treat- ment of the subject,and there are surely at least a few mistakes.Corrections(by email to amchilds@umd.edu) are welcome. I hope you find these notes to be a useful resource for learning about quantum algorithms
Preface This is a set of lecture notes on quantum algorithms. It is primarily intended for graduate students who have already taken an introductory course on quantum information. Such a course typically covers only the early breakthroughs in quantum algorithms, namely Shor’s factoring algorithm (1994) and Grover’s searching algorithm (1996). Here we show that there is much more to quantum computing by exploring some of the many quantum algorithms that have been developed over the past twenty-five years. These notes cover several major topics in quantum algorithms, divided into six parts: • In Part I, we discuss quantum circuits—in particular, the problem of expressing a quantum algorithm using a given universal set of quantum gates. • In Part II, we discuss quantum algorithms for algebraic problems. Many of these algorithms generalize the main idea of Shor’s algorithm. These algorithms use the quantum Fourier transform and typically achieve an exponential (or at least superpolynomial) speedup over classical computers. In particular, we explore a group-theoretic problem called the hidden subgroup problem. A solution of this problem for abelian groups leads to several applications; we also discuss what is known about the nonabelian case. • In Part III, we explore the concept of quantum walk, a quantum generalization of random walk. This concept leads to a powerful framework for solving search problems, generalizing Grover’s search algorithm. • In Part IV, we discuss the model of quantum query complexity. We cover the two main methods for proving lower bounds on quantum query complexity (the polynomial method and the adversary method), demonstrating limitations on the power of quantum algorithms. We also discuss how the concept of span programs turns the quantum adversary method into an upper bound, giving optimal quantum algorithms for evaluating Boolean formulas. • In Part V, we describe quantum algorithms for simulating the dynamics of quantum systems. We also discuss an application of quantum simulation to an algorithm for linear systems. • In Part VI, we discuss adiabatic quantum computing, a general approach to solving optimization problems (in a similar spirit to simulated annealing). Related ideas may also provide insights into how one might build a quantum computer. These notes were originally prepared for a course that was offered three times at the University of Waterloo: in the winter terms of 2008 (as CO 781) and of 2011 and 2013 (as CO 781/CS 867/QIC 823). I thank the students in the course for their feedback on the lecture notes. Each offering of the course covered a somewhat different set of topics. This document collects the material from all versions of the course and includes a few subsequent improvements. The material on quantum algorithms for algebraic problems has been collected into a review article that was written with Wim van Dam [34]. I thank Wim for his collaboration on that project, which strongly influenced the presentation in Part II. Please keep in mind that these are rough lecture notes; they are not meant to be a comprehensive treatment of the subject, and there are surely at least a few mistakes. Corrections (by email to amchilds@umd.edu) are welcome. I hope you find these notes to be a useful resource for learning about quantum algorithms
Chapter 1 Preliminaries This chapter briefly reviews some background material on quantum computation.We cover these topics at a very high level,just to give a sense of what you should know to understand the rest of the lecture notes. If any of these topics are unfamiliar,you can learn more about them from a text on quantum computation such as Nielsen and Chuang [81];Kitaev,Shen,and Vyalyi [64];or Kaye,Laflamme,and Mosca [62]. 1.1 Quantum data A quantum computer is a device that uses a quantum mechanical representation of information to perform calculations.Information is stored in quantum bits,the states of which can be represented as e2-normalized vectors in a complex vector space.For example,we can write the state of n qubits as ）=】 azlz) (1.1) x∈{0,1}m where the arEC satisfy a2=1.We refer to the basis of states r)as the computational basis. It will often be useful to think of quantum states as storing data in a more abstract form.For example, given a group G,we could write g)for a basis state corresponding to the group element gEG,and l)=∑bglg) (1.2) 9EG for an arbitrary superposition over the group.We assume that there is some canonical way of efficiently representing group elements using bit strings;it is usually unnecessary to make this representation explicit. If a quantum computer stores the state and the state o),its overall state is given by the tensor product of those two states.This may be denoted ))=)o)=l,). 1.2 Quantum circuits The allowed operations on(pure)quantum states are those that map normalized states to normalized states, namely unitary operators U,satisfying UUt=UiU=I.(You probably know that there are more general quantum operations,but for the most part we will not need to use them in this course.) To have a sensible notion of efficient computation,we require that the unitary operators appearing in a quantum computation are realized by quantum circuits.We are given a set of gates,each of which acts on one or two qubits at a time (meaning that it is a tensor product of a one-or two-qubit operator with the identity operator on the remaining qubits).A quantum computation begins in the 0)state,applies a sequence of one-and two-qubit gates chosen from the set of allowed gates,and finally reports an outcome obtained by measuring in the computational basis
Chapter 1 Preliminaries This chapter briefly reviews some background material on quantum computation. We cover these topics at a very high level, just to give a sense of what you should know to understand the rest of the lecture notes. If any of these topics are unfamiliar, you can learn more about them from a text on quantum computation such as Nielsen and Chuang [81]; Kitaev, Shen, and Vyalyi [64]; or Kaye, Laflamme, and Mosca [62]. 1.1 Quantum data A quantum computer is a device that uses a quantum mechanical representation of information to perform calculations. Information is stored in quantum bits, the states of which can be represented as `2-normalized vectors in a complex vector space. For example, we can write the state of n qubits as |ψi = X x∈{0,1}n ax|xi (1.1) where the ax ∈ C satisfy P x |ax| 2 = 1. We refer to the basis of states |xi as the computational basis. It will often be useful to think of quantum states as storing data in a more abstract form. For example, given a group G, we could write |gi for a basis state corresponding to the group element g ∈ G, and |φi = X g∈G bg|gi (1.2) for an arbitrary superposition over the group. We assume that there is some canonical way of efficiently representing group elements using bit strings; it is usually unnecessary to make this representation explicit. If a quantum computer stores the state |ψi and the state |φi, its overall state is given by the tensor product of those two states. This may be denoted |ψi ⊗ |φi = |ψi|φi = |ψ, φi. 1.2 Quantum circuits The allowed operations on (pure) quantum states are those that map normalized states to normalized states, namely unitary operators U, satisfying UU† = U †U = I. (You probably know that there are more general quantum operations, but for the most part we will not need to use them in this course.) To have a sensible notion of efficient computation, we require that the unitary operators appearing in a quantum computation are realized by quantum circuits. We are given a set of gates, each of which acts on one or two qubits at a time (meaning that it is a tensor product of a one- or two-qubit operator with the identity operator on the remaining qubits). A quantum computation begins in the |0i state, applies a sequence of one- and two-qubit gates chosen from the set of allowed gates, and finally reports an outcome obtained by measuring in the computational basis
Chapter 1.Preliminaries 1.3 Universal gate sets In principle,any unitary operator on n qubits can be implemented using only 1-and 2-qubit gates.Thus we say that the set of all 1-and 2-qubit gates is (eractly)universal.Of course,some unitary operators may take many more 1-and 2-qubit gates to realize than others,and indeed,a counting argument shows that most unitary operators on n qubits can only be realized using an exponentially large circuit of 1-and 2-qubit gates. In general,we are content to give circuits that give good approximations of our desired unitary transfor- mations.We say that a circuit with gates U1,U2,...,U approximates U with precision e if IU-U..U2U1l≤e. (1.3) Here denotes some appropriate matrix norm,which should have the property that ifU-Vl is small, then U should be hard to distinguish from V no matter what quantum state they act on.A natural choice (which will be suitable for our purposes)is the spectral norm A‖：=max IA )川 (1.4) (where=v(l)denotes the vector 2-norm of )i.e.,the largest singular value of A.Then we call a set of elementary gates universal if any unitary operator on a fixed number of qubits can be approximated to any desired precision e using elementary gates. It turns out that there are finite sets of gates that are universal:for example,the set [H,T,C}with /1 000 ei/8 0 0 1 T:= 0 0 H 0 e-ir/ 0 001 (1.5) 0 010 There are situations in which we say a set of gates is effectively universal,even though it cannot actually approximate any unitary operator on n qubits.For example,the set {H,T2,Tof},where /1 0000000 01000000 00100000 Tof : 00010000 00001000 (1.6) 0000010 0 0 000000 1 0 0000010 is universal,but only if we allow the use of ancilla qubits (qubits that start and end in the 0)state). Similarly,the basis {H,Tof}is universal in the sense that,with ancillas,it can approximate any orthogonal matrix.It clearly cannot approximate complex unitary matrices,since the entries of H and Tof are real; but the effect of arbitrary unitary transformations can be simulated using orthogonal ones by simulating the real and imaginary parts separately. 1.4 Reversible computation Unitary matrices are invertible:in particular,U-1=Ut.Thus any unitary transformation is a reversible operation.This may seem at odds with how we often define classical circuits,using irreversible gates such as AND and OR.But in fact,any classical computation can be made reversible by replacing any irreversible gate zg(x)by the reversible gate (x,y)(,yg(x)),and running it on the input (x,0),producing (r,g()).In other words,by storing all intermediate steps of the computation,we make it reversible. On a quantum computer,storing all intermediate computational steps could present a problem,since two identical results obtained in different ways would not be able to interfere.However,there is an easy way to
2 Chapter 1. Preliminaries 1.3 Universal gate sets In principle, any unitary operator on n qubits can be implemented using only 1- and 2-qubit gates. Thus we say that the set of all 1- and 2-qubit gates is (exactly) universal. Of course, some unitary operators may take many more 1- and 2-qubit gates to realize than others, and indeed, a counting argument shows that most unitary operators on n qubits can only be realized using an exponentially large circuit of 1- and 2-qubit gates. In general, we are content to give circuits that give good approximations of our desired unitary transformations. We say that a circuit with gates U1, U2, . . . , Ut approximates U with precision if kU − Ut . . . U2U1k ≤ . (1.3) Here k·k denotes some appropriate matrix norm, which should have the property that if kU − V k is small, then U should be hard to distinguish from V no matter what quantum state they act on. A natural choice (which will be suitable for our purposes) is the spectral norm kAk := max |ψi kA|ψik k|ψik , (1.4) (where k|ψik = p hψ|ψi denotes the vector 2-norm of |ψi), i.e., the largest singular value of A. Then we call a set of elementary gates universal if any unitary operator on a fixed number of qubits can be approximated to any desired precision using elementary gates. It turns out that there are finite sets of gates that are universal: for example, the set {H, T, C} with H := 1 √ 2 1 1 1 −1 T := e iπ/8 0 0 e −iπ/8 C := 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 . (1.5) There are situations in which we say a set of gates is effectively universal, even though it cannot actually approximate any unitary operator on n qubits. For example, the set {H, T2 , Tof}, where Tof := 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 (1.6) is universal, but only if we allow the use of ancilla qubits (qubits that start and end in the |0i state). Similarly, the basis {H, Tof} is universal in the sense that, with ancillas, it can approximate any orthogonal matrix. It clearly cannot approximate complex unitary matrices, since the entries of H and Tof are real; but the effect of arbitrary unitary transformations can be simulated using orthogonal ones by simulating the real and imaginary parts separately. 1.4 Reversible computation Unitary matrices are invertible: in particular, U −1 = U † . Thus any unitary transformation is a reversible operation. This may seem at odds with how we often define classical circuits, using irreversible gates such as and and or. But in fact, any classical computation can be made reversible by replacing any irreversible gate x 7→ g(x) by the reversible gate (x, y) 7→ (x, y ⊕ g(x)), and running it on the input (x, 0), producing (x, g(x)). In other words, by storing all intermediate steps of the computation, we make it reversible. On a quantum computer, storing all intermediate computational steps could present a problem, since two identical results obtained in different ways would not be able to interfere. However, there is an easy way to
1.5.Uniformity 3 remove the accumulated information.After performing the classical computation with reversible gates,we simply XoR the answer into an ancilla register,and then perform the computation in reverse.Thus we can implement the map (x,y)(z,y f(z))even when f is a complicated circuit consisting of many gates. Using this trick,any computation that can be performed efficiently on a classical computer can be performed efficiently on a quantum computer:if we can efficiently implement the map xf(z)on a classical computer,we can efficiently perform the transformation y),yf(z))on a quantum computer.This transformation can be applied to any superposition of computational basis states,so for example,we can perform the transformation 1 ∑k,0→∑k,fa》 V2m (1.7） x∈{0,1} x∈{0,1}n Note that this does not necessarily mean we can efficiently implement the map )f(z)),even when f is a bijection(so that this is indeed a unitary transformation).However,if we can efficiently invert f,then we can indeed do this efficiently by computing f(z)in another register and then reversibly uncomputing x using the inverse of the reversible circuit for computing f-1 1.5 Uniformity When we give an algorithm for a computational problem,we consider inputs of varying sizes.Typically, the circuits for instances of different sizes will be related to one another in a simple way.But this need not be the case;and indeed,given the ability to choose an arbitrary circuit for each input size,we could have circuits computing uncomputable languages.Thus we require that our circuits be uniformly generated:say, that there exists a fixed(classical)Turing machine that,given a tape containing the symbol'1'n times, outputs a description of the nth circuit in time poly(n). 1.6 Quantum complexity We say that an algorithm for a problem is efficient if the circuit describing it contains a number of gates that is polynomial in the number of bits needed to write down the input.For example,if the input is a number modulo N,the input size is [log2 N]. With a quantum computer,as with a randomized (or noisy)classical computer,the final result of a computation may not be correct with certainty.Instead,we are typically content with an algorithm that can produce the correct answer with high enough probability (for a decision problem,bounded above 1/2; for a non-decision problem for which we can check a correct solution,(1)).By repeating the computation many times,we can make the probability of outputting an incorrect answer arbitrarily small. In addition to considering explicit computational problems,in which the input is a string,we will also consider the concept of query complerity.Here the input is a black box transformation,and our goal is to discover some property of the transformation by making as few queries as possible.For example,in Simon's problem,we are given a transformation f:Z2S satisfying f(r)=f(y)iff y=xt for some unknown tEZ2,and the goal is to learn t.The main advantage of considering query complexity is that it allows us to prove lower bounds on the number of queries required to solve a given problem.Furthermore,if we find an efficient algorithm for a problem in query complexity,then if we are given an explicit circuit realizing the black-box transformation,we will have an efficient algorithm for an explicit computational problem. Sometimes,we care not just about the size of a circuit for implementing a particular unitary operation, but also about its depth,the maximum number of gates on any path from an input to an output.The depth of a circuit tells us how long it takes to implement if we can perform gates in parallel. 1.7 Fault tolerance In any real computer,operations cannot be performed perfectly.Quantum gates and measurements may be performed imprecisely,and errors may happen even to stored data that is not being manipulated.Fortu-
1.5. Uniformity 3 remove the accumulated information. After performing the classical computation with reversible gates, we simply xor the answer into an ancilla register, and then perform the computation in reverse. Thus we can implement the map (x, y) 7→ (x, y ⊕ f(x)) even when f is a complicated circuit consisting of many gates. Using this trick, any computation that can be performed efficiently on a classical computer can be performed efficiently on a quantum computer: if we can efficiently implement the map x 7→ f(x) on a classical computer, we can efficiently perform the transformation |x, yi 7→ |x, y ⊕f(x)i on a quantum computer. This transformation can be applied to any superposition of computational basis states, so for example, we can perform the transformation 1 √ 2 n X x∈{0,1}n |x, 0i 7→ 1 √ 2 n X x∈{0,1}n |x, f(x)i. (1.7) Note that this does not necessarily mean we can efficiently implement the map |xi 7→ |f(x)i, even when f is a bijection (so that this is indeed a unitary transformation). However, if we can efficiently invert f, then we can indeed do this efficiently by computing f(x) in another register and then reversibly uncomputing x using the inverse of the reversible circuit for computing f −1 . 1.5 Uniformity When we give an algorithm for a computational problem, we consider inputs of varying sizes. Typically, the circuits for instances of different sizes will be related to one another in a simple way. But this need not be the case; and indeed, given the ability to choose an arbitrary circuit for each input size, we could have circuits computing uncomputable languages. Thus we require that our circuits be uniformly generated: say, that there exists a fixed (classical) Turing machine that, given a tape containing the symbol ‘1’ n times, outputs a description of the nth circuit in time poly(n). 1.6 Quantum complexity We say that an algorithm for a problem is efficient if the circuit describing it contains a number of gates that is polynomial in the number of bits needed to write down the input. For example, if the input is a number modulo N, the input size is dlog2 Ne. With a quantum computer, as with a randomized (or noisy) classical computer, the final result of a computation may not be correct with certainty. Instead, we are typically content with an algorithm that can produce the correct answer with high enough probability (for a decision problem, bounded above 1/2; for a non-decision problem for which we can check a correct solution, Ω(1)). By repeating the computation many times, we can make the probability of outputting an incorrect answer arbitrarily small. In addition to considering explicit computational problems, in which the input is a string, we will also consider the concept of query complexity. Here the input is a black box transformation, and our goal is to discover some property of the transformation by making as few queries as possible. For example, in Simon’s problem, we are given a transformation f : Z n 2 → S satisfying f(x) = f(y) iff y = x ⊕ t for some unknown t ∈ Z n 2 , and the goal is to learn t. The main advantage of considering query complexity is that it allows us to prove lower bounds on the number of queries required to solve a given problem. Furthermore, if we find an efficient algorithm for a problem in query complexity, then if we are given an explicit circuit realizing the black-box transformation, we will have an efficient algorithm for an explicit computational problem. Sometimes, we care not just about the size of a circuit for implementing a particular unitary operation, but also about its depth, the maximum number of gates on any path from an input to an output. The depth of a circuit tells us how long it takes to implement if we can perform gates in parallel. 1.7 Fault tolerance In any real computer, operations cannot be performed perfectly. Quantum gates and measurements may be performed imprecisely, and errors may happen even to stored data that is not being manipulated. Fortu-
Chapter 1.Preliminaries nately,there are protocols for dealing with faults that may occur during the execution of a quantum com- putation.Specifically,the threshold theorem states that as long as the noise level is below some threshold (depending on the noise model,but typically in the range of 10-3 to 10-4),an arbitrarily long computation can be performed with an arbitrarily small amount of error (see for example [50]). In this course,we will always assume implicitly that fault-tolerant protocols have been applied,such that we can effectively assume a perfectly functioning quantum computer
4 Chapter 1. Preliminaries nately, there are protocols for dealing with faults that may occur during the execution of a quantum computation. Specifically, the threshold theorem states that as long as the noise level is below some threshold (depending on the noise model, but typically in the range of 10−3 to 10−4 ), an arbitrarily long computation can be performed with an arbitrarily small amount of error (see for example [50]). In this course, we will always assume implicitly that fault-tolerant protocols have been applied, such that we can effectively assume a perfectly functioning quantum computer