Citation: Babbush, Ryan, et al. "Focus beyond quadratic speedups for error-corrected quantum advantage." PRX quantum 2.1 (2021): 010103.
Web: https://arxiv.org/abs/2011.04149
Tags: Quantum-advantage, Error-correcting-codes:
This paper gives a lovely intuition-honing review of the speedups required for quantum advantage to be real. The authors argue that under realistic assumptions about the future capabilities of quantum computers, it is unlikely that quadratic runtime improvements will be useful. Namely, the breakeven time is expected to be on the order of 100 days even on the most friendly tasks. The point is that quantum primitives are many orders of magnitude slower than classical primitives, and quantum error correction adds a big overhead.
I'm a bit surprised that under their assumptions you already have quantum advantage kicking in at 100 days. This analysis is based on the surface code, which people are making significant progress on moving past. I suspect that better codes could save at least a factor of 10 on the surface code, bringing the breakeaven time down to 1 day. This means that an N-day computation would have a factor of N speedup on quantum computers. I guess this point here is that even as you go past breakeven, on quadratic speedups, the scaling by which you get faster isn't all that good. If you want huge speedups your computations need to run over huge numbers of days.
This point they make that was extra surprising to me is how plausible it is that you can get advantage for super-quadratic speedups. In particular, if you have a quartic speedup it is already completely reasonable that it will give a real advantage on a scaled quantum computer. Not only does the advantage shift from 100 days to 14 seconds, but as you increase the runtime the advantage gets better on a timescale shorter than seconds. Namely, if you ran the algorithm for 1 hour then you would get a speedup factor of 13,824,000. These sorts of speedups are absolutely incomparable with quadratic speedups. If you can beyond quadratic, that's so much better.
A more recent paper emphasizing this perspective is this one:
> Hoefler, Torsten, Thomas Häner, and Matthias Troyer. "Disentangling hype from practicality: On realistically achieving quantum advantage." Communications of the ACM 66.5 (2023): 82-87.