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

Dorit Aharonov is a Professor at the school of computer science and engineering at the Hebrew University of Jerusalem and the CSO of QEDMA quantum computing. In her PhD, Aharonov proved the quantum fault tolerance theorem together with her advisor Ben-Or; this theorem is one of the main pillars of quantum computation today. She later contributed several pioneering works in a variety of areas, including quantum algorithms, specifically quantum walks. quantum adiabatic computation and topologically related algorithms; as well as Hamiltonian complexity, quantum cryptography and quantum verification. Much of her research can be viewed as creating a bridge between physics and computer science, attempting to study fundamental physics questions using computational language. Aharonov was educated at the Hebrew university in Jerusalem (BSc in Mathematics and Physics, PhD in Computer Science and Physics) and then continued to a postdoc at IAS Princeton (Mathematics) and UC Berkeley (Computer Science). She had joined the faculty of the computer science department of the Hebrew university of Jerusalem in 2001. In 2005 Aharonov was featured by the journal Nature as one of four theoreticians making waves in their chosen field; In 2006 she won the Krill prize, and in 2014 she was awarded the Michael Bruno award. In 2020 she joined forces with Dr. Asif Sinay and Prof. Netanel Lindner to co-found QEDMA quantum computing; In parallel, she continues to lead her quantum computation research group at Hebrew university.

Registration

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.