<div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div>Hi,</div><div><br></div><div>This is a friendly reminder that tomorrow afternoon I will speak about "(Sub)Exponential advantage of adiabatic quantum computation with no sign problem". You can find the abstract of the talk at the bottom of this 
email.<br></div><div><br></div><div>You can join using the following Zoom link: <a href="https://berkeley.zoom.us/j/96826613566?pwd=MUZtOGllSklFM2d0NGhwaFBqNXhjdz09" target="_blank">https://berkeley.zoom.us/j/96826613566?pwd=MUZtOGllSklFM2d0NGhwaFBqNXhjdz09</a> (due to the default privacy settings you need to sign into your Zoom account before clicking on the above link).</div><div><br></div><div>After the seminar we will have room for informal discussions as well on gather.town: <a href="https://gather.town/i/LtMsN2VZ">https://gather.town/i/LtMsN2VZ</a> (to avoid unwanted echoes it is recommended to use Google Chrome or the dedicated gather.town app)</div><div><br></div><div>Best,</div><div><br></div><div>András</div><div><br></div><div>2021.03.25 16:30 CET -- <b>Speaker: András Gilyén</b> (Caltech, CA, USA)<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.<span></span></div></div></div></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/CAG54o1n_VL0MUAdYoMDMoYEB_O8YKVnOF6aghZyPQV_Kt7Uo5w%40mail.gmail.com?utm_medium=email&utm_source=footer">https://groups.google.com/d/msgid/qcsseminar/CAG54o1n_VL0MUAdYoMDMoYEB_O8YKVnOF6aghZyPQV_Kt7Uo5w%40mail.gmail.com</a>.<br />