Transcript Slide 1
Quantum Computing MAS 725 Hartmut Klauck NTU 2.4.2012 Question: Can we solve NP complete problems efficiently on a quantum computer ?? Of course we cannot disprove such a possibility More specific: Is it possible by using only black box techniques? And not the precise problem structure E.g. SAT Problem: given a CNF formula on n variables, is there a satisfying assignment? Trivial approach: Try all 2n assignments of the variables Can a quantum computer do this efficiently? Black Box Model Can we solve SAT quickly in the black box model? I.e., assume all we can do is test assignments, we cannot use more information about a formula n Boolean variables, N=2n assignments Search problem: for bits x0,...,xN-1 find xi=1 if such an i exists Search problems Problem 1: Given x0,...,xN-1, find i with xi=1 if possible Problem 2 : Given x0,...,xN-1 with a guarantee that there is exactly one xi=1, find i Problem 3: Given x0,...,xN-1, compute OR(x0,...,xN-1) Problem 4: Given x0,...,xN-1 with guarantee that either exactly one xi=1 or no xi=1, decide which 2),3) are easier than 1), and 4) is easier than 2),3) Classical algorithms Consider any randomized algorithm with error 1/3 for Problem 4) We will show: (N) queries are necessary Quantum algorithms How fast can quantum computers search? Grover’s algorithm needs O(N1/2) queries! A matching lower bound was proved 2 years earlier… Every quantum algorithm for Problem 4) needs (N1/2) queries This rules out “brute force” algorithms for SAT, they need time 2n/2 Grover’s algorithm [Grover 96] Needs N1/2 queries in the worst case More general: If there are t positions i with xi=1, then we need (N/t)1/2 queries Grover’s algorithm We start by assuming there is exactly one xi=1, unknown to us (Problem 2) Consider vectors |ii and the vector |0i=j=0...N-1 1/N1/2 |ji ”Goal” und “Start” We try to decrease the distance between the two? Consider the plane spanned by|ii and |0i; Let|ei be orthogonal to |ii in that plane Grover’s algorithm Consider the plane spanned by|ii and |0i; Let|ei be orthogonal to |ii in that plane Reflect around |ei and then around |0i Result: |ii |0i |ei Grover’s algorithm Consider the plane spanned by|ii and |0i; Let|ei be orthogonal to |ii in that plane Reflect around |ei and then around |0i Result: |ii |0i |ei Grover’s algorithm Consider the plane spanned by|ii and |0i; Let|ei be orthogonal to |ii in that plane Reflect around |ei and then around |0i Result: rotation by 2 |ii |0i |ei Grover’s algorithm |ii Consider the plane spanned by|ii and |0i; Let|ei be orthogonal to |ii in that plane Reflect around |ei and then around |0i Result: rotation by 2 If our vector has an angle to |0i, then first -- to |ei and then 2 + to |0i |0i |ei Grover’s algorithm Reflect around |ei and then around |0i Result: rotation by 2 |ei=ij 1/(N-1)1/2 |ji How many iterations? At most (/2)/(2) iterations 1/N1/2 = hi|0i = cos(/2- ) = sin() Then 1/N1/2 = sin() ¼ and we need around /4 ¢ N1/2 iterations Grover’s algorithm |ii Reflect around |ei and then around |0i Result: rotation by 2 |ei=ij 1/(N-1)1/2 |ji But how can we do it? Reflection around |ei: map a|ii+ b|ei to -a|ii+ b|ei We can do this with a query! Black box query can change sign for|ii when xi=1 |i |ei Grover’s algorithm |ii Reflect around |ei and then around |0i Reflection around |0i: Apply 2|0ih 0|- I Let N=2n, positions 0,...,N-1 in binary Implement this unitary by Hn P Hn, where P|0ni=|0ni and P|xi=-|xi otherwise |0i |ei Grover’s algorithm Operation 2|0ih 0|- I Implemented as Hn P Hn, where P|0ni=|0ni and P|xi=-|xi otherwise Grover’s algorithm Operation 2|0ih 0|- I Implemented as Hn P Hn, where P|0ni=|0ni and P|xi=-|xi Grover’s algorithm Operation 2|0ih 0|- I Other interpretation: vector (a0,...,aN-1) is mapped to vector with (2j aj/N)-ai in position i Inversion around the average Grover’s algorithm Black Box: Use additional qubit 1/21/2 (|0i-|1i) Apply the usual black box: |ii|ai is mapped to |ii|a©xii Trick with the additional qubit: black box maps |ii to (-1)xi |ii Grover’s algorithm Register with n qubits Starting state |0i=j=0...N-1 1/N1/2 |ji [Apply Hn to |0ni] Iterate roughly N1/2 times: Apply black box Apply Hn P Hn , where P|0ni=|0ni and P|xi=-|xi Measure i, test also, if xi=1 Grover’s algorithm H H H H H H O H H H H H H ¼/4 P N 1/2 H H H H H H Example x0=1, other xi=0 Start: j=0...N-1 1/N1/2 |ji Query: j=1...N-1 1/N1/2 |ji- 1/N1/2|0i Inversion around the average vector (a0,...,aN-1) maps to vector with (2j aj/N)-ai in position i Result: amplitude of |0i increases to roughly 3/N1/2, other amplitudes stay almost the same Repeat…. Finish after (/2)/(2/N1/2)=(/4) N1/2 steps Exact number of iterations If we iterate too many times we move away from the desired final state! Start: j=0...N-1 1/N1/2 |ji 1/N1/2 |i0i +ji0 1/N1/2 |ji kj: amplitude of i0 after j iterations; lj: other amplitudes after j iterations; k0,l0=1/N1/2 Next iteration kj+1= (N-2)/N ¢ kj+2(N-1)/N¢ lj lj+1= (N-2)/N ¢ lj -2/N¢ kj We can show that kj=sin((2j+1)); lj=1/(N-1)1/2 cos((2j+1)) where such that sin2()=1/N km=1 if (2m+1)=/2, if m=(-2)/(4) Error is smaller than 1/N if b/4 N1/2c iterations More than one solution Assume there are t values of i with xi=1 t known Same algorithm, fewer iterations Similar analysis as before, error t/N after b/4 ¢ (N/t)1/2c iterations Important observation: superposition over all marked positions |ii (the goal state) has inner product (t/N)1/2 with |Á0i and so angle between |Á0i and |ei is of that size Unknown number of solutions There are t values of i with xi=1 t is now unknown We use smaller and smaller estimates for t and run the previous algorithm s=N/2,N/4,N/8,...,¼ t/2,... Every time we make O((N/s)1/2) queries Total number of queries s=N/2,N/4,...,t/2 (N/s)1/2 = O((N/t)1/2) Consider (N/t)-1/2 ¢ a=1,...,log N-log t+1 2a/2=O(1) geometric sum Classical algorithms Consider randomized algorithms with error 1/3 for Problem 4) We show that we need (N) queries Classical algorithms Given: randomized algorithm If we have a randomized algo with T queries (worst case) and success probability p then there is a deterministic algorithm with T queries and success p for random x Ex Er [Success for x with r]=p ) there is r, such that Ex [Success for x]¸ p Fix r ) deterministic algorithm Classical algorithms Distribution on inputs: probability 1/2 for 0N, inputs 000010000 have probability 1/(2N) each Deterministic algo with error 1/3 and <N/3 queries Must be correct on 00000 If <N/3 xi are known there are >2/3¢ N positions, that could be one, hence the algorithm makes mistakes on >2N/3, error >1/3 Every algorithm needs at least N/3 queries Quantum search Grover does it in O(N1/2) Lower bound for Problem 4) (N1/2) The lower bound Consider quantum query algorithm A Run A on 0N , with T queries States 0...N-1 ai,t |ii |ui,ti |vi,ti i: address, u register for output of the black box , v for workspace, t=1..T time Define query magnitude M(i) = t=1...T|ai,t|2 Intuitively “probability of querying i” Ei M(i)· T/N Fix i with M(i)· T/N A has little information regarding xi, cannot decide well whether xi=1 or =0 The lower bound Query magnitude M(i) = t=1...T|ai,t|2 Fix i with M(i) · T/N Cauchy Schwarz: t=1...T|ai,t| · t=1...T1¢ |ai,t|· T1/2 (t=1...T|ai,t|2)1/2· T/N1/2 y(i) is a string with y(i)i=1 and 0 elsewhere Consider the following situations: In query 1 to t Black Box holds 0N From query t+1 Black Box holds y(i) Final state |(t)i |(0)i Final state on y(i); |(T)i Final state on 0N The lower bound Consider distance between |(t)i and |(t-1)i Then: Same until step t-1 In step t we introduce distance 21/2|ai,t| From step t+1 no change Set |E(t)i= |(t)i-|(t-1)i Then kE(t) k· 21/2|ai,t| The lower bound |(0)i final state on y(i); |(T)i final state on 0N k |(T)i - |(0)i k = k |(T)i - |(T-1)i +|(T-1)i - |(0)i k · k |(T)i - |(T-1)i k + k |(T-1)i - |(0)i k · t=1...T k |(t)i - |(t-1)i k = t=1...T k |E (t)i k · t=1...T 21/2 |ai,t|· 21/2 T/N 1/2 If T<N1/2/10, then the distance is some small constant, i.e., the error will be large and 0N and y(i) have the same output with some good probability