<div dir="ltr">Hi,<div class="gmail_quote"><div dir="ltr"><div><br></div><div>Next week I am going to speak at the seminar, since we do not have other speaker scheduled, and some participants asked me to talk about what I worked on recently.</div><div><br></div><div>If you have any suggestions for speakers please let me know!<br></div><div><br></div><div>You can find the title and abstract below.</div><div><br></div><div>In the meantime enjoy the Easter Holiday!<br></div><div><br></div><div>Best wishes,</div><div><br></div><div>András</div><div><br></div><div>2021.04.08 16:30 CET -- <b>Speaker:</b> András Gilyén<br><br><b>Title:</b> (Sub)Exponential advantage of adiabatic quantum computation with no sign problem<br><br><b>Abstract:</b> We demonstrate the possibility of (sub)exponential quantum speed-up via a quantum algorithm that follows an adiabatic path of a gapped Hamiltonian with no sign problem. This strengthens the quasipolynomial separation recently proved by Hastings. The Hamiltonian that exhibits this speed-up comes from the adjacency matrix of an undirected graph, and we can view the adiabatic evolution as an efficient O(poly(n))-time quantum algorithm for finding a specific "EXIT" vertex in the graph given the "ENTRANCE" vertex. On the other hand we show that if the graph is given via an adjacency-list oracle, there is no classical algorithm that finds the "EXIT" with probability greater than exp(-n^delta) using at most \exp(n^delta) queries for delta = 1/5 - o(1).<br><br>Our construction of the graph is somewhat similar to the "welded-trees" construction of Childs et al., but uses additional ideas of Hastings for achieving a spectral gap and a short adiabatic path.</div></div>
</div></div>