MilestoneTheory & algorithmsConfirmed

Error-correction costs challenge early gains from quadratic quantum speedups

Nov 9, 2020

Ryan Babbush and colleagues estimate that fixing quantum errors can outweigh the time saved by algorithms such as Grover’s search on early error-corrected machines. They account for the cost of quantum operations and compare with classical computers working in parallel.

Why it matters

An algorithm that needs fewer steps can still take longer to run, so error correction and fast classical hardware must be included when estimating a useful quantum advantage.

Ryan Babbush · Jarrod McClean · Craig Gidney · Google

See it on the timeline

Related

• Lov Grover finds a quantum algorithm for faster unstructured search (May 1996)
• Researchers estimate quantum resources for nitrogen-fixation chemistry (May 11, 2016)