QuantumAlgorithmsAndreas Klappenecker Texas A&M UniversityLecture notes of a course given in Spring 2003. Preliminary draft.c 2003 by Andreas Klappenecker. All rights reserved.PrefaceQuantum computing provides a fresh perspective on information processing.Some quantum algorithms have the promise to possibly provide an exponen-tial speed-up over classical deterministic and randomized algorithms, whichexplains the massive worldwide efforts to build a viable quantum computer.However, this is by no means the only motivation. Quantum computing hasserious repercussions on classical computing as well.These lecture notes provide a rapid introduction to the main ideas behindquantum algorithms. The subject matter is not difficult, but dramaticallydifferent from its classical counterpart. We provide numerous very simpleexercises that are designed to ease the transition into the quantum realm.Solving the exercises will help to gain an active working knowledge.Our approach is largely based on the quantum circuit model, which iseasy to understand. This model abstracts from the nature and the dynamicsof the physical system realizing the quantum computer. The advantage of thisapproach is that within an extremely short period of time it will be possibleto cover interesting algorithms.The course requires some background in linear algebra. The books LinearAlgebra by Serge Lang and Linear Algebra Done Right by Sheldon Axler areexcellent sources to review such material.Please note that this is a preliminary draft. The lecture notes are incom-plete, and all parts are subject to change. The material should be read inconjuction with the books Quantum Computation and Quantum Informationby Michael Nielsen and Isaac Chuang and Classical and Quantum Computa-tion by Alexei Kitaev, A.H. Shen, and M.N. Vyalyi.If you read these notes, then you have accepted a contract: you agree tocommunicate all errors to me. If you do not want to burden yourself with thistask, then do not read further.Andreas KlappeneckerCollege Station, TexasiChapter 2Quantum CircuitsQuantum computing can be based on various different computational models.The most accessible one is the quantum circuit model, which specifies a se-quence of operations that manipulate the state of the quantum computer atdiscrete time steps. The basic rules of this model are surprisingly simple. Thischapter introduces the basic properties of quantum states, quantum gates, andmeasurements.§1 Quantum StatesA bit has two distinguishable states, denoted by 0 and 1. A classical computermanipulates a set of bits, which form the memory of the computer. Thememory of a quantum computer is based in a similar way on the notion of aquantum bit, qubit for short. A qubit has two clearly distinguishable states,denoted by |0i and |1i. The possible states of a qubit are not exhausted bythese two possibilities. In general, the state of a qubit is of the form a|0i+b|1i,where a and b are complex numbers satisfying |a|2+ |b|2= 1.The states |0i and |1i should be understood as basis vectors of a complextwo-dimensional vector space. We can associate with these states the basisvectors|0i =10, |1i =01. (2.1)The state a|0i + b|1i is a linear combination of these two basis vectors, andis represented by the vector (a, b)t. The operations of the quantum computermanipulate these vectors by linear transformations or by measurements.The value of a quantum bit is always 0 or 1, never anything else. If a qubitis in the state a|0i + b|1i, then this means that the value 0 is observed with12 CHAPTER 2. QUANTUM CIRCUITSprobability |a|2, and the value 1 with probability |b|2. A measurement in thecomputational basis returns the value 0 or 1 according to this rule, and setsthe qubit to the state |0i or |1i, respectively. A consequence is that if themeasurement is repeated, then it will return the same value.It is easy to construct a state that yields a fair coin-flip. Choose the state1√2|0i +1√2|1i. Then 0 and 1 are both observed with probability (1/√2)2=1/2. The resulting state after the measurement is |0i, if the measurementresult was 0, and |1i otherwise.Exercise 2.1 Assume that a qubit is in the state1√10|0i +3√10|1i. What isthe probability to observe 0, or 1, respectively?Exercise 2.2 Assume that a qubit is in the statei√2|0i−1√2|1i. What is theprobability to observe 0, or 1, respectively?A memory consisting of n quantum bits has 2nbasis states, which are de-noted by |0 ···00i, |0 ··· 01i, |0 ··· 10i, . . . , |1 ···11i. The state of the memoryis a linear combination of these basis states. Denote by F2the finite field withtwo elements 0 and 1. An arbitrary state of the memory is of the formXk∈Fn2ak|ki, withX|ak|2= 1.If we read out the memory by a measurement in the computational basis, thenwe will observe the result k, a string of n bits, with probability |ak|2. The scalarcoefficients akare called probability amplitudes or, simply, amplitudes.Exercise 2.3 What is the probability of observing 11, if the memory is inthe state12|00i −12|10i +i√2|11i? In what state is the memory once we haveobserved 11?Exercise 2.4 Describe all possible states of a system of two quantum bitssuch that a measurement in the computational basis yields 00 with probability1/2, and the results 01 and 11 both with probability 1/4.Any quantum system with at least two different basis states can basicallystore a quantum bit, and finding appropriate storage media for a quantumcomputer is a very active area of current research. The linear combinationof basis states reflects the superposition principle of quantum mechanics. Itshould be noted that only the measurement process introduces randomizedbehavior in quantum algorithms. All other operations of a quantum computerare completely deterministic.§2. A SINGLE QUANTUM BIT 3§2 A Single Quantum BitThe operations of a quantum computer allow reading, writing, or manipulat-ing the content of the memory, and therefore serve the same purpose as theoperations of a classical computer. The main distinction is that the opera-tions of a quantum computer are formulated to be conformant with the lawsof quantum mechanics. We explain in this section the basic operations on asingle quantum bit, and introduce some convenient notations.The input operation of a quantum computer can prepare the memory inany basis state. As a result, each quantum bit is either in the state |0i orin the state |1i, but not in a superposition of these basis states. The
View Full Document