MilestoneTheory & algorithmsConfirmed

Classical algorithm suggests noisy random circuit sampling cannot scale

Nov 8, 2022

Dorit Aharonov, Umesh Vazirani and colleagues give a classical algorithm that efficiently imitates noisy random quantum circuits as they grow. The algorithm is not practical yet and does not address finite-size experiments such as Google's 2019 test.

Why it matters

Random circuit sampling was the task behind the first quantum supremacy claims. The result suggests that, with a fixed noise rate per gate, it cannot keep beating classical computers at scale.

Dorit Aharonov · Xun Gao · Zeph Landau · Yunchao Liu · Umesh Vazirani · Hebrew University · UC Berkeley

See it on the timeline

Related

• Google researchers propose random circuit sampling to show quantum supremacy (Jul 31, 2016)
• Google claims quantum supremacy with its 53-qubit Sycamore processor (Oct 23, 2019)
• Classical computers catch up with Google's 2019 quantum supremacy task (Nov 4, 2021)