Quantum Computing (fall2013) Instructor:Shengyu Zhang. Lecture 5 Quantum searching algorithms and lower bounds 1.Grover's search After learning quantum algorithms for algebraic problems,we have a feeling that quantum speedup(over classical algorithms)needs a strong algebraic structure in the problem.Thus it was a surprise when Grover discovered that searching,one of the most fundamental primitives,in a totally unstructured set,provides quantum speedup. Consider a set of n elements,say {22,8,3,12,...).We want to see whether there is a target element,say 11.Suppose that once given any particular element,it is easy for us to check whether it's our target.Classically,to solve the problem,we clearly need to scan the whole list,yielding a complexity of (n).Using Grover's search,we can finish the job by looking at the list only 0(vn)times. To make it easier to state,suppose that we are given a string x E(0,1)and we want to decide whether x=00...0.We have an oracle to tell us whether a particular position is 1 or 0.That is,if we make a query "xi=?",then the oracle gives the answer.Such algorithms are called query algorithms.You must have seen these when learning sorting,where the oracle answers the question"and it is well-known that the optimal sorting algorithm needs 0(n log n)queries.In a quantum algorithm,we can make queries in superposition,and get corresponding answers in superposition as well.For example,if we make a query by inputting∑i10）to the oracle,.then we'll get∑ili)lxi〉in the answer..We can also assume that the oracle takes a query li)and answers(-1)li).Can you see why? Assuming the latter oracle format,we now give the Grover's algorithm. 赤26) 922(-100 (H⑧1ognR。H®logm)
Quantum Computing (Fall 2013) Instructor: Shengyu Zhang. Lecture 5 Quantum searching algorithms and lower bounds 1. Grover’s search After learning quantum algorithms for algebraic problems, we have a feeling that quantum speedup (over classical algorithms) needs a strong algebraic structure in the problem. Thus it was a surprise when Grover discovered that searching, one of the most fundamental primitives, in a totally unstructured set, provides quantum speedup. Consider a set of 𝑛 elements, say {22,8,3,12,…}. We want to see whether there is a target element, say 11. Suppose that once given any particular element, it is easy for us to check whether it’s our target. Classically, to solve the problem, we clearly need to scan the whole list, yielding a complexity of 𝛩(𝑛). Using Grover’s search, we can finish the job by looking at the list only O(√𝑛) times. To make it easier to state, suppose that we are given a string 𝑥 ∈ {0,1} 𝑛 and we want to decide whether 𝑥 = 00 …0. We have an oracle to tell us whether a particular position is 1 or 0. That is, if we make a query “𝑥𝑖 =?”, then the oracle gives the answer. Such algorithms are called query algorithms. You must have seen these when learning sorting, where the oracle answers the question “𝑥𝑖 > 𝑥𝑗 ?” and it is well-known that the optimal sorting algorithm needs 𝑂(𝑛 log 𝑛) queries. In a quantum algorithm, we can make queries in superposition, and get corresponding answers in superposition as well. For example, if we make a query by inputting ∑ |𝑖〉|0〉 𝑖 to the oracle, then we’ll get ∑ |𝑖〉|𝑥𝑖 〉 𝑖 in the answer. We can also assume that the oracle takes a query ∑ |𝑖〉 𝑖 and answers ∑ (−1) 𝑥𝑖 |𝑖〉 𝑖 . Can you see why? Assuming the latter oracle format, we now give the Grover’s algorithm. 1 √𝑛 ∑ |𝑖〉 𝑛−1 𝑖=0 𝑂 → 1 √𝑛 ∑ (−1) 𝑥𝑖|𝑖〉 𝑛−1 𝑖=0 (𝐻 ⊗log 𝑛𝑅0𝐻 ⊗log 𝑛 ) 𝑘 → …
Here Ro is the reflection about the state 0),namely,Rol0)=10)and Roli)=-i)for all iE{1,2,...,n-1).The oracle 0 can also be viewed as a reflection about the state where m:1).These two reflections combined have the effect of rotating the current state towards a target one)by 20 where arccos(1-m/n)=0(m/n).So it takes (n/2)/20=0(n/m)iterations.Since in each iteration the algorithm only takes 1 query,the algorithm needs(n/m)=0(n) queries. (In class,I'll show a geometrical interpretation of the algorithm,and things will be very clear.) After the rotations,measure in the computational basis and then verify it by one more query. In this way we'll find an i with x=1. Question:What if we don't know m in ad vance?We can try m =n/2,n/4,n/8,...until we succeed. 2.Quantum query algorithms Grover's searching algorithm belongs to the general class of quantum query algorithms Suppose f:E,"o and an oracle O has the following effect: ∑aka, aiazli,a+x,z） i,a,2 where the addition a+x is mod l.That is,the oracle tells the value of input variables xi in superposition.Note that it doesn't let us to get all information of input variables in one query,since the answers are in a superposition and we cannot extract the n bits from it. Recall that even the last algorithm we talked about in last lecture(for HSP for non-Abelian group)falls in the framework of query algorithm. A general question is how to design query efficient algorithms and how to prove lower bounds for quantum query complexity.Namely,we want to pin down the quantum query complexity Q(f),the smallest number of queries needed to compute f with error
Here 𝑅0 is the reflection about the state |0〉, namely, 𝑅0 |0〉 = |0〉 and 𝑅0 |𝑖〉 = −|𝑖〉 for all 𝑖 ∈ {1,2, …, 𝑛 − 1}. The oracle 𝑂 can also be viewed as a reflection about the state 1 √𝑛−𝑚 ∑ |𝑖〉 𝑖:𝑥𝑖 =0 , where 𝑚 = |{𝑖: 𝑥𝑖 = 1}|. These two reflections combined have the effect of rotating the current state towards a target one 1 √𝑚 ∑ |𝑖〉 𝑖:𝑥𝑖=1 by 2𝜃 where 𝜃 = arccos(√1 − 𝑚/𝑛) = 𝛩(√𝑚/𝑛). So it takes (π/2)/2𝜃 = Θ(√𝑛/𝑚) iterations. Since in each iteration the algorithm only takes 1 query, the algorithm needs Θ(√𝑛/𝑚) = 𝑂(√𝑛) queries. (In class, I’ll show a geometrical interpretation of the algorithm, and things will be very clear.) After the rotations, measure in the computational basis and then verify it by one more query. In this way we’ll find an 𝑖 with 𝑥𝑖 = 1. Question: What if we don’t know 𝑚 in advance? We can try 𝑚 = 𝑛/2, 𝑛/4,𝑛/8,… until we succeed. 2. Quantum query algorithms Grover’s searching algorithm belongs to the general class of quantum query algorithms. Suppose 𝑓: 𝛴𝐼 𝑛 → 𝛴𝑂 and an oracle O has the following effect: ∑𝛼𝑖,𝑎,𝑧 |𝑖, 𝑎, 𝑧〉 𝑖,𝑎,𝑧 𝑂 → ∑𝛼𝑖,𝑎,𝑧 |𝑖, 𝑎 + 𝑥𝑖 ,𝑧〉 𝑖,𝑎,𝑧 where the addition 𝑎 + 𝑥𝑖 is 𝑚𝑜𝑑 |Σ𝐼 |. That is, the oracle tells the value of input variables 𝑥𝑖 in superposition. Note that it doesn’t let us to get all information of input variables in one query, since the answers are in a superposition and we cannot extract the 𝑛 bits from it. Recall that even the last algorithm we talked about in last lecture (for HSP for non-Abelian group) falls in the framework of query algorithm. A general question is how to design query efficient algorithms and how to prove lower bounds for quantum query complexity. Namely, we want to pin down the quantum query complexity 𝑄𝜖 (𝑓), the smallest number of queries needed to compute 𝑓 with error
probability at most e on any input.Next we introduce one powerful method for lower bound proving. 3.Quantum adversary method To use the quantum adversary method,we need to first finda matrix ECNXN where N= Index the rows by x and columns by y.The matrix needs to satisfy I(x,y)=0 as long as f(x)= f(y).Define DiECNxN by Di(x,y)=1 ifxy and Di(xy)=0 otherwise.Suppose r is nonzero,and consider the quantity This is a wer bound of the quantum query compexi! Taking the bestr and denote ADV(= MI The lower bound goes like the following. Q.n≥G-a-可)A0 The proof is in paper [HLS07],which is well written and self-contained enough to be easily read. Thus there is no point of copying the proofhere.I'll show the whole proof in class. Note Grover's search first appeared in [Gro96].The quantum adversary method was originally discovered in a weaker form by Ambainis [Amb02],and various equivalent forms were founded;see [SS06].The final form as we presented was proposed in [HLS07],which is stronger than previous ones. Reference [Amb02]Andris Ambainis,Quantum Lower Bounds by Quantum Arguments,Journal of Computer and System Sciences,Volume 64,Issue 4,pages 750-767,2002.(Earlier at STOC'00.) [Gro96]Lov Grover,A fast quantum mechanical algorithm for database search,in Proceedings of the twenty-eighth annual ACM symposium on Theory ofcomputing,pages 212-219,1996
probability at most 𝜖 on any input. Next we introduce one powerful method for lower bound proving. 3. Quantum adversary method To use the quantum adversary method, we need to first find a matrix 𝛤 ∈ ℂ 𝑁×𝑁 where 𝑁 = |Σ𝐼 |𝑛. Index the rows by 𝑥 and columns by 𝑦. The matrix needs to satisfy 𝛤(𝑥, 𝑦) = 0 as long as 𝑓(𝑥) = 𝑓(𝑦). Define 𝐷𝑖 ∈ ℂ 𝑁×𝑁 by 𝐷𝑖 (𝑥,𝑦) = 1 if 𝑥𝑖 ≠ 𝑦𝑖 and 𝐷𝑖 (𝑥,𝑦) = 0 otherwise. Suppose 𝛤 is nonzero, and consider the quantity ‖𝛤‖ max 𝑖 ‖𝛤∘𝐷𝑖 ‖ . This is a lower bound of the quantum query complexity! Taking the best 𝛤 and denote 𝐴𝐷𝑉(𝑓) = max 𝛤≠0 ‖𝛤‖ max 𝑖 ‖𝛤∘𝐷𝑖 ‖ . The lower bound goes like the following. 𝑄𝜖 (𝑓) ≥ ( 1 2 − √𝜖(1 − 𝜖)) 𝐴𝐷𝑉(𝑓) The proof is in paper [HLS07], which is well written and self-contained enough to be easily read. Thus there is no point of copying the proof here. I’ll show the whole proof in class. Note Grover’s search first appeared in [Gro96]. The quantum adversary method was originally discovered in a weaker form by Ambainis [Amb02], and various equivalent forms were founded; see [SS06]. The final form as we presented was proposed in [HLS07], which is stronger than previous ones. Reference [Amb02] Andris Ambainis, Quantum Lower Bounds by Quantum Arguments, Journal of Computer and System Sciences, Volume 64, Issue 4, pages 750–767, 2002. (Earlier at STOC’00.) [Gro96] Lov Grover, A fast quantum mechanical algorithm for database search, in Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212-219, 1996
[HLS07]Peter Hoyer,Troy Lee,Robert Spalek,Negative weights make adversaries stronger,in Proceedings of the thirty-ninth annual ACM symposium on Theory of computing,pages 526-535, 2007. [SS06]Robert Spalek,Mario Szegedy,All Quantum Adversary Methods are Equivalent,Theory ofComputing 2(1):1-18,2006
[HLS07] Peter Hoyer, Troy Lee, Robert Spalek, Negative weights make adversaries stronger, in Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 526 – 535, 2007. [SS06] Robert Spalek, Mario Szegedy, All Quantum Adversary Methods are Equivalent, Theory of Computing 2(1): 1-18, 2006