[Qp-l] [QCSBP] Seminar next week: András Gilyén

[Gilyén András]

Hi,

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.

If you have any suggestions for speakers please let me know!

You can find the title and abstract below.

In the meantime enjoy the Easter Holiday!

Best wishes,

András

2021.04.08 16:30 CET -- *Speaker:* András Gilyén

*Title:* (Sub)Exponential advantage of adiabatic quantum computation with
no sign problem

*Abstract:* 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).

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.

-- 
You received this message because you are subscribed to the Google Groups "Quantum CS Seminar" group.
To unsubscribe from this group and stop receiving emails from it, send an email to qcsseminar+unsubscribe at googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/qcsseminar/CAG54o1%3DT6kTgwbnpnjzabvcmxewdMKkVOuZgB6JxTrgdMNCh%3Dw%40mail.gmail.com.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://plc.inf.elte.hu/pipermail/qp-l/attachments/20210401/5a5581e7/attachment.html>