Area 1:Quantum Algorithms 1994 1996 1998 2000 2002 2004 2006 2008 ● Element Distinctness:Given n integers,decide whether they are the all distinct. ·Classical:(n) Quantum:Θ(n23) Apply quantum walk on (n,n2/3)-Johnson graph. AAKV: Ambainis*1: Def Ele.Dist. QW (Quantum Walk):poly and exp speedup;rapidly developed. *1:A.Ambainis.FOCS04
Area 1: Quantum Algorithms 1994 1996 1998 2000 2002 2004 2006 2008 QW (Quantum Walk): poly and exp speedup; rapidly developed. AAKV: Def • Element Distinctness: Given n integers, decide whether they are the all distinct. • Classical: Θ(n) • Quantum: Θ(n2/3) – Apply quantum walk on (n,n2/3)-Johnson graph. *1: A. Ambainis, FOCS’04 Ambainis*1 : Ele. Dist
Area 1:Quantum Algorithms 1994 1996 1998 2000 2002 2004 2006 2008 ·Classica:曰(n) ·Quantum:~曰(Nn) apply QW on the formula graph with weight carefully Grover's search: designed for inductions to OR function general formula by (AND-OR-NOT work. AAKV: Ambainis: ACRSZ*1:Formula Def Ele.Dist. Evaluation QW (Quantum Walk):poly and exp speedup;rapidly developed. *1:A.Ambainis,A.Childs,B.Reichardt,R.Spalek,S.Zhang.FOCS'07
Area 1: Quantum Algorithms 1994 1996 1998 2000 2002 2004 2006 2008 QW (Quantum Walk): poly and exp speedup; rapidly developed. AAKV: Def *1: A. Ambainis, A. Childs, B. Reichardt, R. Spalek, S. Zhang. FOCS’07 Ambainis: Ele. Dist. ACRSZ*1 : Formula Evaluation ∧ ∨ ¬ ∧ general formula by {AND-OR-NOT} ∨ Grover’s search: OR function • Classical: Θ(n) • Quantum: ~ Θ(√n) • apply QW on the formula graph with weight carefully designed for inductions to work