NOTICE: Due to a lapse in annual appropriations, most of this website is not being updated. Learn more.
Form submissions will still be accepted but will not receive responses at this time. Sections of this site for programs using non-appropriated funds (such as NVLAP) or those that are excepted from the shutdown (such as CHIPS and NVD) will continue to be updated.
An official website of the United States government
Here’s how you know
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
Secure .gov websites use HTTPS
A lock (
) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.
Resilience-Runtime Tradeoff Relations for Quantum Algorithms
Published
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.
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 1, 2025)