14:00
15:00

This talk is mostly based on a paper by Andras Gilyen, Matthew Hastings and Umesh Vazirani titled " (Sub)Exponential advantage of adiabatic Quantum computation with no sign problem ” published at STOC 2021. Quantum Adiabatic Computation is another model of quantum computation which was introduced to solve some optimization problems due to the closeness of hamiltonian evolution to constraint satisfaction problems. It has been proved to be equivalent to the circuit model. In this talk I will give a brief introduction to Quantum Adiabatic Computation (QAC) and the power it offers over any classical algorithm when the hamiltonian is promised to be stoquastic i.e. a hamiltonian with all off-diagonal entries being non-positive. I will present a simple graph search problem given query access to the graph which is initially efficiently solvable by both QAC and classical algorithms but gradually changed to one that is hard for any classical algorithm to the extent that it shows a sub-exponential separation between QAC and classical algorithms in the query model. I will talk about the ideas in the paper which are behind this gradual separation and present some interesting questions to further amplify this separation to an exponential separation.

https://combalgo.labri.fr/pmwiki.php/Groupe/Info-Quantique

Room 178 - unsual time!