log in  |  register  |  feedback?  |  help  |  web accessibility
MS Defense: Quantum algorithms and the power of forgetting
Amin Shiraz Gilani
3100A ATL
Friday, May 20, 2022, 2:00-4:00 pm Calendar
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)
The so-called Welded Tree Problem provides an example of a black-box problem that can be solved exponentially faster by a quantum walk than by any classical algorithm (https://arxiv.org/abs/quant-ph/0209131). Given the name of a special ENTRANCE vertex, a quantum walk can find another distinguished EXIT vertex using polynomially many queries, though without finding any particular path from ENTRANCE to EXIT. It has been an open problem for twenty years whether there is an efficient quantum algorithm for finding such a path, or if the path-finding problem is hard even for quantum computers. We show that a natural class of efficient quantum algorithms provably cannot find a path from ENTRANCE to EXIT in the Welded Tree Problem. Specifically, we consider algorithms that, within each branch of their superposition, always store a set of vertex labels that form a connected subgraph including the ENTRANCE, and that only provide these vertex labels as inputs to the oracle. While this does not rule out the possibility of a quantum algorithm that efficiently finds a path, it is hard to imagine how an algorithm could benefit by deviating from this behavior. Our no-go result suggests that, to outperform classical computation, quantum algorithms must necessarily forget the path they take to reach a solution.

Examining Committee:
Dr. Andrew Childs    
Dr. Matthew Coudron    
Dr. William Gasarch    

Amin is a master's student in computer science, currently on a Fulbright scholarship. His research interests involve understanding quantum query and computational complexity of combinatorial problems. He is advised by Andrew Childs and Matthew Coudron.

This talk is organized by Tom Hurst