17 October 2023
from 14:30 to 16:00
CANCELLED: Specialized seminar by Distinguished Lecturer Prof. Dorit Aharonov.
Address / Location
Max Planck Institute of Quantum Optics
Due to the current situation in Israel, we have to unfortunately postpone the public talk until further notice.
As MCQST Distinguished Lecturer, Prof. Dorit Aharonov is giving a series of talks targeted to varied audiences. This specialized seminar is designed for researchers working in the same field.
The search for evidence of quantum advantage
The field of quantum computation heavily relies on the belief that quantum computation violates the extended Church Turing thesis, namely,
that quantum many-body systems cannot be simulated by classical ones with only polynomially growing overhead. Importantly, we must ask: what experimental evidence do we have for this assumption? A natural candidate for such evidence is quantum simulations ofhighly complex many body quantum evolutions. However there are inherent difficulties in viewing such simulations as providing evidence for quantum advantage. Assuming the high complexity regimes of quantum systems are hard to simulate classically, verification of quantum evolution requires either exponential time or sophisticated interactive protocols; unfortunately, so far no (conjectured to be) computationally hard problem was identified and verified to be solved by quantum simulations.
A major effort towards providing such evidence for scalable quantum advantage have concentrated in the past decade on quantum random circuit sampling (RCS); such is the famous supremacy experiment by Google from 2019. The RCS experiments can be modeled as sampling from a random quantum circuit where each gate is subject to a small amount of noise. I will describe a recent work in which we give a polynomial time classical algorithm for sampling from the output distribution of a noisy random quantum circuit under an anti-concentration assumption, to within inverse polynomial total variation distance. It should be noted that our algorithm is not practical in its current form, and does not address finite-size RCS based quantum supremacy experiments. Nevertheless our result gives strong evidence that random circuit sampling (RCS) cannot be the basis of a scalable experimental violation of the extended Church-Turing thesis. I will end with a discussion regarding the prospects of providing evidence for scalable violation of the ECTT in the pre-quantum fault tolerance era (also known as NISQ era).
Based on recent joint work with Xun Gao, Zeph Landau Yunchao Liu and Umesh Vazirani, arxiv: 2211.03999, QIP 2023, STOC 2023.
About Dorit Aharonov
This specialized seminar is designed for researchers working in the same field as Dorit Aharanov.
After the talk, there will the possibility for further discussion over coffee and cake. Please register by 15. October.