BEGIN:VCALENDAR
VERSION:2.0
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
BEGIN:VEVENT
CATEGORIES:Colloquia / Seminar / Lecture
DESCRIPTION:Please register here to join us for the CS Colloquium Series 20
20-21 via Zoom. Once you register\, you will receive a recurring Zoom link.
You only need to register once to be able to attend any of the seminars. \
n\n---\n\nA crucial milestone before achieving full-scale quantum computing
is to utilize the more restricted quantum hardware accessible in the near
future. As a part of this step\, it is desirable to design intermediate-sca
le quantum com putations with robust theoretical guarantees for surpassing
classical computers. To accomplish this\, research over the past decade has
established the hardness of sampling from elementary quantum experiments o
n plausible assumptions. \n\nIn this talk\, I will illustrate several conne
ctions between these assumptions and two other paradigms in physics and mat
hematics. First\, I will focus on quantum pseudo-randomness and explain my
joint contribution (with Aram Harrow QIP 2019) to this area. We settle a co
njecture of BrandĖao-Harrow Horodecki\, which states that random low-depth
quantum circuits on several fundamental architectures are pseudo-random. Th
ese pseudo-random construc tions\, known as t-designs\, have significant ap
plications in quantum information theory and also appear in the study of ch
aotic quantum systems. Notably\, one of the baseline assumptions pertinent
to the hardness of the random circuit sampling experiment\, implemented rec
ently by the Google AI Quantum team\, follows from our result. Next\, I wil
l proceed to a different paradigm\, known as the geometry of analytic funct
ions\, and outline its interfaces with statistical physics and computer sci
ence. I will specifically describe the implications of this evolving field
to the average-case complexity of the permanent polynomial. One of the basi
c assumptions of BosongSampling (recently conducted on scales remarkably la
rger than previous realizations) is that the permanent of Gaussian matrices
with zero mean is hard to approximate. Despite this widely-accepted conjec
ture\, in joint work with Lior Eldar (FOCS 2018)\, we use recent approaches
in the geometry of the zeros of polynomials to design a quasi-polynomial t
ime approximation algorithm for the permanent of complex Gaussian matrices
with unit variance and asymptotically vanishing mean.
DTEND:20210401T200000Z
DTSTAMP:20240423T074119Z
DTSTART:20210401T190000Z
LOCATION:Zoom
SEQUENCE:0
SUMMARY:Pseudo-Randomness\, Complex Zeros of Polynomials\, and Hardness of
Sampling from Small Quantum Devices
UID:tag:localist.com\,2008:EventInstance_35865455273013
URL:https://events.seas.harvard.edu/event/guest_speaker_saeed_mehraban_post
doctoral_scholar_california_institute_of_technology
END:VEVENT
END:VCALENDAR