Join the Department of Computer Science as we welcome Andrew Childs, University of Maryland who will be delivering a lecture on, 'Quantum Algorithms and the Power of Forgetting.'

When: 11/3/23 @ 2:30 PM

Where: New Computer Science Building, Room 120.

Reception to follow.

Abstract:

Quantum computers can solve certain problems dramatically faster than classical computers. In particular, the welded tree problem provides an example of a black-box task that can be solved exponentially faster by a quantum walk than by any classical algorithm. 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 probably cannot find a path from ENTRANCE to EXIT. While this does not rule out the possibility of a quantum algorithm that efficiently finds a path, it is unclear how an algorithm could benefit by more general behavior. Our no-go result suggests that, for some problems, quantum algorithms must necessarily forget how they reach a solution in order to outperform classical computation.

Bio:

Andrew Childs is a professor in the Department of Computer Science and the Institute for Advanced Computer Studies (UMIACS) at the University of Maryland. He is the co-director of the Joint Center for Quantum Information and Computer Science (QuICS), and the director of the NSF Quantum Leap Challenge Institute for Robust Quantum Simulation. Childs's research interests are in the theory of quantum information processing, especially quantum algorithms. He has explored the computational power of quantum walk, providing an example of exponential speedup, demonstrating computational universality, and constructing algorithms for problems including search and formula evaluation. Childs has also developed fast quantum algorithms for simulating Hamiltonian dynamics. His other areas of interest include quantum query complexity and quantum algorithms for algebraic problems. Before coming to UMD, Childs was a DuBridge Postdoctoral Scholar at Caltech from 2004-2007 and a faculty member in Combinatorics & Optimization and the Institute for Quantum Computing at the University of Waterloo from 2007-2014. Childs received his doctorate in physics from MIT in 2004.