论文标题
超越二次加速器以获得错误校正的量子优势
Focus beyond quadratic speedups for error-corrected quantum advantage
论文作者
论文摘要
从这个角度来看，我们讨论了一个条件，在这些条件下，适度的容忍量子计算机可以通过在最佳的经典替代方案中执行量子算法来实现运行时优势。面临的挑战是，计算必须在合理的时间内完成，同时足够困难，以使较小的量度比例优势可以补偿与错误校正相关的大型恒定因子开销。我们使用最先进的表面代码构造在各种假设下计算了此类运行时间的几个示例。我们得出的结论是，除非我们如何实现量子误差校正有显着改善，否则二次加速器将无法在此类容忍故障的设备的早期获得量子优势。尽管该结论仍然存在，即使我们要将表面代码中逻辑门的速率提高不止一个数量级，但我们还以其他多项式程度重复了此分析，并发现四分之一的加速看起来更实用。
In this perspective, we discuss conditions under which it would be possible for a modest fault-tolerant quantum computer to realize a runtime advantage by executing a quantum algorithm with only a small polynomial speedup over the best classical alternative. The challenge is that the computation must finish within a reasonable amount of time while being difficult enough that the small quantum scaling advantage would compensate for the large constant factor overheads associated with error-correction. We compute several examples of such runtimes using state-of-the-art surface code constructions under a variety of assumptions. We conclude that quadratic speedups will not enable quantum advantage on early generations of such fault-tolerant devices unless there is a significant improvement in how we would realize quantum error-correction. While this conclusion persists even if we were to increase the rate of logical gates in the surface code by more than an order of magnitude, we also repeat this analysis for speedups by other polynomial degrees and find that quartic speedups look significantly more practical.
