Share Pdf : Lecture Notes On Quantum Algorithms

Download and Preview : Lecture Notes On Quantum Algorithms

Report CopyRight/DMCA Form For : Lecture Notes On Quantum Algorithms

## Transcription

Preface vii, 1 Preliminaries 1, 1 1 Quantum data 1. 1 2 Quantum circuits 1, 1 3 Universal gate sets 2, 1 4 Reversible computation 2. 1 5 Uniformity 3, 1 6 Quantum complexity 3, 1 7 Fault tolerance 3. I Quantum circuits 5, 2 Efficient universality of quantum circuits 7. 2 1 Subadditivity of errors 7, 2 2 The group commutator and a net around the identity 8.

2 3 Proof of the Solovay Kitaev Theorem 8, 2 4 Proof of Lemma 2 3 9. 3 Quantum circuit synthesis over Clifford T 11, 3 1 Converting to Matsumoto Amano normal form 11. 3 2 Uniqueness of Matsumoto Amano normal form 12, 3 3 Algebraic characterization of Clifford T unitaries 13. 3 4 From exact to approximate synthesis 14, II Quantum algorithms for algebraic problems 15. 4 The abelian quantum Fourier transform and phase estimation 17. 4 1 Quantum Fourier transform 17, 4 2 QFT over Z2n 17.

4 3 Phase estimation 19, 4 4 QFT over ZN and over a general finite abelian group 19. 5 Discrete log and the hidden subgroup problem 21, 5 1 Discrete log 21. 5 2 Diffie Hellman key exchange 21, 5 3 The hidden subgroup problem 22. 5 4 Shor s algorithm 23, 6 The abelian HSP and decomposing abelian groups 25. 6 1 The abelian HSP 25, 6 2 Decomposing abelian groups 27.

7 Quantum attacks on elliptic curve cryptography 29. 7 1 Elliptic curves 29, 7 2 Elliptic curve cryptography 31. 7 3 Shor s algorithm for discrete log over elliptic curves 32. 8 Quantum algorithms for number fields 33, iv Contents. 8 1 Review Order finding 33, 8 2 Pell s equation 33. 8 3 Some basic algebraic number theory 34, 8 4 A periodic function for the units of Z d 35. 9 Period finding from Z to R 37, 9 1 Period finding over the integers 37.

9 2 Period finding over the reals 39, 9 3 Other algorithms for number fields 41. 10 Quantum query complexity of the HSP 43, 10 1 The nonabelian HSP and its applications 43. 10 2 The standard method 44, 10 3 Query complexity of the HSP 45. 11 Fourier analysis in nonabelian groups 47, 11 1 A brief introduction to representation theory 47. 11 2 Fourier analysis for nonabelian groups 49, 12 Fourier sampling 51.

12 1 Weak Fourier sampling 51, 12 2 Normal subgroups 52. 12 3 Strong Fourier sampling 53, 13 Kuperberg s algorithm for the dihedral HSP 55. 13 1 The HSP in the dihedral group 55, 13 2 Fourier sampling in the dihedral group 56. 13 3 Combining states 56, 13 4 The Kuperberg sieve 57. 13 5 Analysis of the Kuperberg sieve 57, 13 6 Entangled measurements 58.

14 The HSP in the Heisenberg group 59, 14 1 The Heisenberg group 59. 14 2 Fourier sampling 60, 14 3 Two states are better than one 60. 15 Approximating the Jones polynomial 63, 15 1 The Hadamard test 63. 15 2 The Jones polynomial 63, 15 3 Links from braids 64. 15 4 Representing braids in the Temperley Lieb algebra 64. 15 5 A quantum algorithm 65, 15 6 Quality of approximation 65.

15 7 Other algorithms 66, III Quantum walk 67, 16 Continuous time quantum walk 69. 16 1 Continuous time quantum walk 69, 16 2 Random and quantum walks on the hypercube 70. 16 3 Random and quantum walks in one dimension 71, 16 4 Black box traversal of the glued trees graph 71. 16 5 Quantum walk algorithm to traverse the glued trees graph 72. 16 6 Classical and quantum mixing 74, 16 7 Classical lower bound 76. 17 Discrete time quantum walk 77, 17 1 Discrete time quantum walk 77.

