Quantum computers have the potential to solve certain problems dramatically faster than classical computers. One of the main quantum algorithmic tools is the notion of quantum walk, a quantum mechanical analog of random walk. I will describe quantum algorithms based on this idea, including an optimal algorithm for evaluating Boolean formulas and one of the best known algorithms for simulating quantum dynamics. I will also show how quantum walk can be viewed as a universal model of quantum computation.


Talk Number PIRSA:14040135
Speaker Profile Andrew Childs
Collection Colloquium