The Elusive Source of Quantum Speedup

Stephan Hoyer, Mohan Sarovar, K. Birgitta Whaley

It has been suggested that excitation transport in photosynthetic light-harvesting complexes features speedups analogous to those found in quantum algorithms. Here we compare the dynamics in these light-harvesting systems to the dynamics of quantum walks, in order to elucidate the limits of such quantum speedups. For the Fenna–Matthews–Olson complex of green sulfur bacteria, we show that while there is indeed speedup at short times, this is short lived (70 fs) despite longer-lived (ps) quantum coherence. Remarkably, this timescale is independent of the details of the decoherence model. More generally, we show that the distinguishing features of light-harvesting complexes not only limit the extent of quantum speedup but also reduce the rates of diffusive transport. These results suggest that quantum coherent effects in biological systems are optimized for efficiency or robustness rather than the more elusive goal of quantum speedup.

Giuseppe Castagnoli

Salvatore Mandrà, Helmut G. Katzgraber

Abstract There have been multiple attempts to design synthetic benchmark problems with the goal of detecting quantum speedup in current quantum annealing (QA) machines. To date, classical heuristics have consistently outperformed quantum annealing based approaches. Here we introduce a class of problems based on frustrated cluster loops—deceptive cluster loops—for which all currently known state of-the-art classical heuristics are outperformed by the DW2000Q QA machine. While there is a sizable constant speedup over all known classical heuristics, a noticeable improvement in the scaling remains elusive. These results represent the first steps towards a detection of potential quantum speedup, albeit without a scaling improvement and for synthetic benchmark problems.

Bibek Pokharel, Daniel A. Lidar

Despite the development of increasingly capable quantum computers, an experimental demonstration of a provable algorithmic quantum speedup employing today's non-fault-tolerant devices has remained elusive. Here, we unequivocally demonstrate such a speedup within the oracular model, quantified in terms of the scaling with the problem size of the time-to-solution metric. We implement the single-shot Bernstein-Vazirani algorithm, which solves the problem of identifying a hidden bitstring that changes after every oracle query, using two different 27-qubit IBM Quantum superconducting processors. The speedup is observed on only one of the two processors when the quantum computation is protected by dynamical decoupling but not without it. The quantum speedup reported here does not rely on any additional assumptions or complexity-theoretic conjectures and solves a bona fide computational problem in the setting of a game with an oracle and a verifier.

Bill Fefferman