Specialized Seminar: "The search for evidence of quantum advantage" (Prof. Dr. Dorit Aharonov)

Date: Jan 29, 2024
Time: 01:00 PM (Local Time Germany)
Speaker: Prof. Dr. Dorit Aharonov
Hebrew University, Jerusalem
Location: Max Planck Institute of Quantum Optics
Room: Herbert Walther Lecture Hall
Host: Munich Center for Quantum Science and Technology (MCQST)

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.

Based on recent joint work with Xun Gao, Zeph Landau Yunchao Liu and Umesh Vazirani, arxiv: 2211.03999, QIP 2023, STOC 2023.

This specialized seminar is designed for researchers working in the same field as Dorit Aharonov.
Please register here.