Dartmouth Events

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 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. (Joint work with Stacey Jeffery, Michael Jarret, and Alvaro Piedrafita.) This talk should be accessible to a wide quantum audience.