Theory Seminar: Computational speedups using small quantum devices

Yimin Ge (MPQ Theory Department)
While fully scalable quantum computers may be far off, small quantum computers may be achievable in the foreseeable future.

Yimin Ge (MPQ Theory Department)
Herbert-Walther Lecture Hall G0.25
Wed 03. April 2019, 11:30 am (MEZ)

Abstract:

While fully scalable quantum computers may be far off, small quantum computers may be achievable in the foreseeable future. It remained unclear however, how they could be utilised for speeding up relevant computations of much larger problem instances. The reason is that quantum and classical algorithms typically exploit global structures of problems, and restricting superpositions to smaller block sizes will break that structure. Thus, for structured problems where arbitrarily sized quantum computers offer large speedups, small quantum computers may be expected to be of no significant help given large inputs. In this talk, I will show that this is in general not true: given a small quantum computer with only M qubits, it is possible to significantly speed up certain important classical algorithms, even when the problem size is much larger than M. Based on the famous 3SAT algorithm of Schöning, I will present a quantum-enhanced version for solving 3SAT problems involving n>>M variables that significantly speeds up its fully classical counterpart. I will also show similar results for the cubic Hamiltonian cycle problem, and moreover hightlight general criteria for when such speedups may be possible in other algorithms. Joint work with Vedran Dunjko and Ignacio Cirac.