PIRSA:14040135

The computational power of quantum walk

Childs, A. (2014). The computational power of quantum walk. Perimeter Institute. https://pirsa.org/14040135

Childs, Andrew. The computational power of quantum walk. Perimeter Institute, Apr. 11, 2014, https://pirsa.org/14040135 

          @misc{ pirsa_PIRSA:14040135,
            doi = {10.48660/14040135},
            url = {https://pirsa.org/14040135},
            author = {Childs, Andrew},
            keywords = {},
            language = {en},
            title = {The computational power of quantum walk},
            publisher = {Perimeter Institute},
            year = {2014},
            month = {apr},
            note = {PIRSA:14040135 see, \url{https://pirsa.org}}
          }

Andrew Childs University of Waterloo

DOI 10.48660/14040135
Collection
Talk Type Scientific Series

Abstract

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.