Chapter 5: Quantum Computing

8.06 Spring 2015 Lecture Notes 5. Quantum Computing Aram Harrow Last updated: May 23, 2016 Quantum computing uses familiar principles of quantum mechanics, but with a different philosophy. The key differences are • It looks at the information carried by quantum systems, and methods of manipulating it, in ways that are independent of the underlying physical realization (i.e. spins, photons, superconductors, etc.) • Instead of attempting to describe the world around us, it asks what we can create. As a result, features of quantum mechanics that appear to be limitations, such as Heisenberg’s uncertainty principle, can be turned into new capabilities, such as secure quantum key distribution. The approach is of course analogous to classical computing, where the principles of computing are the same whether your information is stored in magnetic spins (e.g. a hard drive) or electric circuits (e.g. RAM). After the modern notion of a computer was invented in the 1930s by Alan Turing, Alonzo Church, and others, many believed that all computing models (ranging from modern CPUs to DNA computers to clerks working with pencil and paper) were fundamentally equivalent. Specifically, the Strong Church-Turing thesis held that any reasonable computing model could simulate any other with modest overhead. Relativity turns out to still be compatible with this hypothesis, but as we will see, quantum mechanics is not. 1 Classical computing Model a classical computer by a collection of m bits x1 , . . . , xm upon which we perform gates, each acting on O(1) bits. For example, the NOT gate acts on a single bit, maps 0 to 1, and 1 to 0. The NAND gate means “not-AND” is defined by x y x NAND y 0 0 1 0 1 1 1 0 1 1 1 0 The NAND gate is useful because it is computationally universal. Using only NAND gates, we can construct any function on n-bit strings. Here, we can imagine the output of a gate overwriting an existing bit, but it is often simpler to work with reversible computers. The NOT gate is reversible. Another example of a reversible gate is the controlled-NOT or CNOT, which maps a pair of bits (x, y) to (x, x ⊕ y). Here ⊕ denotes addition modulo 2. 1 x y x⊕y 0 0 0 0 1 1 1 0 1 1 1 0 For reversible circuits, computational universality means the ability to implement any invertible function from {0, 1}n (the set of n-bit strings) to {0, 1}n . It turns out that NOT and CNOT gates alone are not computationally universal (proving this is a nice exercise; as a hint, they generate only transformations that are linear mod 2). For computational universality in reversible circuits, we need some 3-bit gate. One convenient one is the Toffoli gate (named after its inventor, Tom Toffoli), which maps (x, y, z) to (x, y, z⊕xy). If we start with (x, y, 1), then applying the Toffoli gate yields (x, y, x NAND y). Since the Toffoli gate can simulate the NAND gate, it is computationally universal. There are not significant differences between the reversible and irreversible models, but the reversible one will be a more convenient way to discuss quantum computing. 1.1 Complexity The complexity of a function is the minimum number of gates required to implement it. Since the exact number of gates is not very illuminating, and will in general depend on the details of the computational model, we often care instead about how the complexity scales with the input size n. For example, the time to multiply two n-bit numbers using the straightforward method requires time O(n2 ), since this is the number of pairs of bits that have to be considered. The true complexity is lower, since a more clever algorithm is known to multiply numbers in time O(n log(n)). Factoring integers, on the other hand, is not something we know how to do quickly. The naive algorithm √ to factor an n-bit number x requires checking all primes ≤ x, which requires checking ≈ 2n/2 /n numbers. A much more complicated algorithm is known (the number field sieve) which requires 1/3 time O(2n ), and modern cryptosystems are based on the assumption that nothing substantially faster is possible. In general, we say that a problem can be solved efficiently if we can solve in time polynomial in the input size n, i.e. in time ≤ nc for some constant c > 0. So multiplication can be solved efficiently, as well as many other problems, like inverting a matrix, minimizing a convex function, finding the shortest path in a graph, etc. On the other hand, many problems besides factoring are also not known to have any fast algorithms, of which one example is the “taxicab-ripoff problem”, namely finding the longest path in a graph without repeating any vertex. The strong Church-Turing essentially states that modern computers (optionally equipped with true random number generators) can simulate any other model of computation with polynomial overhead. In other words “polynomial-time” means the same on any platform. 1.2 The complexity of quantum mechanics Feynman observed in 1982 that quantum mechanics appeared to violate the strong Church-Turing n thesis. Consider the state of n spin-1/2 particles. This state is a unit vector in (C2 )⊗n = C2 , so to describe it requires 2n complex numbers. Similarly solving the Schrödinger equation on this system appears to require time exponential in n on a classical computer. 2 Already this suggests that the classical model of computing does not capture everything in the world. But Feynman then asked whether in this case a hypothetic quantum computer might be able to do better. On pset 10, you will have the option of exploring a technique by which quantum computers can simulate general quantum systems with overhead that is polynomial in the space and time of the region being simulated. 2 2.1 Quantum computers Qubits and gates A quantum computer can be thought of as n spin-1/2 particles whose Hamiltonian is under our control. A single spin-1/2 particle is called a qubit and we write its state as a0 |0i + a1 |1i (think of |0i = | ↑i and |1i = | ↓i if you like, but |0i = |groundi, |1i = |first excitedi works equally well). The state of two qubits can be written as a00 |00i + a01 |01i + a10 |10i + a11 |11i, where we use |x1 x2 i as a shorthand for |x1 i ⊗ |x2 i. And the state of n qubits can be written as X |ψi = a~x |~xi. ~ x∈{0,1}n The power of quantum computing comes from the fact that acting on one or two qubits is equivalent to applying a 2n × 2n matrix to the state |ψi. Let’s see concretely how this works. If we have a single qubit and can apply any H we like for any time t, we can generate any −iHt . (Use units where ~ = 1.) This is because any unitary matrix U can be unitary matrix U = eP P diagonalized as U = 2j=1 eiθj |vj ihvj |, and so applying the Hamiltonian j −θj |vj ihvj | for time 1 will yield U . What if we have two qubits? If we apply H to the first qubit then this is equivalent to the two-qubit Hamiltonian H ⊗ I2 . The resulting unitary is V = e−i(H⊗I) = e−iH ⊗ I = U ⊗ I. Similarly if we apply H to the second qubit, then this corresponds to the two-qubit Hamiltonian I ⊗ H, which generates the unitary operation I ⊗ U . If we instead apply a two-qubit Hamiltonian, then we can generate any two-qubit (i.e. 4 × 4) unitary. This does not scale up to general n-qubit unitaries. Instead we perform these by stringing together sequences of one and two-qubit gates. Some important one-qubit gates (each of which is 3 both Hermitian and unitary, meaning their eigenvalues are 1, −1) are   0 1  X = σx =  1 0   0 −i  Y = σy =  i 0   1 0  Z = σz =  0 −1   X 1 1 1  = √1 H=√  (−1)xy |xihy| 2 1 −1 2 x,y∈{0,1} The last gate H is known as the Hadamard transform and plays an important role in quantum computing. It has the useful properties that HXH = Z and HZH = X. An important two-qubit is the controlled-NOT gate, which is discussed further on pset 10. How do these look when acting on n qubits? If we apply a one-qubit (2 × 2) gate U to the j th qubit, this results in the unitary I2⊗j−1 ⊗ U ⊗ I2⊗n−j . If we apply a two-qubit gate V to qubits j, j + 1, then we have the unitary I2⊗j−1 ⊗ V ⊗ I2⊗n−j−1 . There is no reason two-qubit gates cannot be applied to non-consecutive qubits, but it requires more notation, so we will avoid this. One fact we will use later is that X X X 1 1 1 (−1)x1 y1 |y1 ihx1 | ⊗ √ (−1)x2 y2 |y2 ihx2 | ⊗ · · · ⊗ √ (−1)xn yn |yn ihxn | H ⊗n = √ 2 x ,y ∈{0,1} 2 x ,y ∈{0,1} 2 x ,y ∈{0,1} n n 1 1 2 2 X 1 =√ (−1)x1 y1 +...+xn yn |~y ih~x| 2n ~x,~y∈{0,1}n X 1 =√ (−1)~x·~y |~y ih~x| 2n ~x,~y∈{0,1}n 2.2 Quantum computing is at least as strong as classical computing I claim that one and two-qubit gates can implement the quantum Toffoli gate. There is a construction with 6 CNOT gates and many single-qubit gates which I will not describe here. This means that given the ability to do arbitrary one- and two-qubit gates, a quantum computer can perform any classical reversible computation with asymptotically constant overhead. This is good to know, but it is in going beyond classical computing that quantum computers become interesting. On the other hand, we may often want to use classical algorithms as a subroutine. If f : {0, 1}n → {0, 1}n is a reversible (i.e. invertible) function, then the corresponding unitary is X U= |f (~x)ih~x|. ~ x∈{0,1}n 4 3 Grover’s algorithm Grover’s algorithm shows a quantum speedup for the simple problem of unstructured search. Suppose that f is a function from {0, . . . , N − 1} → {0, 1} and our goal is to find some x for which f (x) = 1. How many times do we need to evaluate f to find such an x? For simplicity, assume that there is a single w for which f (w) = 1. (w stands for “winner.”) Evaluating f (x) for random x will find w in an expected N/2 steps. √Remarkably, quantum computers can improve this by a quadratic factor, and can find w using O( N ) steps. The algorithm has two ingredients. First, we need to be able to implement the unitary X A= (−1)f (x) |xihx| = I − 2|wihw|. 0≤x x then ay−x ≡ 1 mod N . (This is not obvious but can be proved using tools like the Chinese Remainder Theorem.) Now suppose we have found r = ord(a). This means that ar − 1 = mN for some integer m. Suppose that • r is even, and • ar/2 + 1 is not a multiple of N . (If either of these fails, try another a. It turns out there is a reasonable probability that one of these holds.) Suppose even more concretely that N = pk11 . . . pkl l . Then (ar/2 − 1)(ar/2 + 1) = mpk11 . . . plkl (1) and since ar/2 + 1 is not a multiple of N there must be some pj that divides ar/2 − 1. We can now compute gcd(ar/2 − 1, N ) using Euclid’s algorithm and we will find a nontrivial factor of N . That’s it for the number theory. Now how do we find ord(a)? We use period finding! Define f (x) = ax mod N. 7 (2) This has period r. Indeed f (x + r) = ax+r mod N = ax ar mod N = ax mod N = f (x). (3) The intuition behind period finding is similar to what we did for Simon’s algorithm, although now the Fourier transform is instead more like the traditional (i.e. U (1)) Fourier transform. Here’s how this works. Choose n such that N 2 ≤ 2n < 2N 2 . We will evaluate f (x) on x ∈ {0, 1, . . . , 2n −1}. Before describing Shor’s algorithm we present a subroutine, the Quantum Fourier Transform. n 2 −1 1 X 2πixy/2n UQFT |xi = √ e |y i. 2n y=0 (4) This is a unitary transformation and I claim it can be performed using O(n2 ) gates. Let’s see how we use it first and then show how to perform it next. The quantum part of Shor’s algorithm consists of these steps: P n −1 |xi ⊗ |0i. • Prepare the state √12n 2x=0 • Calculate f (x) in the second register to obtain n 2 −1 1 X √ |xi ⊗ |f (x)i. 2n x=0 • Discard the second register. (But we just calculated it!) We can think of this as measuring the register and ignoring the answer. The first register will be in a superposition of the form C(|x0 i + |x0 + ri + |x0 + 2ri + . . .). for a random choice of x0 . Let’s make this more precise and say the state is m−1 1 X √ |x0 + k ri, m (5) k=0 with m ≈ 2n /r. At this point our superposition has period r. Think of this as a state with period r in time. If we Fourier transform we should get a peak in frequency proportional to 1/r (in fact 2n /r for our discretized Fourier transform). Let’s now do the math and see that this happens. • Apply UQFT . This yields n m −1 2X −1 X 1 n n √ e2πix0 y/2 e2πikr/2 |yi. n m2 k=0 y=0 (6) • Measure y. We find m−1 1 X 2πikry Pr[y] = e 2n m2n k=0 8 2 . (7) To get some intuition for (7), suppose y ≈ 2n j/r for some integer j. Then the phase will b ≈ 1 and we will get Pr[y] ≈ m/2n = 1/r. Let’s argue this more precisely. Observe that Pem−1 k m n k=0 z = (1 − z )/(1 − z). Consider y = 2 j/r + δj for |δj | ≤ 1/2. Then  2  2   2πimrδj 2πimry 1 − exp 1 − exp n n 2 2 1 1    =  Pr[y] = (8) n n 2πirδ j m2 m2 1 − exp 2πiry 1 − exp n n 2 2 Using mr ≈ 2n and |1 − eiθ | = 2 sin(θ/2) we have Pr[y] ≈ sin2 (πδj ) 1 1 (πδj /(π/2))2 4 1 ≥ = 2 . 2 n n 2 m2 sin (πδj /m) m2 (πδj /m) π r (9) Therefore with probability ≥ 4/π 2 we obtain j2n /r from which we can extract r. • Extract r using more number theory. This part is a classical computation so I will not dwell on δ it. From the last step we obtain 2yn = rj + 2nj for an unknown integer j and unknown |δj | ≤ 1/2. Since r < N and N 2 ≤ 2n , finding the best rational approximation with denominator ≤ N will do the job. This “best rational approximation” can be found by something called the continued fraction expansion, which we illustrate with an example. 49 1 1 1 1 = 300 = 6 = 1 = 1 300 6 + 6 + 6 + 49 49 49 8+ 1 6 6 Rational approximations are obtained by truncating this series, e.g. 1/(6 + 1/8) = 8/49 ≈ 49/300. For the last twenty years there have been many attempts to generalize Shor’s algorithm to other groups. In some cases these would break other cryptosystems. It is often possible to find efficient quantum Fourier transforms for other groups but finding analogues of the continued fraction expansion and the other ingredients has been elusive. (n) Finally let’s talk about how to implement UQFT . The superscript denotes the number of qubits. When n = 1 this is just our old friend the Hadamard transform.   1 1 1 (1)  UQFT = √  2 1 −1 When n = 2 we get fourth roots of unity, namely  1   1 1  (2)  UQFT = √  4 1  1 (n) ±i in addition to ±1:  1 1 1   i −1 −i    −1 1 −1  −i −1 i In general the matrix elements of UQFT look like exp(2πixy/2n ). Let’s see how this looks in terms fo the bits of x and y. Write x = x0 + 2x1 + 4x2 + . . . + 2n−1 xn−1 and similarly y = y0 + . . . + 2n−1 yn−1 . Then xy mod 2n = x0 y0 + 2(x1 y0 + x0 y1 ) + . . . + 2n−1 (x0 yn−1 + . . . + xn−1 y0 ). 9 xn−1 xn−2 xn−3 .. . x0 H y0 R2 R3 ... y0 Rn−1 y1 • • (n−1) UQFT • y2 .. . yn−1 Figure 1: Quantum circuit implementing the quantum Fourier transform. Write x = 2n−1 xn−1 + x̄ and y = 2ȳ + y0 . Then 2πi2n−1 xn−1 2ȳ 2πix̄2ȳ 1 2πixy 1 2πi2n−1nxn−1 y0 2πix̄y (−1)xn−1 y0 2πix̄y 0 0 (n−1) 2 2n 2n √ e 2n = √ e √ e 2n e| e = e 2n hȳ|UQFT |x̄i. {z } n n 2 2 2 1 (n) This suggests a recursive algorithm for UQFT which we express as a circuit diagram. See Fig. 1. There we have defined the rotation gate   1 0 . Rk ≡  (10) k 0 e2πi/2 10