Path Detection: A Quantum Computing Primitive
"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 any Boolean formula evaluation problem can be transformed into an st-connectivity problem, so good algorithms for st-connectivity potentially give good algorithms for formula evaluation. I will discuss a quantum algorithm for st-connectivity that is relatively straightforward to analyze, and that is also optimal for evaluating many Boolean formulas.
Bio: Shelby Kimmel is a Hartree Postdoctoral Fellow at the University of Maryland at QuICS -- the Joint Center for Quantum Information and Computer Science. Previously, she earned a PhD in physics from MIT and a BA in astrophysics from Williams College.