We design an adiabatic quantum algorithm for the counting problem, i.e., approximating the proportion, $α$ , of the marked items in a given database. As the quantum system undergoes a designed cyclic adiabatic evolution, it acquires a Berry phase $2πα$ . By estimating the Berry phase, we can approximate $α$ , and solve the problem. For an error bound $ε$ , the algorithm can solve the problem with cost of order $(\frac{1}ε)^{3/2}$ , which is not as good as the optimal algorithm in the quantum circuit model, but better than the classical random algorithm. Moreover, since the Berry phase is a purely geometric feature, the result may be robust to decoherence and resilient to certain noise.We design an adiabatic quantum algorithm for the counting problem, i.e., approximating the proportion, $α$, of the marked items in a given database. As the quantum system undergoes a designed cyclic adiabatic evolution, it acquires a Berry phase $2πα$. By estimating the Berry phase, we can approximate $α$, and solve the problem. For an error bound $ε$, the algorithm can solve the problem with cost of order $(\frac{1}ε)^{3/2}$, which is not as good as the optimal algorithm in the quantum circuit model, but better than the classical random algorithm. Moreover, since the Berry phase is a purely geometric feature, the result may be robust to decoherence and resilient to certain noise.

arXiv:0805.1387May 9, 20080 citations

Uncovering and Circumventing Noise in Quantum Algorithms via Metastability

Antonio Sannia, Pratik Sathe, Luis Pedro García-Pintos

The presence of noise is the primary challenge in realizing fault-tolerant quantum computers. In this work, we introduce and experimentally validate a novel strategy to circumvent noise by exploiting the phenomenon of metastability, where a dynamical system exhibits a separation of time scales in its evolution. We demonstrate that if quantum hardware noise exhibits metastability, both digital and analog algorithms can be designed in a noise-aware fashion to achieve intrinsic resilience. We develop a general theoretical framework and introduce an efficiently computable noise vulnerability metric that avoids the need for full classical simulation of the quantum algorithm. We show that the noise vulnerability index bounds errors in noisy implementations, with smaller values indicating greater fidelity between the achieved and target quantum states. We illustrate the use of our framework with applications to variational quantum algorithms and analog adiabatic state preparation. Crucially, we provide experimental evidence supporting the presence of metastable noise in gate-model quantum processors and quantum annealing devices. Thus, we establish that the noise properties in near-term quantum hardware can directly inform practical implementation strategies, enabling the preparation of final noisy states that more closely approximate the ideal ones.The presence of noise is the primary challenge in realizing fault-tolerant quantum computers. In this work, we introduce and experimentally validate a novel strategy to circumvent noise by exploiting the phenomenon of metastability, where a dynamical system exhibits a separation of time scales in its evolution. We demonstrate that if quantum hardware noise exhibits metastability, both digital and analog algorithms can be designed in a noise-aware fashion to achieve intrinsic resilience. We develop a general theoretical framework and introduce an efficiently computable noise vulnerability metric that avoids the need for full classical simulation of the quantum algorithm. We show that the noise vulnerability index bounds errors in noisy implementations, with smaller values indicating greater fidelity between the achieved and target quantum states. We illustrate the use of our framework with applications to variational quantum algorithms and analog adiabatic state preparation. Crucially, we provide experimental evidence supporting the presence of metastable noise in gate-model quantum processors and quantum annealing devices. Thus, we establish that the noise properties in near-term quantum hardware can directly inform practical implementation strategies, enabling the preparation of final noisy states that more closely approximate the ideal ones.

quant-pharXiv:2511.09821Nov 14, 20250 citations

Resilience–runtime tradeoff relations for quantum algorithms

Luis Pedro García-Pintos, Tom O’Leary, Tanmoy Biswas +4 more

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.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.

arXiv:2408.02764Reports on Progress in PhysicsJan 21, 20250 citations

Noise-resilient quantum circuits

Isaac H. Kim, Brian G. Swingle

Bulletin of the American Physical SocietyMar 7, 20180 citations

Adiabatic processes, noise, and stochastic algorithms for quantum computing and quantum simulation

Guanglei Xu

Jan 1, 20180 citations

We design an adiabatic quantum algorithm for the counting problem, i.e., approximating the proportion,

α

, of the marked items in a given database. As the quantum system undergoes a designed cyclic adiabatic evolution, it acquires a Berry phase

2πα

. By estimating the Berry phase, we can approximate

α

, and solve the problem. For an error bound

ε

, the algorithm can solve the problem with cost of order

(\frac{1}ε)^{3/2}

, which is not as good as the optimal algorithm in the quantum circuit model, but better than the classical random algorithm. Moreover, since the Berry phase is a purely geometric feature, the result may be robust to decoherence and resilient to certain noise.