Lecture notes in Quantum Computing

how quantum computing will change the world and how does quantum computing work | pdf free download
JackBrown Profile Pic
JackBrown,Georgia,Professional
Published Date:11-07-2017
Your Website URL(Optional)
Comment
Quantum Computing: Lecture Notes Ronald de WolfContents 1 Quantum Computing 1 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Quantum mechanics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2.1 Superposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2.2 Measurement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.3 Unitary evolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Quantum memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Elementary gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.5 Example: quantum teleportation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2 The Circuit Model and Deutsch-Jozsa 9 2.1 Quantum computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.1.1 Classical circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.1.2 Quantum circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2 Universality of various sets of elementary gates . . . . . . . . . . . . . . . . . . . . . 11 2.3 Quantum parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.4 The early algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.4.1 Deutsch-Jozsa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.4.2 Bernstein-Vazirani . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3 Simon’s Algorithm 16 3.1 The problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.2 The quantum algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.3 Classical algorithms for Simon’s problem . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.3.1 Upper bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.3.2 Lower bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4 The Fourier Transform 21 4.1 The classical discrete Fourier transform . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.2 The Fast Fourier Transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.3 Application: multiplying two polynomials . . . . . . . . . . . . . . . . . . . . . . . . 22 4.4 The quantum Fourier transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.5 An efficient quantum circuit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.6 Application: phase estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 ii5 Shor’s Factoring Algorithm 28 5.1 Factoring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 5.2 Reduction from factoring to period-finding. . . . . . . . . . . . . . . . . . . . . . . . 28 5.3 Shor’s period-finding algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.4 Continued fractions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 6 Grover’s Search Algorithm 35 6.1 The problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 6.2 Grover’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 6.3 Amplitude amplification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 6.4 Application: satisfiability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 7 Quantum Walk Algorithms 41 7.1 Classical random walks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 7.2 Quantum walks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 7.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 7.3.1 Grover search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 7.3.2 Collision problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 7.3.3 Finding a triangle in a graph . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 8 Quantum Query Lower Bounds 49 8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 8.2 The polynomial method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 8.3 The quantum adversary method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 9 Quantum Complexity Theory 56 9.1 Most functions need exponentially many gates . . . . . . . . . . . . . . . . . . . . . . 56 9.2 Classical and quantum complexity classes . . . . . . . . . . . . . . . . . . . . . . . . 57 9.3 Classically simulating quantum computers in polynomial space . . . . . . . . . . . . 58 10 Quantum Encodings, with a Non-Quantum Application 61 10.1 Mixed states and general measurements . . . . . . . . . . . . . . . . . . . . . . . . . 61 10.2 Quantum encodings and their limits . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 10.3 Lower bounds on locally decodable codes . . . . . . . . . . . . . . . . . . . . . . . . 64 11 Quantum Communication Complexity 67 11.1 Classical communication complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 11.2 The quantum question . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 11.3 Example 1: Distributed Deutsch-Jozsa . . . . . . . . . . . . . . . . . . . . . . . . . . 69 11.4 Example 2: The Intersection problem . . . . . . . . . . . . . . . . . . . . . . . . . . 70 11.5 Example 3: The vector-in-subspace problem . . . . . . . . . . . . . . . . . . . . . . . 71 11.6 Example 4: Quantum fingerprinting . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 12 Entanglement and Non-locality 75 12.1 Quantum non-locality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 12.2 CHSH: Clauser-Horne-Shimony-Holt . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 12.3 Magic square game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 iiiChapter 1 Quantum Computing 1.1 Introduction Today’s computers—both in theory (Turing machines) and practice (PCs)—are based on classical physics. However, modern quantum physics tells us that the world behaves quite differently. A quantumsystemcanbeinasuperposition ofmanydifferentstatesatthesametime,andcanexhibit interference effects during the course of its evolution. Moreover, spatially separated quantum systems may be entangled with each other and operations may have “non-local” effects because of this. Quantum computation is the field that investigates the computational power and other prop- erties of computers based on quantum-mechanical principles. An important objective is to find quantum algorithms that are significantly faster than any classical algorithm solving the same problem. The field started in the early 1980s with suggestions for analog quantum computers by Yuri Manin 65 (and appendix of 66), Richard Feynman 41, 42, and Paul Benioff 14, and reached more digital ground when in 1985 David Deutsch defined the universal quantum Turing machine 33. The following years saw only sparse activity, notably the development of the first al- gorithmsbyDeutschandJozsa35andbySimon82,andthedevelopmentofquantumcomplexity theory by Bernstein and Vazirani 18. However, interest in the field increased tremendously after Peter Shor’s very surprising discovery of efficient quantum algorithms for the problems of integer factorization and discrete logarithms in 1994 81. Since most of current classical cryptography is based on the assumption that these two problems are computationally hard, the ability to actually build and use a quantum computer would allow us to break most current classical cryptographic systems, notably the RSA system 76, 77. (In contrast, a quantum form of cryptography due to Bennett and Brassard 17 is unbreakable even for quantum computers.) Let us mention three different motivations for studying quantum computers, from practical to more philosophical: 1. The process of miniaturization that has made current classical computers so powerful and cheap, has already reached micro-levels where quantum effects occur. Chip-makers tend to go to great lengths to suppressthose quantum effects, butinstead one might also try to make good use of them. 2. Making use of quantum effects allows one to speed-up certain computations enormously (sometimes exponentially), and even enables some things that are impossible for classical 1computers The main purpose of this course is to explain these things (algorithms, crypto, etc.) in detail. 3. Finally, one might state the main goal of theoretical computer science as “study the power and limitations of the strongest-possible computational devices that nature allows us.” Since our current understanding of nature is quantum mechanical, theoretical computer science should be studying the power of quantum computers, not classical ones. Before limiting ourselves to theory, let us say a few words about practice: to what extent will quantum computers ever be built? At this point in time, it is just too early to tell. The first small 2-qubit quantum computer was built in 1997 and 2001 a 5-qubit quantum computer was used to successfully factor the number 15 85. Since then, experimental progress on a number of different technologies has beensteady but slow. Thepractical problems facing physical realizations of quantum computers seem formidable. The problems of noise and decoherence have to some extent been solved in theory by the discovery of quantum error-correcting codes and fault-tolerant computing (see, e.g., Chapter 14 in these notes or 72, Chapter 10), but these problems are by no means solved in practice. On the other hand, we shouldrealize that the field of physical realization of quantum computing is still in its infancy and that classical computing had to face and solve many formidable technical problems as well—interestingly, often these problems were even of the samenatureasthose nowfacedbyquantumcomputing(e.g., noise-reduction anderror-correction). Moreover, thedifficultiesfacingtheimplementationofafullquantumcomputermayseemdaunting, but more limited things involving quantum communication have already been implemented with some success, for example teleportation (which is the process of sending qubits using entanglement andclassical communication),andquantumcryptographyisnowadaysevencommerciallyavailable. Even if the theory of quantum computing never materializes to a real physical computer, quantum-mechanical computers are still anextremely interesting ideawhich will bearfruitin other areas than practical fast computing. On the physics side, it may improve our understanding of quantum mechanics. The emerging theory of entanglement has already done this to some extent. Onthecomputerscienceside, thetheoryofquantumcomputationgeneralizes andenrichesclassical complexity theory and may help resolve some of its problems. 1.2 Quantum mechanics Here we give a brief and abstract introduction to quantum mechanics. In short: a quantum state is a superposition of classical states, to which we can apply either a measurement or a unitary operation. For the required linear algebra and Dirac notation we refer to Appendix A. 1.2.1 Superposition Consider some physical system that can be inN different, mutually exclusive classical states. Call these states 1i,2i,...,Ni. Roughly, by a “classical” state we mean a state in which the system can befoundifwe observe it. A pure quantum state (usually justcalled state)φi isa superposition of classical states, written φi =α 1i+α 2i+···+α Ni. 1 2 N Here α is a complex number that is called the amplitude of ii in φi (see Appendix B for a brief i explanation of complex numbers). Intuitively, a system in quantum state φi is in all classical 2states at the same time It is in state1i with amplitudeα , in state2i with amplitudeα , and so 1 2 on. Mathematically, the states1i,...,Ni form an orthonormal basis of anN-dimensional Hilbert space (i.e., anN-dimensional vector space equipped with an inner product) of dimensionN, and a quantum state φi is a vector in this space. 1.2.2 Measurement There are two things we can do with a quantum state: measure it or let it evolve unitarily without measuring it. We will deal with measurement first. Measurement in the computational basis Suppose we measure state φi. We cannot “see” a superposition itself, but only classical states. Accordingly, if we measure stateφi we will see one and only one classical stateji. Which specific ji will we see? This is not determined in advance; the only thing we can say is that we will 2 see state ji with probability α , which is the squared norm of the corresponding amplitude α j j √ 2 2 (a+ib = a +b ). Thus observing a quantum state induces a probability distribution on the P N 2 classical states, given by the squared norms of the amplitudes. This implies α =1, so the j j=1 vectorofamplitudeshas(Euclidean)norm1. Ifwemeasureφiandseeclassicalstatejiasaresult, thenφi itselfhas“disappeared,”andall thatisleftisji. Inotherwords, observingφi “collapses” the quantum superposition φi to the classical state ji that we saw, and all “information” that might have been contained in the amplitudes α is gone. i Projective measurement Asomewhatmoregeneralkindofmeasurementthantheabove“measurementinthecomputational (or standard) basis” is possible. This will be used only sparsely in the course, so it may be skipped on a first reading. Such a projective measurement is described by projectors P ,...,P (m≤N) 1 m which sum to identity. These projectors are then pairwise orthogonal, meaning that PP = 0 if i j i = 6 j. The projectorP projects on some subspaceV of the total Hilbert spaceV, and every state j j P m φi∈V canbedecomposedinauniquewayasφi = φ i,withφ i=P φi∈V . Becausethe j j j j j=1 projectors are orthogonal, the subspacesV are orthogonal as well, as are the statesφ i. When we j j 2 applythismeasurementtothepurestateφi, thenwewillgetoutcomej withprobabilitykφ ik = j Tr(P φihφ) and the state will then “collapse” to the new state φ i/kφ ik=P φi/kP φik. j j j j j For example, a measurement in the standardbasis is the specific projective measurement where m=N andP =jihj. Thatis,P projectsontothestandardbasisstatejiandthecorresponding j j P N subspace V is the space spanned by ji. Consider the state φi = α ji. Note that P φi = j j j j=1 2 2 α ji, so applying our measurement to φi will give outcome j with probability kα jik = α , j j j α α j j and in that case the state collapses to α ji/kα jik = ji. The norm-1 factor may be j j α α j j disregarded because it has no physical significance, so we end up with the state ji as we saw before. As another example, a measurement that distinguishes between ji with j ≤ N/2 and ji P P with j N/2 corresponds to the two projectors P = jihj and P = jihj. 1 2 j≤N/2 jN/2 q 1 2 √ Applying this measurement to the stateφi = 1i+ Ni will give outcome 1 with probability 3 3 32 kP φik = 1/3, in which case the state collapses to 1i, and will give outcome 2 with probability 1 2 kP φik =2/3, in which case the state collapses toNi. 2 1.2.3 Unitary evolution Instead of measuringφi, we can also apply some operation to it, i.e., change the state to some ψi =β 1i+β 2i+···+β Ni. 1 2 N Quantum mechanics only allows linear operations to be applied to quantum states. What this T means is: if we view a state like φi as an N-dimensional vector (α ,...,α ) , then applying an 1 N operation that changes φi to ψi corresponds to multiplying φi with an N ×N complex-valued matrix U:     α β 1 1     . . . . U = .     . . α β N N P P Note that by linearity we have ψi =Uφi =U ( αii) = αUii. i i i i Because measuring ψi should also give a probability distribution, we have the constraint P N 2 β = 1. This implies that the operation U must preserve the norm of vectors, and hence j j=1 −1 must be a unitary transformation. A matrix U is unitary if its inverse U equals its conjugate ∗ transpose U . This is equivalent to saying that U always maps a vector of norm 1 to a vector of norm1. Becauseaunitarytransformationalwayshasaninverse,itfollowsthatany(non-measuring) −1 operation on quantumstates mustbe reversible: byapplyingU we can always “undo”the action ofU,andnothingislostintheprocess. Ontheotherhand,ameasurementisclearlynon-reversible, because we cannot reconstruct φi from the observed classical state ji. 1.3 Quantum memory In classical computation, the unit of information is a bit, which can be 0 or 1. In quantum compu- tation, this unit is a quantum bit (qubit), which is a superposition of 0 and 1. Consider a system   1 with 2 basis states, call them 0i and 1i. We identify these basis states with the vectors 0   0 and , respectively. A single qubit can be in any superposition 1 2 2 α 0i+α 1i, α +α =1. 0 1 0 1 2 Accordingly, a single qubit “lives” in the vector spaceC . Similarly we can think of systems of more than 1 qubit, which “live” in the tensor product space of several qubit systems. For instance, a 2-qubit system has 4 basis states: 0i⊗0i,0i⊗1i,1i⊗0i,1i⊗1i. Here for instance1i⊗0i means that the first qubit is in its basis state 1i and the second qubit is in its basis state 0i. We will often abbreviate this to1i0i, 1,0i, or even 10i. n More generally, a register ofn qubits has 2 basis states, each of the formb i⊗b i⊗...⊗b i, 1 2 n n with b ∈ 0,1. We can abbreviate this to b b ...b i. We will often abbreviate 0...0 to 0 . i 1 2 n n Since bitstrings of length n can be viewed as numbers between 0 and 2 −1, we can also write 4n the basis states as numbers0i,1i,2i,...,2 −1i. A quantum register of n qubits can be in any superposition n 2 −1 X n 2 α 0i+α 1i+···+α n 2 −1i, α =1. 0 1 2 −1 j j=0 2 If we measure this in the standard basis, we obtain the n-bit state state ji with probabilityα . j Measuring just the first qubit of a state would correspond to the projective measurement that has the two projectors P = 0ih0⊗I n−1 and P = 1ih1⊗I n−1. For example, applying this 0 2 1 2 q 1 2 √ measurement to the state 0iφi+ 1iψi will give outcome 0 with probability 1/3 (the state 3 3 thenbecomes0iφi)andoutcome1withprobability2/3(thestatethenbecomes1iψi). Similarly, measuring the first n qubits of an (n+m)-qubit state in the standard basis corresponds to the n n m projective measurement that has 2 projectors P =iihi⊗I for i∈0,1 . i 2 Animportant propertythat deserves tobementioned is entanglement, whichreferstoquantum correlations between different qubits. For instance, consider a 2-qubit register that is in the state 1 1 √ 00i+√ 11i. 2 2 Such2-qubit states are sometimes called EPR-pairs inhonor ofEinstein, Podolsky, andRosen39, who first examined such states and their seemingly paradoxical properties. Initially neither of the two qubits has a classical value0i or1i. However, if we measure the first qubit and observe, say, a 0i, then the whole state collapses to 00i. Thus observing the first qubit immediately fixes also the second, unobserved qubit to a classical value. Since the two qubits that make up the register may be far apart, this example illustrates some of the non-local effects that quantum systems can exhibit. In general, a bipartite state φi is called entangled if it cannot be written as a tensor productφ i⊗φ i whereφ i lives in the first space andφ i lives in the second. A B A B At this point, a comparison with classical probability distributions may be helpful. Suppose n m we have two probability spaces, A and B, the first with 2 possible outcomes, the second with 2 n possible outcomes. A distribution on the first space can be described by 2 numbers (non-negative n reals summing to 1; actually there are only 2 − 1 degrees of freedom here) and a distribution m on the second by 2 numbers. Accordingly, a product distribution on the joint space can be n m described by 2 + 2 numbers. However, an arbitrary (non-product) distribution on the joint n+m n+m space takes 2 real numbers, since there are 2 possible outcomes in total. Analogously, an n n-qubit state φ i can be described by 2 numbers (complex numbers whose squared moduli sum A m n m to 1), an m-qubit state φ i by 2 numbers, and their tensor product φ i⊗φ i by 2 +2 B A B n+m numbers. However, an arbitrary (possibly entangled) state in the joint space takes 2 numbers, n+m since it lives in a 2 -dimensional space. We see that the number of parameters required to describe quantum states is the same as the number of parameters needed to describe probability 1 distributions. Also note the analogy between statistical independence of two random variables A and B and non-entanglement of the product state φ i⊗φ i. However, despite the similarities A B between probabilities and amplitudes, quantum states are much more powerful than distributions, because amplitudes may have negative parts which can lead to interference effects. Amplitudes only become probabilities when we square them. The art of quantum computing is to use these special properties for interesting computational purposes. 1 Two random variablesA andB are independent if their joint probability distribution can be written as a product of individual distributions for A and for B: PrA =a∧B =b= PrA =a·PrB =b for all possible values a,b. 51.4 Elementary gates A unitary that acts on a small number of qubits (say, at most 3) is often called a gate, in analogy to classical logic gates like AND, OR, and NOT; more about that in the next chapter. Two simple but important 1-qubit gates are the bitflip gate X (which negates the bit, i.e., swaps 0i and 1i) and the phaseflip gate Z (which puts a − in front of 1i). Represented as 2×2 unitary matrices, these are     0 1 1 0 X = , Z = . 1 0 0 −1 Anotherimportant1-qubitgateisthephase gate R ,whichmerelyrotatesthephaseofthe1i-state φ by an angle φ: R 0i =0i φ iφ R 1i =e 1i φ This corresponds to the unitary matrix   1 0 R = . φ iφ 0 e iπ Note that Z is a special case of this: Z =R , because e =−1. π Possibly the most important 1-qubit gate is the Hadamard transform, specified by: 1 1 H0i = √ 0i+√ 1i 2 2 1 1 √ √ H1i = 0i− 1i 2 2 As a unitary matrix, this is represented as   1 1 1 √ H = . 1 −1 2 If we apply H to initial state 0i and then measure, we have equal probability of observing 0i or 1i. Similarly, applying H to 1i and observing gives equal probability of 0i or 1i. However, 1 1 √ √ if we apply H to the superposition 0i + 1i then we obtain 0i: the positive and negative 2 2 amplitudes for 1i cancel out (note that this also means that H is its own inverse) This effect is called interference, and is analogous to interference patterns between light or sound waves. An example of a two-qubit gate is the controlled-not gate CNOT. It negates the second bit of its input if the first bit is 1, and does nothing if it’s 0: CNOT0ibi =0ibi CNOT1ibi =1i1−bi In matrix form, this is   1 0 0 0   0 1 0 0   CNOT= .   0 0 0 1 0 0 1 0 61.5 Example: quantum teleportation In the next chapter we will look in more detail at how we can use and combine such elementary gates, but as an example we will here already explain teleportation 15. Suppose there are two parties, Alice and Bob. Alice hasa qubitα 0i+α 1i that she wants to sendto Bob via a classical 0 1 channel. Without further resources this would be impossible, but Alice also shares an EPR-pair 1 √ (00i+11i) 2 with Bob (say Alice holds the first qubit and Bob the second). Initially, their joint state is 1 (α 0i+α 1i)⊗√ (00i+11i). 0 1 2 The first two qubits belong to Alice, the third to Bob. Alice performs a CNOT on her two qubits and then a Hadamard transform on her first qubit. Their joint state can now be written as 1 00i(α 0i+α 1i) + 0 1 2 1 01i(α 1i+α 0i) + 0 1 2 1 10i(α 0i−α 1i) + 0 1 2 1 11i(α 1i−α 0i). 0 1 2 z z Alice Bob Alice then measures her two qubits in the computational basis and sends the result (2 random classical bits) to Bob over a classical channel. Bob now knows which transformation he must do on his qubit in order to regain the qubit α 0i +α 1i. For instance, if Alice sent 11 then Bob 0 1 knows that his qubit isα 1i−α 0i. A bitflip (X) followed by a phaseflip(Z) will give himAlice’s 0 1 original qubit α 0i+α 1i. In fact, if Alice’s qubit had been entangled with other qubits, then 0 1 teleportation preserves this entanglement: Bob then receives a qubit that is entangled in the same way as Alice’s original qubit was. Note that the qubit on Alice’s side has been destroyed: teleporting moves a qubit from A to B, rather than copying it. In fact, copying an unknown qubit is impossible 88, see Exercise 1. Exercises 1. Prove the quantum no-cloning theorem: there does not exist a 2-qubit unitary U that maps φi0i7→φiφi for every qubit φi. Hint: consider what U has to do when φi = 0i, when φi = 1i, and when φi is a superposition of these two. 2. Show that unitaries cannot “delete” information: there is no one-qubit unitary U that maps φi7→0i for every one-qubit state φi. 3. Compute the result of applying a Hadamard transform to both qubits of0i⊗1i in two ways (the first way using tensor product of vectors, the second using tensor product of matrices), and show that the two results are equal: H0i⊗H1i =(H⊗H)(0i⊗1i). 74. Show that a bit-flip operation, preceded and followed by Hadamard transforms, equals a phase-flip operation: HXH =Z. 1 √ 5. Prove that an EPR-pair (00i+11i) is an entangled state, i.e., that it cannot be written 2 as the tensor product of two separate qubits. 6. A matrix A is inner product-preserving if the inner product hAvAwi between Av and Aw equalstheinnerproducthvwi, forallvectorsv,w. Ais norm-preserving ifkAvk=kvkforall ∗ ∗ vectorsv, i.e.,ApreservestheEuclideanlengthofthevector. Aisunitary ifA A =AA =I. In the following, you may assume for simplicity that the entries of the vectors and matrices are real, not complex. (a) Prove that A is norm-preserving if, and only if, A is inner product-preserving. ∗ ∗ (b) Prove that A is inner product-preserving iff A A=AA =I. (c) Conclude that A is norm-preserving iff A is unitary. Bonus: prove the same for complex instead of real vector spaces. 7. Suppose Alice and Bob are not entangled. If Alice sends a qubit to Bob, then this can give 2 Bob at most one bit of information about Alice. However, if they share an EPR-pair, they cantransmit two classical bitsbysendingonequbitover thechannel; thisiscalled superdense coding 16. This exercise will show how this works. 1 √ (a) They start with a shared EPR-pair, (00i +11i). Alice has classical bits a and b. 2 Suppose she does an X-operation on her half of the EPR-pair if a = 1, and then a Z- operation ifb =1 (she does both ifab=11, and neither ifab=00). Write the resulting 2-qubit state. (b) Suppose Alice sends her half of the state to Bob, who now has two qubits. Show that Bob can determine both a and b from his state. Write Bob’s operation as a quantum circuit with Hadamard and CNOT gates. 2 Thisisactuallyadeepstatement,aspecialcaseofHolevo’s theorem. MoreaboutthismaybefoundinChapter10. 8Chapter 2 The Circuit Model and Deutsch-Jozsa 2.1 Quantum computation Below we explain how a quantum computer can apply computational steps to its register of qubits. Twomodelsexistforthis: thequantumTuringmachine33,18andthequantumcircuitmodel34, 89. These models are equivalent, in the sense that they can simulate each other in polynomial time, assuming the circuits are appropriately “uniform.” We only explain the circuit model here, which is more popular among researchers. 2.1.1 Classical circuits In classical complexity theory, a Boolean circuit is a finite directed acyclic graph with AND, OR, and NOT gates. It has n input nodes, which contain the n input bits (n ≥ 0). The internal nodes are AND, OR, and NOT gates, and there are one or more designated output nodes. The initial input bits are fed into AND, OR, and NOT gates according to the circuit, and eventually the output nodes assume some value. We say that a circuit computes some Boolean function n m n f :0,1 →0,1 if the output nodes get the right value f(x) for every inputx∈0,1 . A circuit family is a set C =C of circuits, one for each input size n. Each circuit has one n ∗ n output bit. Such a family recognizes or decides a language L⊆0,1 =∪ 0,1 if, for every n≥0 n n and every input x∈0,1 , the circuit C outputs 1 if x∈L and outputs 0 otherwise. Such a n circuit family is uniformly polynomial if there is a deterministic Turing machine that outputs C n given n as input, using space logarithmic in n (this implies time polynomial in n, because such a machine will have only poly(n) different internal states, so it either halts after poly(n) steps or cycles forever). Note that the size (number of gates) of the circuits C can then grow at most n polynomially with n. It is known that uniformly polynomial circuit families are equal in power to polynomial-time deterministic Turing machines: a language L can be decided by a uniformly polynomial circuit family iffL∈P 73, Theorem 11.5, whereP is the class of languages decidable by polynomial-time Turing machines. Similarly we can consider randomized circuits. These receive, in addition to the n input bits, also some random bits (“coin flips”) as input. A randomized circuit computes a function f if it successfullyoutputstherightanswerf(x)withprobabilityatleast2/3foreveryx(probabilitytaken over the values of the random bits; the 2/3 may be replaced by any 1/2+ε). Randomized circuits are equal in power to randomized Turing machines: a language L can be decided by a uniformly 9polynomial randomized circuit family iff L ∈ BPP, where BPP (“Bounded-error Probabilistic Polynomial time”) is the class of languages that can efficiently berecognized byrandomized Turing machines with success probability at least 2/3. 2.1.2 Quantum circuits A quantum circuit (also called quantum network or quantum gate array) generalizes the idea of classical circuit families, replacing the AND, OR, and NOT gates by elementary quantum gates. A quantum gate is a unitary transformation on a small (usually 1, 2, or 3) number of qubits. We saw a number of examples already in the last chapter: the bitflip gate X, the phaseflip gate Z, the Hadamard gate H. The main 2-qubit gate we have seen is the controlled-NOT (CNOT) gate. Adding another control register, we get the 3-qubit Toffoli gate, also called controlled-controlled- not (CCNOT) gate. This negates the third bit of its input if both of the first two bits are 1. The Toffoli gate is important because it is complete for classical reversible computation: any classical computation can be implemented by a circuit of Toffoli gates. This is easy to see: using auxiliary wireswithfixedvalues, Toffoli canimplementAND(fixthe3rdingoingwireto0)andNOT(fixthe 1st and2ndingoingwireto1). ItisknownthatAND andNOT-gates together sufficetoimplement any classical Boolean circuit, so if we can apply (or simulate) Toffoli gates, we can implement any classical computation in a reversible manner. Mathematically, such elementary gates can be composed by taking tensor products (if gates are applied in parallel to different parts of the register, and ordinary products (if gates are applied sequentially). We have already seen a simple example of such a circuit of elementary gates, namely to implement teleportation in the previous chapter. For example, if we apply the Hadamard gate H to each bit in a register of n zeroes, we obtain P 1 ⊗n √ ji, which is a superposition of all n-bit strings. More generally, if we applyH to n n j∈0,1 2 n an initial state ii, with i∈0,1 , we obtain X 1 ⊗n i·j H ii = √ (−1) ji, (2.1) n 2 n j∈0,1 P n n where i·j = i j denotes the inner product of the n-bit strings i,j ∈0,1 . For example: k k k=1 X 1 1 1 ⊗2 01·j H 01i = √ (0i+1i)⊗√ (0i−1i) = (−1) ji. 2 2 2 2 j∈0,1 Then-fold Hadamard transform will be very useful for all the quantum algorithms explained later. As in the classical case, a quantum circuit is a finite directed acyclic graph of input nodes, gates, and output nodes. There are n nodes that contain the input (as classical bits); in addition we may have some more input nodes that are initially 0i (“workspace”). The internal nodes of the quantum circuit are quantum gates that each operate on at most 2 qubits of the state. The gates in the circuit transform the initial state vector into a final state, which will generally be a superposition. We measure some dedicated output bits of this final state to (probabilistically) obtain an answer. In analogy to the classical class BPP, we will define BQP (“Bounded-error Quantum Poly- nomial time”) as the class of languages that can efficiently be computed with success probability at least 2/3 by (a family of) quantum circuits whose size grows at most polynomially with the input length. We will study this quantum complexity class and its relation with various classical complexity classes in more detail in Chapter 9. 102.2 Universality of various sets of elementary gates Which set of elementary gates should we allow? There are several reasonable choices. (1) The set of all 1-qubit operations together with the 2-qubit CNOT gate is universal, meaning that any other unitary transformation can be built from these gates. Allowing all 1-qubit gates is not very realistic from an implementational point of view, as there are uncountably many of them. However, the model is usually restricted, only allowing a small finite set of 1-qubit gates from which all other 1-qubit gates can be efficiently approximated. (2) The set consisting of CNOT, Hadamard, and the phase-gate R is universal in π/4 the sense of approximation, meaning that any other unitary can be arbitrarily well approximated using circuits of only these gates. The Solovay-Kitaev theorem says that thisapproximationisquiteefficient: wecanapproximateanygateon1or2qubitsupto error ε using polylog(1/ε) gates from our small set; in particular, simulating arbitrary gates up to exponentially small error costs only a polynomial overhead. It is often convenient to restrict to real numbers and use an even smaller set of gates: (3) The set of Hadamard and Toffoli (CCNOT) is universal for all unitaries with real entries in the sense of approximation, meaning that any unitary with only real entries canbearbitrarilywellapproximatedusingcircuitsofonlythesegates(againtheSolovay- Kitaev theorem says that this simulation can be done efficiently). 2.3 Quantum parallelism One uniquely quantum-mechanical effect that we can use for buildingquantum algorithms is quan- n tum parallelism. Suppose we have a classical algorithm that computes some functionf :0,1 → m 0,1 . Then we can build a quantum circuit U (consisting only of Toffoli gates) that maps n xi0i→xif(x)i foreveryx∈0,1 . Now supposeweapplyU toasuperpositionof all inputsx (which is easy to build usingn Hadamard transforms):   X X 1 1   √ √ U xi0i = xif(x)i. n n 2 2 n n x∈0,1 x∈0,1 n WeappliedU justonce,butthefinalsuperpositioncontainsf(x)forall 2 inputvaluesx However, byitself thisisnot veryusefulanddoesnotgive morethanclassical randomization, since observing the final superposition will give just one random xif(x)i and all other information will be lost. As we will see below, quantum parallelism needs to be combined with the effects of interference and entanglement in order to get something that is better than classical. 2.4 The early algorithms The two main successes of quantum algorithms so far are Shor’s factoring algorithm from 1994 81 and Grover’s search algorithm from 1996 47, which will be explained in later chapters. In this section we describe some of the earlier quantum algorithms that preceded Shor’s and Grover’s. 11Virtually all quantum algorithms work with queries in some form or other. We will explain this model here. It may look contrived at first, but eventually will lead smoothly to Shor’s and Grover’s algorithm. We should, however, emphasize that the query complexity model differs from the standard model described above, because the input is now given as a “black-box.” This means that the exponential quantum-classical separations that we describe below (like Simon’s) donot by themselves give exponential quantum-classical separations in the standard model. N To explain the query setting, consider an N-bit input x = (x ,...,x )∈0,1 . Usually we 1 N n will have N =2 , so that we can address bitx using ann-bit indexi. One can think of the input i as an N-bit memory which we can access at any point of our choice (a Random Access Memory). A memory access is via a so-called “black-box,” which is equipped to output the bit x on inputi. i As a quantum operation, this would be the following unitary mapping on n+1 qubits: O :i,0i→i,xi. x i The first n qubits of the state are called the address bits (or address register), while the (n+1)st qubit is called the target bit. Since this operation must be unitary, we also have to specify what happens if the initial value of the target bit is 1. Therefore we actually let O be the following x unitary transformation: O :i,bi→i,b⊕xi, x i n here i∈0,1 , b∈0,1, and⊕ denotes exclusive-or (addition modulo 2). In matrix representa- tion, O is now a permutation matrix and hence unitary. Note also that a quantum computer can x apply O on a superposition of various i, something a classical computer cannot do. One applica- x tion of this black-box is called a query, and counting the required number of queries to compute this or that function of x is something we will do a lot in the first half of these notes. Given the ability to make a query of the above type, we can also make a query of the form 1 x i √ ii→(−1) ii by setting the target bit to the state −i= (0i−1i) =H1i: 2 1 x i O (ii−i) =ii√ (xi−1−xi) =(−1) ii−i. x i i 2 This±-kindofqueryputstheoutputvariableinthephaseofthestate: ifx is1thenwegeta−1in i the phase of basis stateii; ifx =0 then nothing happenstoii. This “phase-oracle” is sometimes i more convenient than the standard type of query. We sometimes denote the correspondingn-qubit unitary transformation by O . x,± 2.4.1 Deutsch-Jozsa Deutsch-Jozsa problem 35: n N For N =2 , we are given x∈0,1 such that either (1) all x have the same value (“constant”), or i (2) N/2 of the x are 0 and N/2 are 1 (“balanced”). i The goal is to find out whetherx is constant or balanced. n The algorithm of Deutsch and Jozsa is as follows. We start in then-qubit zero state0 i, apply a Hadamard transform to each qubit, apply a query (in its ±-form), apply another Hadamard to each qubit, and then measure the final state. As a unitary transformation, the algorithm would 120i H H O measure 0i H x,± H 0i H H Figure 2.1: The Deutsch-Jozsa algorithm for n=3 ⊗n ⊗n be H O H . We have drawn the corresponding quantum circuit in Figure 2.1 (where time ± progresses from left to right). n Let us follow the state through these operations. Initially we have the state 0 i. By Equa- tion2.1onpage10,afterthefirstHadamardtransformswehaveobtainedtheuniformsuperposition of all i: X 1 √ ii. n 2 n i∈0,1 The O -query turns this into ± X 1 x i √ (−1) ii. n 2 n i∈0,1 Applying the second batch of Hadamards gives (again by Equation 2.1) the final superposition X X 1 x i·j i (−1) (−1) ji, n 2 n n i∈0,1 j∈0,1 P n n n where i·j = i j as before. Since i·0 = 0 for all i∈0,1 , we see that the amplitude of k k k=1 n the 0 i-state in the final superposition is  1 if x =0 for all i,  i X 1 x i (−1) = −1 if x =1 for all i, i n 2  n 0 if x is balanced. i∈0,1 n Hence the final observation will yield 0 i if x is constant and will yield some other state if x is balanced. Accordingly, the Deutsch-Jozsa problem can be solved with certainty using only 1 quantum query and O(n) other operations (the original solution of Deutsch and Jozsa used 2 queries, the 1-query solution is from 31). In contrast, it is easy to see that any classical deterministic algorithm needs at least N/2+1 queries: if it has made onlyN/2 queries and seen only 0s, the correct output is still undetermined. However, aclassicalalgorithmcansolvethisproblemefficientlyifweallowasmallerrorprobability: just queryx at two random positions, output “constant” if those bits are the same and “balanced” if they are different. This algorithm outputs the correct answer with probability 1 if x is constant and outputs the correct answer with probability 1/2 if x is balanced. Thus the quantum-classical separation of this problem only holds if we consider algorithms without error probability. 132.4.2 Bernstein-Vazirani Bernstein-Vazirani problem 18: n N n For N = 2 , we are given x∈0,1 with the property that there is some unknown a ∈0,1 such that x =(i·a) mod 2. The goal is to finda. i The Bernstein-Vazirani algorithm is exactly the same as the Deutsch-Jozsa algorithm, but now x (i·a) mod 2 i·a i the final observation miraculously yields a. Since (−1) = (−1) = (−1) , we can write the state obtained after the query as: X X 1 1 x i·a i √ (−1) ii = √ (−1) ii. n n 2 2 n n i∈0,1 i∈0,1 Applying a Hadamard to each qubit will turn this into the classical state ai and hence solves the problem with 1 query and O(n) other operations. In contrast, any classical algorithm (even a randomized one with small error probability) needs to ask n queries for information-theoretic reasons: thefinalanswerconsistsofnbitsandoneclassical querygivesatmost1bitofinformation. Bernstein and Vazirani also defined a recursive version of this problem, which can be solved exactly by a quantum algorithm inpoly(n) steps, but for which any classical randomized algorithm Ω(logn) needs n steps. Exercises −1 1. Is the controlled-NOT operation C Hermitian? Determine C . 2. Show that every unitary one-qubit gate with real entries can be written as a rotation matrix, possibly preceded and followed by Z-gates. In other words, show that for every 2×2 real unitary U, there exist signs s ,s ,s ∈1,−1 and angle θ∈0,2π) such that 1 2 3     1 0 cos(θ) −sin(θ) 1 0 U =s 1 0 s sin(θ) cos(θ) 0 s 2 3 3. Construct a CNOT from two Hadamard gates and one controlled-Z (the controlled-Z gate maps11i7→−11i and acts like the identity on the other basis states). 4. A SWAP-gate interchanges two qubits: it maps basis state a,bi to b,ai. Implement a SWAP-gate using a few CNOTs. 5. Let U be a 1-qubit unitary that we would like to implement in a controlled way, i.e., we c want to implement a map cibi 7→ciU bi for all c,b ∈0,1. Suppose there exist 1-qubit unitaries A, B, and C, such that ABC = I and AXBXC = U (remember that X is the NOT-gate). Give a circuit that acts on two qubits and implements a controlled-U gate, using CNOTs and (uncontrolled) A, B, and C gates. 6. It is possible to avoid doing any intermediate measurements in a quantum circuit, using one auxiliary qubit to delay a measurement till the end of the computation. Show how. Hint: instead of measuring the qubit, apply a CNOT that “copies” it to a new 0i-qubit, which is then left alone until the end of the computation. Analyze what happens. 14n n 7. (a) Give a circuit that maps 0 ,bi 7→ 0 ,1−bi for b ∈ 0,1, and that maps i,bi 7→ n n i,bi whenever i ∈0,1 \0 . You are allowed to use every type of elementary gate mentioned in the lecture notes (incl. Toffoli gates), as well as auxiliary qubits that are initially 0i and that should be put back to0i at the end of the computation. You can draw a Toffoli gate similar to a CNOT gate: a bold dot on each of the two control wires, and a ‘⊕’ on the target wire. N (b) Suppose we can make queries of the type i,bi 7→ i,b⊕xi to input x∈0,1 , with i n ′ ′ N =2 . Letx be the inputxwith its firstbit flipped(e.g., ifx=0110 thenx =1110). ′ Give a circuit that implements a query to x. Your circuit may use one query to x. ′′ (c) Give a circuit that implements a query to an input x that is obtained from x (analo- gously to (b)) by setting its first bit to 0. Your circuit may use one query to x. 8. In Section 2.4 we showed that a query of the typei,bi7→i,b⊕xi (wherei∈0,...,N−1 i x i andb∈0,1) can be used to implement a phase-query, i.e., one of the typeii7→(−1) ii. Is the converse possible: can a query of the first type be implemented using phase-queries, and possibly some ancilla qubits and other gates? If yes, show how. If no, explain why not. 9. Give a randomized classical algorithm (i.e., one that can flip coins during its operation) that makes only two queries tox, and decides the Deutsch-Jozsa problem with success probability at least 2/3 on every possible input. A high-level description is enough, no need to write out the classical circuit. 10. Suppose our N-bit input x satisfies the following promise: either (1) the firstN/2 bits ofx are all 0 andthe secondN/2 bits are all 1; or (2) the number of 1s in the first half of x plus the number of 0s in the second half, equals N/2. Modify the Deutsch-Jozsa algorithm to efficiently distinguish these two cases (1) and (2). N 11. Aparity query toinputx∈0,1 correspondstothe(N+1)-qubitunitarymapQ :y,bi7→ x P N−1 N y,b⊕(x·y)i, where x·y = xy mod 2. For any fixed function f :0,1 →0,1, i i i=0 give aquantumalgorithm that computesf(x)usingonlyone suchquery(i.e., one application of Q ), and as many elementary gates as you want. You don’t need to give the circuit in full x detail, an informal description of the algorithm is good enough. 15Chapter 3 Simon’s Algorithm The Deutsch-Jozsa problem showed an exponential quantum improvement over the best determin- istic classical algorithms; the Bernstein-Vazirani problem shows a polynomial improvement over the best randomized classical algorithms that have error probability≤1/3. In this chapter we will combine these two features: we will see a problem where quantum computers are exponentially more efficient than bounded-error randomized algorithms. 3.1 The problem n n LetN =2 , andN =1,...,N, which we can identify with0,1 . Letj⊕sbethen-bit string obtained by bitwise adding the n-bit strings j and s mod 2. Simon’s problem 82: n n ForN =2 , we are given x=(x ,...,x ), withx ∈0,1 , with the property that there is some 1 N i n unknown non-zero s∈0,1 such that x =x iff i=j⊕s. The goal is to finds. i j Note that x, viewed as a function from N to N is a 2-to-1 function, where the 2-to-1-ness is determined by the unknown mask s. The queries to the input here are slightly different from before: the inputx =(x ,...,x ) now has variables x that themselves are n-bit strings, and one 1 N i n query gives such a string completely (i,0 i7→i,xi). However, we can also view this problem as i n having n2 binary variables that we can query individually. Since we can simulate one x -query i using only n binary queries (just query all n bits of x ), this alternative view will not affect the i number of queries very much. 3.2 The quantum algorithm Simon’s algorithm starts out very similar to Deutsch-Jozsa: start in a state of 2n zero qubits n n 0 i0 i and apply Hadamard transforms to the firstn qubits, giving X 1 n √ ii0 i. n 2 n i∈0,1 16At this point, the second n-qubit register still holds only zeroes. A query turns this into X 1 √ iixi. i n 2 n i∈0,1 Now the algorithm measures the secondn-bit register (this measurement is actually not necessary, but it facilitates analysis). The measurement outcome will be some value x and the first register i will collapse to the superposition of the two indices having that x -value: i 1 √ (ii+i⊕si)xi. i 2 We will now ignore the second register and applyHadamard transformsto the firstnqubits. Using Equation 2.1 and the fact that (i⊕s)·j =(i·j)⊕(s·j), we can write the resulting state as   X X 1 i·j (i⊕s)·j   √ (−1) ji+ (−1) ji = n+1 2 n n j∈0,1 j∈0,1   X  1 i·j s·j   √ (−1) 1+(−1) ji . n+1 2 n j∈0,1 Note that ji has non-zero amplitude iff s·j = 0 mod 2. Measuring the state gives a uniformly randomelement fromthesetj s·j =0 mod 2. Accordingly, weget alinear equation that gives information about s. We repeat this algorithm until we have obtained n−1 independent linear n equations involving s. The solutions to these equations will be 0 and the correct s, which we can compute efficiently by a classical algorithm (Gaussian elimination modulo 2). This can be done by 3 means of a classical circuit of size roughly O(n ). k Note thatifthej’syouhave generated at somepointspanaspace ofsize2 , forsomekn−1, then the probability that your next run of the algorithm produces aj that is linearly independent n−1 k n−1 of the earlier ones, is (2 − 2 )/2 ≥ 1/2. Hence an expected number of O(n) runs of the algorithm suffices to find n−1 linearly independent j’s. Simon’s algorithm thus finds s using an expected number of O(n) x -queries and polynomially many other operations. i 3.3 Classical algorithms for Simon’s problem 3.3.1 Upper bound √ n Let us first sketch a classical randomized algorithm that solves Simon’s problem using O( 2 ) queries, based on the so-called “birthday paradox.” Our algorithm will make T randomly chosen distinct queries i ,...,i , for some T to be determined later. If there is a collision among those 1 T queries (i.e., x = x for some k 6= ℓ), then we are done, because then we know i = i ⊕s, i i k ℓ k ℓ equivalently s = i ⊕i . How large should T be such that we are likely to see a collision in case k ℓ  T n n 1 2 s = 6 0 ? (there won’t be any collisions if s = 0 .) There are = T(T −1)≈T /2 pairs in our 2 2 sequence that could be a collision, and since the indices are chosen randomly, the probability for a n fixed pair to form a collision is 1/(2 −1). Hence by linearity of expectation, the expected number √ 2 n+1 n+1 of collisions in our sequence will be roughly T /2 . If we choose T = 2 , we expect to have 17

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.