Unstructured SearchBlack-Box TechniquesGrover's algorithmAnother approachMore applicationsThe Collision ProblemCS 294-2 Quadratic speedup for unstructured search - Grover’s Al-gorithm 2/28/07Spring 2007 Lecture 110.1 Unstructured SearchHere’s the problem: You are given an efficient boolean function f : {1, ..., N} → {0,1}, and are promised that forexactly one a ∈{1,. .. ,N}, f(a) = 1. Think of this as a table of size N, where exactly one element has value 1, and allthe others are 0. How long does it take to determine the a such that f(a) = 1?Since we assume f can be computed classically in polynomial time, we can also compute it in superposition:∑xαx|xi|0i →∑xαx|xi|f(x)iAs we saw before, we can use circuit for f to put information about f(x) in the phase by effecting the transformation:∑xαxx→∑xαx(−1)f(x)xHere is another way of creating this phase state:∑xαx|xi|0i−|1i√27→∑xαx |xi|f(x)i−|xi|f(x)i√2!=∑xαx|xi |f(x)i−|f(x)i√2!=∑xαx|xi(−1)f(x)|0i−|1i√2Now, we might as well assume f is a black box or oracle. All we need to do is design an algorithm that findsa : f(a) = 1.0.1.1 Black-Box TechniquesA black-box algorithm attempts to determine a without actually examining the structure of f, but it is allowed toevaluate f on any input or superposition of inputs. As we saw before, any black-box quantum algorithm must makeΩ(2n/2) queries to f.In complexity theory, black-box techniques such as simulation and diagonalization are one way to determine whetheror not two complexity classes are equal. Since these techniques don’t look inside the actual machine, they would notbe able to tell if you gave your machine access to an oracle f, which is called relativization. Complexity classes can bedefined relative to oracles: for example, Pfis the class of problems that can be solved in polynomial time if you haveCS 294-2, Spring 2007, Lecture 11 0-1|ai|ui =1√N∑Nx=1|xi|ei2θθφθ+φ|vi|v0iFigure 0.1: To rotate |vi by 2θto |v0i, we reflect around |ei and then reflect around |ψ0i.access to the oracle f. Now if there is an oracle f relative to which two complexity classes are equal, and an oracleg relative to which they are not, then these black-box techniques cannot be used to determine whether or not the twoclasses are equal. In the case of P and NP, ∃f . Pf= NPf, and ∃g . Pg6= NPg, so no black-box technique can answerthe P =? NP question.There are statements in complexity theory that don’t relative, such as IP = PSPACE and MIP = NEXP. However,these rely on a single technique using the principle of local checkability, and we don’t know how to apply it to eitherP =? NP or NP ⊆? BQP. So we have no idea how to resolve these open questions.0.2 Grover’s algorithmGrover’s algorithm finds a in O(√N) steps. Consider the N dimensional Hilbert space spanned by |1i,. .. ,|Ni. Wewish to find |ai. Consider the uniform superposition |ui =∑x1√N|xi. Then ha|ui = 1/√N = cosθa,u.Consider the two dimensional subspace spanned by |ai and |ui. Let |ei be the state orthogonal to |ai in this subspace.Letθbe the angle between |ui and |ei. Then sinθ= cos(π2−θ) = cosθa,u= 1/√N and thereforeθ≈ 1/√N. SeeFigure 0.1 for an illustration of these vectors.|ai is the target, so we want to increaseθ. But how?One way to rotate a vector is to make two reflections. In particular, we can rotate a vector |vi by 2θby reflecting about|ei and then reflecting about |ui. This transformation is also illustrated in Figure 0.1.Each step of our algorithm is a rotation by 2θ(we discuss the implementation below). This means that we needπ/22θiterations for the algorithm to complete. We know thatθ≈1√N, so we need O(√N) iterations for the algorithm tocomplete. In the end, we get very close to |ai, and then with high probability, a measurement of the state yields a.How do you implement the two reflections?CS 294-2, Spring 2007, Lecture 11 0-21. Reflection about |ei is easy. We can reflect about the hyperplane orthogonal toaby flipping the phase of thecomponent in the direction of |ai, i.e. carry out the transformation∑xαxx→∑xαx(−1)f(x)x2. For the reflection about |ui, let us first to determine how to reflect about the basis state |0i. We can do so byflipping the phase of all components except |0i, i.e. carry out the transformation∑xαxx→α00+∑x6=0−αxxSince |ui= H⊗n|0i, we can flip around |ui by first applying the Hadamard transform H⊗n, then reflecting about|0i, and finally applying the Hadamard again to switch back from the Hadamard basis.0.3 Another approachLet’s look at the search algorithm differently, with all superpositions. The rotation about |ui, D, is an ”inversion aboutthe mean”:1. For N = 2n, D can be decomposed and rewritten as:D = HN1 0 ··· 00 −1 ··· 0............0 0 ··· −1HN= HN2 0 ··· 00 0 ··· 0............0 0 ··· 0−IHN= HN2 0 ··· 00 0 ··· 0............0 0 ··· 0HN−I=2/N 2/N ··· 2/N2/N 2/N ··· 2/N............2/N 2/N ··· 2/N−I=2/N −1 2/N ··· 2/N2/N 2/N −1 ··· 2/N............2/N 2/N ··· 2/N −1Observe that D is expressed as the product of three unitary matrices (two Hadamard matrices separated by aconditional phase shift matrix). Therefore, D is also unitary. Regarding the implementation, both the Hadamardand the conditional phase shift transforms can be efficiently realized within O(n) gates.CS 294-2, Spring 2007, Lecture 11 0-32. Consider D operating on a vector |αi to generate another vector |βi:Dα1...αi...αN= 2µ...µ...µ−α1...αi...αN, whereµ=1NN∑i=1αiHere,µis the mean amplitude, so the expression 2µ−αidescribes a reflection ofαiabout the mean. Thus, theoperation D can be considered an “inversion about the mean” with respect toαi.The quantum search algorithm iteratively improves the probability of measuring a solution. Here’s how:1. Start state is |ψ0i = |ui =∑x1√N|xi2. Invert the phase of |ai using f3. Then invert about the mean using D4. Repeat steps 2 and 3 O(√N) times, so in each
View Full Document
Unlocking...