[Qp-l] [QCSBP] Re: Seminar tomorrow at 16:30 CET: András Gilyén

Gilyén András gilyenandras at gmail.com
Thu Apr 8 16:14:08 CEST 2021


Hi,

There was some typo in the reminder e-mail. The swminar is today, and
starts in 15 minutes!

Best,

András

On Wed, 7 Apr 2021, 14:08 Gilyén András, <gilyenandras at gmail.com> wrote:

> Hi,
>
> 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.
>
> You can join using the following Zoom link:
> https://berkeley.zoom.us/j/96826613566?pwd=MUZtOGllSklFM2d0NGhwaFBqNXhjdz09
> (due to the default privacy settings you need to sign into your Zoom
> account before clicking on the above link).
>
> After the seminar we will have room for informal discussions as well on
> gather.town: https://gather.town/i/LtMsN2VZ (to avoid unwanted echoes it
> is recommended to use Google Chrome or the dedicated gather.town app)
>
> Best,
>
> András
>
> 2021.03.25 16:30 CET -- *Speaker: András Gilyén* (Caltech, CA, USA)
>
> *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/CAG54o1k5_yv9UawrjWOgiRjpyJzfjMTr8zgcC-cZ7qKK%2BT%3D1Jg%40mail.gmail.com.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://plc.inf.elte.hu/pipermail/qp-l/attachments/20210408/948b0b6c/attachment.html>


More information about the Qp-l mailing list