Minimizing estimation runtime on noisy quantum computers*

There is no evidence that NISQ algorithms such as VQE will outperform classical computers for problems of interest. This unfortunate fact urges us to ask: what new insights may be needed to achieve quantum advantage? Towards answering this question we attempt to reconcile two contrasting features of quantum computation: the power of deep-circuit quantum amplification and the reality of imperfect or noisy operating conditions. We present an estimation algorithm tailored to practical implementation by incorporating noise models into its design and optimizing for minimal runtime. We show simulations which demonstrate its advantage over existing techniques. Finally, we demonstrate the long-term impact of this technique for converting device improvement into algorithm performance. As the field of applied quantum computing navigates the evolving hardware, software, and algorithm landscape, these insights may help to find the shortest path to quantum advantage.