Resilience-Runtime Tradeoff Relations for Quantum Algorithms

Published

February 3, 2025

Author(s)

Luis Pedro Garcia-Pintos, Tom O'Leary, Tanmoy Biswas, Jacob Bringewatt, Lukasz Cincio, Lucas Brady, Yi-Kai Liu

Abstract

A leading approach to algorithm design aims to minimize the number of operations in an algorithm's compilation. One intuitively expects that reducing the number of operations may decrease the chance of errors. This paradigm is particularly prevalent in quantum computing, where gates are hard to implement and noise rapidly decreases a quantum computer's potential to outperform classical computers. Here, we find that minimizing the number of operations in a quantum algorithm can be counterproductive, leading to a noise sensitivity that induces errors when running the algorithm in non-ideal conditions. To show this, we develop a framework to characterize the resilience of an algorithm to perturbative noises (including coherent errors, dephasing, and depolarizing noise). Some compilations of an algorithm can be resilient against certain noise sources while being unstable against other noises. We condense these results into a tradeoff relation between an algorithm's number of operations and its noise resilience. We also show how this framework can be leveraged to identify compilations of an algorithm that are better suited to withstand certain noises.

Citation

Reports on Progress in Physics

Pub Type

Journals

Download Paper

https://doi.org/10.1088/1361-6633/adac8b

Local Download

Citation

Garcia-Pintos, L. , O'Leary, T. , Biswas, T. , Bringewatt, J. , Cincio, L. , Brady, L. and Liu, Y. (2025), Resilience-Runtime Tradeoff Relations for Quantum Algorithms, Reports on Progress in Physics, [online], https://doi.org/10.1088/1361-6633/adac8b, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=958438 (Accessed October 20, 2025)