<div dir="ltr"><div>Hi,</div><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>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups "Quantum CS Seminar" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:qcsseminar+unsubscribe@googlegroups.com">qcsseminar+unsubscribe@googlegroups.com</a>.<br />
To view this discussion on the web visit <a href="https://groups.google.com/d/msgid/qcsseminar/CAG54o1%3DT6kTgwbnpnjzabvcmxewdMKkVOuZgB6JxTrgdMNCh%3Dw%40mail.gmail.com?utm_medium=email&utm_source=footer">https://groups.google.com/d/msgid/qcsseminar/CAG54o1%3DT6kTgwbnpnjzabvcmxewdMKkVOuZgB6JxTrgdMNCh%3Dw%40mail.gmail.com</a>.<br />