15436

Video URL

https://simons.berkeley.edu/talks/path-detection-quantum-computing-primitive

Path Detection: A Quantum Computing Primitive

(2020). Path Detection: A Quantum Computing Primitive. The Simons Institute for the Theory of Computing. https://simons.berkeley.edu/talks/path-detection-quantum-computing-primitive

Path Detection: A Quantum Computing Primitive. The Simons Institute for the Theory of Computing, Feb. 27, 2020, https://simons.berkeley.edu/talks/path-detection-quantum-computing-primitive 

          @misc{ scivideos_15436,
            doi = {},
            url = {https://simons.berkeley.edu/talks/path-detection-quantum-computing-primitive},
            author = {},
            keywords = {},
            language = {en},
            title = {Path Detection: A Quantum Computing Primitive},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2020},
            month = {feb},
            note = {15436 see, \url{https://scivideos.org/Simons-Institute/15436}}
          }
Shelby Kimmel (Middlebury College)
Talk number15436
Source RepositorySimons Institute
Subject

Abstract

"st-connectivity" is the problem of deciding whether two points in a graph are connected or not (i.e. whether there is a path between them). I will show that a range of common problems can be reduced to st-connectivity, and furthermore, this reduction leads to an optimal quantum algorithm in many cases of interest. The analysis of the quantum algorithm is fairly simple, and uses standard graph theoretic quantities. These properties suggest that st-connectivity would make a good building block, or primitive, for designing and analyzing quantum algorithms.