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 polynomial overhead. Importantly, we must ask: what experimental evidence do we have for this bold assumption? A major effort towards providing such evidence had concentrated on random quantum circuit sampling (RCS) as in the famous supremacy experiment by Google from 2019. I will describe a recent work with Gao, Landau, Liu and Vazirani in which we give a polynomial time classical algorithm for simulating such RCS experiments. Our algorithm gives strong evidence that RCS cannot be the basis for near term experimental evidence for scalable exponential quantum advantage.

A natural alternative is quantum Hamiltonian simulations of highly complex many body quantum evolutions. In a recent work with Zhou, we proved that very simple families of Hamiltonians, even in 1D, are capable of performing universal Hamiltonian simulations. However, as I will explain in the talk, there are inherent difficulties in viewing existing experiments of Hamiltonian simulations as evidence for scalable quantum advantage. So far no (conjectured to be) computationally hard problem was identified and convincingly verified to be solved efficiently by quantum Hamiltonian simulations.

While evidence for scalable quantum advantage is still wanting, initial finite size quantum advantages might be much closer. In the last part of my talk I will describe recent demonstrations on IBM and IONQ quantum devices, performed by my company Qedma's team using Qedma's error mitigation software. These experiments demonstrate unbiased quantum Hamiltonian simulations of unprecedented volumes, suggesting that with devices of 99.9% two-qubit gate fidelities, initial quantum advantages of Hamiltonian simulations can already be demonstrated.

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 Aharonov.