The search for evidence of quantum advantage (45' + 15')

• Dorit Aharonov

**Abstract**: 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 of highly 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 **Short bio**: 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, algorithmic measurements and topologically related quantum algorithms; as well as Hamiltonian complexity and quantum cryptography. 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.