[ICQ] Mario Szegedy (Rutgers University) Why Quadratic?

Several well-known quantum algorithms provide up to, or exactly, quadratic speed-ups compared to their classical counterparts. Are these merely variants of Grover's algorithm? Why do we hit this exact speed bump? In this survey talk we examine a range of algorithms, from quantum random walks to quantum versions of Monte Carlo methods, and explore these questions.


Room 178