MIT OpenCourseWare http ocw mit edu 6 080 6 089 Great Ideas in Theoretical Computer Science Spring 2008 For information about citing these materials or our Terms of Use visit http ocw mit edu terms 6 080 6 089 GITCS May 13 2008 Lecture 24 Lecturer Scott Aaronson 1 Scribe Chris Granade Quantum Algorithms Of course the real question is can quantum computers actually do something more e ciently than classical computers In this lecture we ll see why the modern consensus is that they can 1 1 Computing the XOR of Two Bits We ll rst see an algorithm due to Deutsch and Jozsa Even though this algorithm is trivial by modern standards it gave the rst example where a quantum algorithm could provably solve a problem using fewer resources than a classical algorithm Suppose we re given access to a Boolean function f 0 1 0 1 And suupose we want to compute f 0 f 1 the XOR of f 0 and f 1 Classically how many times would we need to evaluate f It s clear that the answer is twice knowing only f 0 or f 1 tells us exactly nothing about their XOR So what about in the quantum case Well rst we need to say what it even means to evaluate f Since this is a quantum algorithm we re talking about we should be able to evaluate both inputs f 0 and f 1 in quantum superposition But we have to do so in a reversible way For example we can t map the state x b to x f x overwriting b since that wouldn t be unitary The standard solution is that querying f means applying a unitary transformation that maps x y x y f x Is it reversible Yeah Applying it twice gets you back to where you started I claim we can compute f 0 f 1 using just a single one of these operations How 0 H H Uf 0 X H Figure 1 Finding f 0 f 1 in one query In the circuit above the e ect of the gates before Uf is to prepare an initial state 0 0 1 0 1 0 1 2 If you think of the e ect of Uf on the rst qubit in this state it s just to negate the amplitude if f 1 Thus Uf produces if f 0 f 1 and otherwise The nal Hadamard f 0 gate transforms the rst qubit back into the computational basis so that we measure 1 if and only if f 0 f 1 In particular this means that if you want to compute the XOR of N bits with a quantum computer you can do so using N 2 queries as follows rst divide the bits into N 2 pairs of bits 24 1 then run the above algorithm on each pair and nally output the XOR of the results Of course this is only a constant factor speedup but it s a harbinger of much more impressive speedups to come 1 2 Simon s Algorithm Say you re given a Boolean function f 0 1 n 0 1 n You re promised there exists a secret string s such that f x f y if and only if y x s where denotes a sum mod 2 The problem is to nd s by querying f as few times as possible How many queries would a classical randomized algorithm need to solve this problem Some thing very similar was on your problem set Right 2n 2 This is basically just the birthday paradox Until it happens to nd an x y pair such that f x f y your algorithm is basically just shoot ing in the dark it has essentially no information about s And after T queries the probability of having found an x y pair such that f x f y is at most T 2 2n 1 why On the other hand in 1993 Daniel Simon gave a quantum algorithm that solves this problem in polynomial time in fact using only O n queries This was the rst example of a problem that a quantum computer can solve exponentially faster than a classical one Admittedly it s a contrived example and probably for that reason Simon s paper was originally rejected But it s good to see for two reasons rst it led directly to Shor s factoring algorithm And second the easiest way to understand Shor s algorithm is to understand Simon s algorithm and then see Shor s algorithm as the same thing with a di erent underlying group Before proceeding further though there s one thing I want to clear up I said that Simon s problem was the rst known example where quantum computers provably give an exponential speedup over classical computers How is that consistent with what I said before that we can t prove P BQP unconditionally Right Simon s problem involves the function f as a black box In the black box setting we can prove unconditionally that quantum computers give an exponential speedup over classical ones 1 3 RSA Alright so let s say you want to break the RSA cryptosystem in order to rob some banks read your ex s email whatever We all know that breaking RSA reduces to nding the prime factors of a large integer N Unfortunately we also know that trying all possible divisors in parallel and then instantly picking the right one isn t going to work Hundreds of popular magazine articles notwithstanding trying everything in parallel just isn t the sort of thing that a quantum computer can do Sure in some sense you can try all possible divisors but if you then measure the outcome you ll get a random potential divisor which almost certainly won t be the one you want What this means is that if we want a fast quantum factoring algorithm we re going to have to exploit some structure in the factoring problem in other words some mathematical property of factoring that it doesn t share with just a generic problem of nding a needle in a haystack Fortunately the factoring problem has oodles of special properties What are some examples we discussed in class Right if I give you a positive integer you might not know its prime factorization but you do know that it has exactly one factorization By contrast if I gave you say a Sudoku puzzle and asked you to solve it a priori you d have no way of knowing whether it had exactly one solution 200 million solutions or no solutions at all Of course knowing that there s exactly one needle in a haystack is still not much help in nding the needle But this uniqueness is a hint that 24 2 the factoring problem might have other nice mathematical properties lying around for the picking As it turns out it does The property we ll exploit is the reducibility of factoring to another problem called period nding OK time for a brief number theory digression Let s look at the powers of 2 …