Applications of Grover’s Search Algorithm

Lecture 11: Applications of Grover’s Search Algorithm Scribed by: Yuan­Chung Cheng Department of Chemistry, MIT October 9, 2003 In this lecture we will cover several applications of Grover’s search algorithm, and show that Grover’s search algorithm is optimal. Grover’s search algorithm: ∃ function O such that O|x� = −|x� O|x� = |x� if x ∈ T, otherwise. We�want to find elements in the target set T. If there are N |x�’s and M targets, after N c· M iterations of G, most amplitude will be in the target set. The following operator G is performed in each iteration: G = H⊗n (2|0��0| − I)H⊗n · O, � and the initial state is prepared in √12n x |x�. In addition to perform the search of a target in a set of elements, the Grover’s search algorithm has other possible applications. Here we will demonstrate how to use Grover’s search algorithm to speed up classical algorithms, and do target counting. Speed up classical algorithms NP problems are those for which a solution is easy to check, but not necessarily easy to find. Examples of NP problems are: � � n distances between them, we want Travel Salesman Problem (TSP): Having n cities and 2 to find a tour of the cities of length at most D. 3­SAT: Given a boolean formula of totally n variables in conjunctive normal form with at most 3 variables in each clause, ex. (x1 ∨ x3 ∨ x7 ) ∧ (x1 ∨ x¯5 ∨ x9 ) ∧ (x2 ∨ x¯3 ∨ x11 ) . . ., we want to know if there exist a set of {xi , i = 1 . . . n} such that the whole formula is satisfied. 1 P. Shor – 18.435/2.111 Quantum Computation – Lecture 11 2 Using the 3­SAT problem as an example, classically we have to search exhaustively and try every set of values, therefor the algorithm takes 2n time. Here we will show that the problem can be done using the Grover’s search algorithm in 2n/2 time. A better way to start is to find a maximal set of disjoint clauses in the formula. We can rename the variables and write the formula as (x1 ∨ x2 ∨ x3 ) ∧ (x4 ∨ x5 ∨ x6 ) ∧ . . . ∧ (xm−2 ∨ xm−1 ∨ xm ) ∧ . . . (xi ∨ xn−1 ∨ xn ), where 1 < m < n, and 1 < i < m. In this form, we have a disjoint clauses set (from x1 to xm ), and the rest of the formula are 2­SAT. Since we know polynomial time algorithm for 2­SAT problems, we can easily solve the left­over part. Notice that we need to try only 7 values for each clause,and there are at most n3 clauses. The time is 7n/3 ≈ 2.93n . If we apply Grover’s search algorithm, we can do with time in O(2.93n/2 ). This is almost close to the best classical algorithm O(2.43n ). This demonstrates that applying Grover’s algorithm to a relatively simple classical algorithm can gain substantial speed up (however, not exponential speed up). It is possible that the Grover’s algorithm and be used on best classical algorithm can gain speed up that can not be done classically. Approximate counting: How many solutions are there? Grover’s algorithm can be combined with the quantum phase estimation algorithm to approximately count the number of targets in the set, i.e. the value of M . Classically, suppose you need to�sample A values to get M ± εM . The expected number in target set is A· M N , standard deviation is The estimate of M , Mest , is the number of targets you found times N/A. Mest = = A· M N. N f ound A · number� N M AM ±N A A N� A N = M ± NAM � � � N = M 1 ± AM Therefore, M (1 + ε) = M (1 ± � N AM ). To get M within ±ε range, we need to sample A times, N . M ε2 where A ≈ The efficient of the estimation is ∼ 1/ε2 . We can use Grover’s algorithm to improve the performance. Recall that in the Grover’s search algorithm, if we define � |α� = √N1−M |x� |β� = √1 M / �x∈T |x�, x∈T what Grover’s algorithm does in each iteration is �to rotate the state vector in the |α�, |β� basis θ counter­clockwise for θ angle, where 2 = arcsin( M N ). In the |α�, |β� basis, we can write the G operator as a rotation matrix (for N � M ): � � cos θ − sin θ . G= sin θ cos θ P. Shor – 18.435/2.111 Quantum Computation – Lecture 11 3 Figure 1: Circuit for quantum counting. The eigenvalues of the matrix are e±iθ . Therefore, we can use phase estimation algorithm to obtain the phase factor θ, and compute the number of targets in the set. Figure 1. shows the circuit for approximate quantum counting to t qubits accuracy on a quantum computer. We now analyze the efficiency of the quantum counting algorithm. Suppose we get θ to t bits accuracy, i.e. θest = θ ± 21t . We need 2t calls to the function. By the definition of θ, we have M θ = . 2 N To estimate the error, we take the derivative on both side to obtain the relationship between the change of θ, δθ, and the change of M , δM : sin2 2 sin θ θ δM cos · δθ = . N 2 2 Using N � M, and θ � 1, we obtain √ M θ cos ≤ 2δθ M N . N 2 � √ We define εM = δM ≈ 2δθ M N , so δθ = M · 2 . Therefore, in terms of ε, the number of calls � N ε 2 needed to get to the accuracy of ε is ∼ M N · ε . This is the square­root of what we need in the classical algorithm. � δM = 2N δθ Grover’s search algorithm is optimal Suppose we have a new quantum algorithm that can find state |x�. We define Ox as the oracle of finding state |x�: � |x� → −|x� Ox = |y� → |y� if y �= x Let |ψ� be the starting state of the algorithm. One can write any algorithm of finding state |x� as P. Shor – 18.435/2.111 Quantum Computation – Lecture 11 √ 1 − ε|x� + √ 4 ε|g� ≈ Un Ox . . . U3 Ox U2 Ox U1 Ox |ψ�, where |g� is composed of states ⊥ to |x�. For a successful algorithm, the outcome of the operations should be very close to the target state, that is, ε has to be very small. Let’s also define |ψkx � = Uk Ox Uk−1 Ox . . . U1 Ox |ψ�, |ψk � = Uk Uk−1 . . . U1 |ψ�. Notice that |ψkx � and |ψk � differ by the oracle operator Ox that separates the target state from other states. From this, we can define the Euclidean distance between these two states after k operations: Dk = � �|ψkx � − |ψk ��2 . (1) x This distance can serve as a measurement of how much this algorithm can made to distinguish 2 |x� and |y� states. We will show that D√ k ≤ O(k ). To solve Grover’s problem, one needs at least Dleast ≈ O(N ). Therefore, at least k ∼ N is necessary, which is what Grover’s search algorithm does. Consider the Euclidean distance of the k + 1 states: � Dk+1 = �Uk+1 Ox |ψkx � − Uk+1 |ψk ��2 x � = �Ox |ψkx � − |ψk ��2 x � = �Ox (|ψkx � − |ψk �) + (Ox − I)|ψk ��2 , x where we have applied the property that the unitary operator Uk+1 preserves the norm. Use the inequality �b + c�2 ≤� b �2 +2 � b � · � c � + � c �2 , we obtain �� � �Ox (|ψkx � − |ψk �)�2 + 2�Ox (|ψkx � − |ψk �)� · �(Ox − I)|ψk �� + �(Ox − I)|ψk ��2 x � � � �(Ox − I)|ψk ��2 2 · �|ψkx � − |ψk �� · �(Ox − I)|ψk �� + ≤ �|ψkx � − |ψk ��2 + x x x � ≤ Dk + 4 · �|ψkx � − |ψk �� · ��x|ψk � · |x�� + 4, Dk+1 ≤ x (2) where we have used the property that the unitary operator Ox preserves the norm and Ox − I = −2|x��x|. Now apply the Cauchy’s inequality, � �� � �|ψkx � − |ψk ��2 · ��x|ψk � · |x��2 , �|ψkx � − |ψk �� · ��x|ψk � · |x�� ≤ x x in Eq. (2), we obtain the recursion relation Dk+1 ≤ Dk + 4 � Dk + 4. Assume Dk ≤ 4k 2 , we get Dk+1 ≤ (4k 2 + 8k + 4) = 4(k + 1)2 . P. Shor – 18.435/2.111 Quantum Computation – Lecture 11 5 Hence we have shown that the best you can do to distinguish the target states and other states using j operations is Dj ≤ 4 · j 2 . Note that the least distance√you need to distinguish target states in totally N states is Dleast ≈ O(N ). Therefore, at least k ∼ N is necessary to solve the Grover’s problem. This shows that you can not do better than Grover’s algorithm.