RQC Colloquium

30th RQC Colloquium

• Speaker

  Prof. Dorit Aharonov
  (Hebrew University)

• Date

  16:00-17:00 (JST), January 6, 2025 (Monday)

• Venue

  Online (Zoom)

• Title

  The search for evidence of quantum advantage

• Inquiries

  rqc_colloquium_inquiry[at]ml.riken.jp

• Registration Form

  https://krs2.riken.jp/m/rqc_registration_form

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 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 and follow-up works. I will describe recent work (by Gao, Landau, Liu and Vazirani as well as follow-up works) 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 work with L. Zhou, we proved that very simple families of Hamiltonians, even in 1D, are capable of performing universal Hamiltonian simulations, capable of simulating any other Hamiltonian. However, as I will explain in the talk, there are 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 discuss the notion of finite quantum advantage, in comparison to scalable quantum advantage, and describe recent demonstrations on IBM and IONQ quantum devices, performed by my company Qedma, 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, experimental evidence for finite quantum advantages of Hamiltonian simulations can already be achieved.
Flyer: 30th RQC Colloquium Flyer