17 2 How to quantize a Markov chain 78, Contents v. 17 3 Spectrum of the quantum walk 79, 17 4 Hitting times 80. 18 Unstructured search 83, 18 1 Unstructured search 83. 18 2 Quantum walk algorithm 83, 18 3 Amplitude amplification and quantum counting 84. 18 4 Search on graphs 85, 19 Quantum walk search 87.

19 1 Element distinctness 87, 19 2 Quantum walk algorithm 88. 19 3 Quantum walk search algorithms with auxiliary data 89. IV Quantum query complexity 91, 20 Query complexity and the polynomial method 93. 20 1 Quantum query complexity 93, 20 2 Quantum queries 94. 20 3 Quantum algorithms and polynomials 94, 20 4 Symmetrization 95. 20 5 Parity 95, 20 6 Unstructured search 96, 21 The collision problem 99.

21 1 Problem statement 99, 21 2 Classical query complexity 99. 21 3 Quantum algorithm 100, 21 4 Toward a quantum lower bound 100. 21 5 Constructing the functions 101, 21 6 Finishing the proof 102. 22 The quantum adversary method 105, 22 1 Quantum adversaries 105. 22 2 The adversary method 106, 22 3 Example Unstructured search 109.

23 Span programs and formula evaluation 111, 23 1 The dual of the adversary method 111. 23 2 Span programs 112, 23 3 Unstructured search 113. 23 4 Formulas and games 113, 23 5 Function composition 114. 23 6 An algorithm from a dual adversary solution 115. 24 Learning graphs 117, 24 1 Learning graphs and their complexity 117. 24 2 Unstructured search 117, 24 3 From learning graphs to span programs 118.

24 4 Element distinctness 119, 24 5 Other applications 120. V Quantum simulation 121, 25 Simulating Hamiltonian dynamics 123. 25 1 Hamiltonian dynamics 123, 25 2 Efficient simulation 123. 25 3 Product formulas 124, 25 4 Sparse Hamiltonians 125. vi Contents, 25 5 Measuring an operator 126, 26 Fast quantum simulation algorithms 129.

26 1 No fast forwarding 129, 26 2 Quantum walk 130. 26 3 Linear combinations of unitaries 130, VI Adiabatic quantum computing 133. 27 The quantum adiabatic theorem 135, 27 1 Adiabatic evolution 135. 27 2 Proof of the adiabatic theorem 136, 28 Adiabatic optimization 141. 28 1 An adiabatic optimization algorithm 141, 28 2 The running time and the gap 142.

28 3 Adabatic optimization algorithm for unstructured search 143. 29 An example of the success of adiabatic optimization 147. 29 1 The ring of agrees 147, 29 2 The Jordan Wigner transformation From spins to fermions 148. 29 3 Diagonalizing a system of free fermions 150, 29 4 Diagonalizing the ring of agrees 152. 30 Universality of adiabatic quantum computation 155. 30 1 The Feynman quantum computer 155, 30 2 An adiabatic variant 156. 30 3 Locality 159, Bibliography 161, 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 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. 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. 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 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 33 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 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. viii Contents, 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 75 Kitaev Shen and Vyalyi 62 or Kaye Laflamme and Mosca 60. 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 ax xi 1 1, where the ax C satisfy 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 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 U U 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, 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. 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 Ut approximates U with precision if. kU Ut U2 U1 k 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 1 4, where k ik 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. i 8 1 0 0 0, 1 1 1 e 0 0 1 0 0, H T i 8 0 0 0 1, 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 T 2 Tof where. 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. Tof 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, is universal but only if we allow the use of ancilla qubits qubits that start and end in the 0i state. quantum algorithms for evaluating Boolean formulas InPart 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 InPart VI we discuss adiabatic quantum computing a general approach to solving optimization prob lems in a similar spirit to simulated annealing Related ideas