5. (16 pts) In the previous homework, we looked at a quantum algorithm for performing a Fourier transform, which is a part of Shor's algorithm for factoring numbers. Now we will look at another quantum algorithm, Grover's algorithm, which is for searching the space of solutions to a problem. This is particularly useful for solving problems where it is hard to find the solution(s), but easy to check if a given solution is correct. An example of such a problem is finding whether a graph has a Hamiltonian path. A graph (in this context) is a series of vertices (points) connected in some way by edges (lines). A Hamiltonian path is a path along the edges that visits all the vertices exactly once without repeating. Given a path, it is easy to check if it is a Hamiltonian path. But if the graph is very big, it is generally hard to find such a path. If there are Ne edges, then the number of paths is on the order of Ne! Classically, the best way to solve this problem is to start trying all Ne! possibilities and checking them. To solve this problem on a quantum computer, assume we have some way of encoding a given path by a number n. We can then use the basis states (n) of NA qubits to represent each possible path. (As before with Shor's algorithm, In) represents a state like 101101 ...0001), which is the tensor product of some combination of the individual qubits' basis states, and the number n is the binary number that appears in the ket.) We then want to come up with an operator that performs the action of checking whether that path is a Hamiltonian path (HP). Since this is straightforward to do on a regular computer, it can also be done on a quantum computer. On a regular computer we could write an efficient function f(n) = {-1 n is an HP n is not an HP. So in the quantum computer we can find an operator such that In) = f(n)|n). Now on to the algorithm. The first step is to initialize the qubits into the state In = 0) = 10000 ...00). Next we apply a Hadamard gate to all the qubits, as we did in the last homework as well. As you found last week, the resulting state is N-1 1 (a) = In). VN n=0 Note that here N = 2N is the number of basis states. If you like, you can think of |a) as representing all possible paths across the graph. Next, we apply a series of four operations: (1) We apply the operator 0. (2) Apply another Hadamard to every qubit. (3) Flip the sign of every coefficient except that of n = 0). (Or equivalently, shift the phase of those basis states by ). (4) Again apply a Hadamard to every qubit. Time for you to do something. a. Consider a general state of the qubits cnin). Show that step (3) above can be accomplished with the following operator: 20/0 -1, where 10) = (n = 0) = 1000...0), and I is the identity operator (In) = )). b. Considering just a single qubit, what is the effect of applying a Hadamard, the identity, and another Hadamard? Given what we now know, it may not be surprising that steps (2)-(4) can be represented as 2 a/al-1. c. Again consider a general states) = CnIn). Show that (2a)(a|-1|s) = -2 (20 - Cn)n), n where c = En Cn/N is the mean of the Cro So now steps (1)-(4) are all given by the operator G = (2|a)(al-1)0. The computation is then carried out by applying repeatedly. d. Consider a graph that just has one Hamiltonian path Ino). If the qubits are in the state (a) and you measure o, on all the qubits, what is the probability P, that the resulting state is (no)? e. Now consider the first iteration of Grover's algorithm: S1) = Ecn|n) = [a). Find the coefficients Cn. Verify that they are normalized. Now what is probability Po of the measurement resulting in the state (no)? (Keep terms in po only to lowest order in (1).) f. Repeat part e for the second iteration |s2) = cn|n) = 2|a). You should have found that po is increasing with each iteration, though if N is large, then po is still small after 2 iterations. The goal is to get the correct answer (no) with some reasonably high probability. You should be able to guess from the pattern in your answers to d-f that it will take about VN iterations for po to be on the order of 1. This is significantly better than the classical approach of trying all N paths sequentially. (That would be N iterations.) However, if N is really large, VN may still be pretty big, so the quantum advantage is not as much as it is for Shor's algorithm. 5. (16 pts) In the previous homework, we looked at a quantum algorithm for performing a Fourier transform, which is a part of Shor's algorithm for factoring numbers. Now we will look at another quantum algorithm, Grover's algorithm, which is for searching the space of solutions to a problem. This is particularly useful for solving problems where it is hard to find the solution(s), but easy to check if a given solution is correct. An example of such a problem is finding whether a graph has a Hamiltonian path. A graph (in this context) is a series of vertices (points) connected in some way by edges (lines). A Hamiltonian path is a path along the edges that visits all the vertices exactly once without repeating. Given a path, it is easy to check if it is a Hamiltonian path. But if the graph is very big, it is generally hard to find such a path. If there are Ne edges, then the number of paths is on the order of Ne! Classically, the best way to solve this problem is to start trying all Ne! possibilities and checking them. To solve this problem on a quantum computer, assume we have some way of encoding a given path by a number n. We can then use the basis states (n) of NA qubits to represent each possible path. (As before with Shor's algorithm, In) represents a state like 101101 ...0001), which is the tensor product of some combination of the individual qubits' basis states, and the number n is the binary number that appears in the ket.) We then want to come up with an operator that performs the action of checking whether that path is a Hamiltonian path (HP). Since this is straightforward to do on a regular computer, it can also be done on a quantum computer. On a regular computer we could write an efficient function f(n) = {-1 n is an HP n is not an HP. So in the quantum computer we can find an operator such that In) = f(n)|n). Now on to the algorithm. The first step is to initialize the qubits into the state In = 0) = 10000 ...00). Next we apply a Hadamard gate to all the qubits, as we did in the last homework as well. As you found last week, the resulting state is N-1 1 (a) = In). VN n=0 Note that here N = 2N is the number of basis states. If you like, you can think of |a) as representing all possible paths across the graph. Next, we apply a series of four operations: (1) We apply the operator 0. (2) Apply another Hadamard to every qubit. (3) Flip the sign of every coefficient except that of n = 0). (Or equivalently, shift the phase of those basis states by ). (4) Again apply a Hadamard to every qubit. Time for you to do something. a. Consider a general state of the qubits cnin). Show that step (3) above can be accomplished with the following operator: 20/0 -1, where 10) = (n = 0) = 1000...0), and I is the identity operator (In) = )). b. Considering just a single qubit, what is the effect of applying a Hadamard, the identity, and another Hadamard? Given what we now know, it may not be surprising that steps (2)-(4) can be represented as 2 a/al-1. c. Again consider a general states) = CnIn). Show that (2a)(a|-1|s) = -2 (20 - Cn)n), n where c = En Cn/N is the mean of the Cro So now steps (1)-(4) are all given by the operator G = (2|a)(al-1)0. The computation is then carried out by applying repeatedly. d. Consider a graph that just has one Hamiltonian path Ino). If the qubits are in the state (a) and you measure o, on all the qubits, what is the probability P, that the resulting state is (no)? e. Now consider the first iteration of Grover's algorithm: S1) = Ecn|n) = [a). Find the coefficients Cn. Verify that they are normalized. Now what is probability Po of the measurement resulting in the state (no)? (Keep terms in po only to lowest order in (1).) f. Repeat part e for the second iteration |s2) = cn|n) = 2|a). You should have found that po is increasing with each iteration, though if N is large, then po is still small after 2 iterations. The goal is to get the correct answer (no) with some reasonably high probability. You should be able to guess from the pattern in your answers to d-f that it will take about VN iterations for po to be on the order of 1. This is significantly better than the classical approach of trying all N paths sequentially. (That would be N iterations.) However, if N is really large, VN may still be pretty big, so the quantum advantage is not as much as it is for Shor's algorithm