Area 1:Quantum Algorithms 1994 1996 1998 2000 2002 2004 2006 2008 Shor:Factoring Hallgren:Pell's Kuperberg: Discrete Log Equation HSP-Dihedral QFT (Quantum Fourier Transform):exponential speedup;slower than expected. Hidden Subgroup Problem(HSP):Given a function f on a group G, which has a hidden subgroup H,s.t.f is 一 constant on each coset aH, distinct on different cosets. Task:find the hidden H. Factoring,Pell's Equation both reduce to it. Efficient quantum algorithms are known for Abelian groups. Main question:HSP for non-Abelian groups?
Area 1: Quantum Algorithms 1994 1996 1998 2000 2002 2004 2006 2008 QFT (Quantum Fourier Transform): exponential speedup; slower than expected. Shor: Factoring & Discrete Log • Hidden Subgroup Problem (HSP): Given a function f on a group G, which has a hidden subgroup H, s.t. f is – constant on each coset aH, – distinct on different cosets. Task: find the hidden H. • Factoring, Pell’s Equation both reduce to it. • Efficient quantum algorithms are known for Abelian groups. • Main question: HSP for non-Abelian groups? Hallgren: Pell’s Equation Kuperberg: HSP-Dihedral
Area 1:Quantum Algorithms 1994 1996 1998 2000 2002 2004 2006 2008 Shor:Factoring Hallgren:Pell's Kuperberg: Discrete Log Equation HSP-Dihedral QFT、 (Quantum Fourier Transform):exponential speedup;slower than expected. Two biggest cases: HSP for symmetric group S:Graph Isomorphism reduce to it. HSP for dihedral group D:Shortest Lattice Vector reduces to it. HSP(D): Classical (best known):21gIGI Quantum*1:20(VlogIGI) *1:G.Kuperberg.arXiv:quant-ph/0302112,2003
Area 1: Quantum Algorithms 1994 1996 1998 2000 2002 2004 2006 2008 QFT (Quantum Fourier Transform): exponential speedup; slower than expected. Shor: Factoring & Discrete Log • Two biggest cases: – HSP for symmetric group Sn : Graph Isomorphism reduce to it. – HSP for dihedral group Dn : Shortest Lattice Vector reduces to it. • HSP(Dn ): – Classical (best known): 2log|G| – Quantum*1 : 2O(√log|G|) Hallgren: Pell’s Equation Kuperberg: HSP-Dihedral *1: G. Kuperberg. arXiv:quant-ph/0302112, 2003
Area 1:Quantum Algorithms 1994 1996 1998 2000 2002 2004 2006 2008 Shor:Factoring Hallgren:Pell's Kuperberg: Discrete Log Equation HSP-Dihedral QFT、 (Quantum Fourier Transform):exponential speedup;slower than expected. Grover: Search QS (Quantum Search):polynomial speedup;most solved. Given n bits x1,...,Xn,find an i with i =1. Given n bits x1,...,xn decide whether i s.t.=1. Classical:(n) Quantum*1:(Vn) *1:L.Grover.Physical Review Letters,1997
Area 1: Quantum Algorithms 1994 1996 1998 2000 2002 2004 2006 2008 QFT (Quantum Fourier Transform): exponential speedup; slower than expected. QS (Quantum Search): polynomial speedup; most solved. Shor: Factoring & Discrete Log Hallgren: Pell’s Equation Kuperberg: HSP-Dihedral Grover: Search • Given n bits x1 ,…,xn , find an i with xi = 1. – Given n bits x1 ,…,xn , decide whether ∃i s.t. xi = 1. • Classical: Θ(n) • Quantum*1 : Θ(√n) *1: L. Grover. Physical Review Letters, 1997
Area 1:Quantum Algorithms 1994 1996 1998 2000 2002 2004 2006 2008 Shor:Factoring Hallgren:Pell's Kuperberg: Discrete Log Equation HSP-Dihedral QFT (Quantum Fourier Transform):exponential speedup;slower than expected. Grover: Many combinatorial Search /graph problems QS (Quantum Search):polynomial speedup;most solved. AAKV*1: Def QW (Quantum Walk):poly and exp speedup;rapidly developed. *1:D.Aharonov,A.Ambainis,J.Kempe,U.Vazirani.STOC'01
Area 1: Quantum Algorithms 1994 1996 1998 2000 2002 2004 2006 2008 QFT (Quantum Fourier Transform): exponential speedup; slower than expected. QS (Quantum Search): polynomial speedup; most solved. Shor: Factoring & Discrete Log Hallgren: Pell’s Equation Kuperberg: HSP-Dihedral Grover: Search QW (Quantum Walk): poly and exp speedup; rapidly developed. AAKV*1 : Def *1: D. Aharonov, A. Ambainis, J. Kempe, U. Vazirani. STOC'01 Many combinatorial /graph problems
Area 1:Quantum Algorithms 1994 1996 1998 2000 2002 2004 2006 2008 ● Classical random walk on graphs:starting from some vertex, repeatedly go to a random neighbor Many algorithmic applications Quantum walk on graphs:even definition is non-trivial. - For instance:classical random walk converges to a stationary distribution,but quantum walk doesn't since unitary is reversible. AAKV*1: Def QW (Quantum Walk):poly and exp speedup;rapidly developed. *1:D.Aharonov,A.Ambainis,J.Kempe,U.Vazirani.STOC'01
Area 1: Quantum Algorithms 1994 1996 1998 2000 2002 2004 2006 2008 QW (Quantum Walk): poly and exp speedup; rapidly developed. AAKV*1 : Def • Classical random walk on graphs: starting from some vertex, repeatedly go to a random neighbor – Many algorithmic applications • Quantum walk on graphs: even definition is non-trivial. – For instance: classical random walk converges to a stationary distribution, but quantum walk doesn’t since unitary is reversible. *1: D. Aharonov, A. Ambainis, J. Kempe, U. Vazirani. STOC'01