Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0409127 · Physical Review A

Noise resistance of adiabatic quantum computation using random matrix theory

Jérémie Roland, Nicolas J. Cerf

Published Mar 21, 2005• 103 citations
arXivHTMLPDF

Abstract

Besides the traditional circuit-based model of quantum computation, several quantum algorithms based on a continuous-time Hamiltonian evolution have recently been introduced, including for instance continuous-time quantum walk algorithms as well as adiabatic quantum algorithms. Unfortunately, very little is known today about the behavior of these Hamiltonian algorithms in the presence of noise. Here, we perform a fully analytical study of the resistance to noise of these algorithms using perturbation theory combined with a theoretical noise model based on random matrices drawn from the Gaussian orthogonal ensemble, whose elements vary in time and form a stationary random process.

DOI
10.1103/physreva.71.032330

Related papers

Quantum search with hybrid adiabatic–quantum-walk algorithms and realistic noise

James G. Morley, Nicholas Chancellor, Sougato Bose +1 more

Computing using a continuous-time evolution, based on the natural interaction Hamiltonian of the quantum computer hardware, is a promising route to building useful quantum computers in the near term. Adiabatic quantum computing, quantum annealing, computation by a continuous-time quantum walk, and special purpose quantum simulators all use this strategy. In this work, we carry out a detailed examination of adiabatic and quantum-walk implementation of the quantum search algorithm, using the more physically realistic hypercube connectivity, rather than the complete graph, for our base Hamiltonian. We calculate optimal adiabatic schedules both analytically and numerically for the hypercube and then interpolate between adiabatic and quantum-walk searching, obtaining a family of hybrid algorithms. We show that all of these hybrid algorithms provide the quadratic quantum speedup when run with optimal parameter settings, which we determine and discuss in detail. We incorporate the effects of multiple runs of the same algorithm, noise applied to the qubits, and two types of problem misspecification, determining the optimal hybrid algorithm for each case. Our results reveal a rich structure of how these different computational mechanisms operate and should be balanced in different scenarios. For large systems with low noise and good control, a quantum walk is the best choice, while hybrid strategies can mitigate the effects of many shortcomings in hardware and problem misspecification.

arXiv:1709.00371•Physical Review A•Feb 28, 2019•49 citations

Random matrix model of adiabatic quantum computing

David R. Mitchell, Christoph Adami, Waynn Lue +1 more

We present an analysis of the quantum adiabatic algorithm for solving hard instances of 3-SAT (an NP-complete problem) in terms of random matrix theory (RMT). We determine the global regularity of the spectral fluctuations of the instantaneous Hamiltonians encountered during the interpolation between the starting Hamiltonians and the ones whose ground states encode the solutions to the computational problems of interest. At each interpolation point, we quantify the degree of regularity of the average spectral distribution via its Brody parameter, a measure that distinguishes regular (i.e., Poissonian) from chaotic (i.e., Wigner-type) distributions of normalized nearest-neighbor spacings. We find that for hard problem instances---i.e., those having a critical ratio of clauses to variables---the spectral fluctuations typically become irregular across a contiguous region of the interpolation parameter, while the spectrum is regular for easy instances. Within the hard region, RMT may be applied to obtain a mathematical model of the probability of avoided level crossings and concomitant failure rate of the adiabatic algorithm due to nonadiabatic Landau-Zener-type transitions. Our model predicts that if the interpolation is performed at a uniform rate, the average failure rate of the quantum adiabatic algorithm, when averaged over hard problem instances, scales exponentially with increasing problem size.

arXiv:quant-ph/0409088•Physical Review A•May 20, 2005•21 citations

Quantum information processing in continuous time

Andrew M. Childs, Edward Farhi

Quantum mechanical computers can solve certain problems asymptotically faster than any classical computing device. Several fast quantum algorithms are known, but the nature of quantum speedup is not well understood, and inventing new quantum algorithms seems to be difficult. In this thesis, we explore two approaches to designing quantum algorithms based on continuous-time Hamiltonian dynamics. In quantum computation by adiabatic evolution, the computer is prepared in the known ground state of a simple Hamiltonian, which is slowly modified so that its ground state encodes the solution to a problem. We argue that this approach should be inherently robust against low-temperature thermal noise and certain control errors, and we support this claim using simulations. We then show that any adiabatic algorithm can be implemented in a different way, using only a sequence of measurements of the Hamiltonian. We illustrate how this approach can achieve quadratic speedup for the unstructured search problem. We also demonstrate two examples of quantum speedup by quantum walk, a quantum mechanical analog of random walk. First, we consider the problem of searching a region

•Jan 1, 2004•91 citations

Computational Complexity Analysis of Quantum Algorithms using Random Matrix Theory

Jincheng Zhang

This paper investigates the application of Random Matrix Theory (RMT) to the analytical complexity assessment of quantum algorithms. Traditional methods for estimating the computational complexity of quantum algorithms often rely on heuristics and approximations, frequently leading to overly pessimistic or overly optimistic results. We propose a novel approach utilizing RMT to model the statistical behavior of quantum circuits. Specifically, we leverage the eigenvalues and eigenvectors of random matrices to characterize the evolution of quantum states under arbitrary quantum circuits. This allows for a more precise estimation of the number of quantum gates (operations) required to achieve a desired level of accuracy in solving a given problem. We demonstrate, through illustrative examples, how RMT can provide tighter and more accurate bounds on the computational complexity compared to conventional techniques. The core claim of this work is that RMT offers a fundamentally new perspective on complexity analysis, promising to reveal deeper insights into the performance characteristics of quantum algorithms and potentially guide the design of more efficient quantum solutions.

•Sep 1, 2026•0 citations

A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem

Edward Farhi, Jeffrey Goldstone, Sam Gutmann +3 more

A quantum system will stay near its instantaneous ground state if the Hamiltonian that governs its evolution varies slowly enough. This quantum adiabatic behavior is the basis of a new class of algorithms for quantum computing. We tested one such algorithm by applying it to randomly generated hard instances of an NP-complete problem. For the small examples that we could simulate, the quantum adiabatic algorithm worked well, providing evidence that quantum computers (if large ones can be built) may be able to outperform ordinary computers on hard sets of instances of NP-complete problems.

arXiv:quant-ph/0104129•Science•Apr 20, 2001•2,100 citations

Adiabatic quantum computing from an eigenvalue dynamics point of view

Richard D. Wilson

We investigate the effects of a generic noise source on a prototypical adiabatic quantum algorithm. We take an alternative eigenvalue dynamics viewpoint and derive a generalised, stochastic form of the Pechukas-Yukawa model. The distribution of avoided crossings in the energy spectra is then analysed in order to estimate the probability of level occupation. \nWe find that the probability of successfully finding the system in the solution state decreases polynomially with the computation speed and that this relationship is independent of the noise amplitude. The overall regularity of the eigenvalue dynamics is shown to be relatively unaffected by noise perturbations. These results imply that adiabatic quantum computation is a relatively stable process and possesses a degree of resistance against the effects of noise. We also show that generic noise will inherently break any symmetries, and therefore remove degeneracies, in the energy spectrum that might otherwise have impeded the computation process. This suggests that the conventional stipulation that the initial and final Hamiltonians do not commute is unnecessary in realistic physical systems. We explore the effects of an artificial noise source with a specifically engineered time-dependent amplitude and show that such a scheme could provide a significant enhancement to the performance of the computation.\nFinally, we formulate an extended version of the Pechukas-Yukawa formalism. This provides a complete description of the dynamics of a quantum system by way of an exact mapping to a system of classical equations of motion.

•Sep 6, 2011•0 citations
Besides the traditional circuit-based model of quantum computation, several quantum algorithms based on a continuous-time Hamiltonian evolution have recently been introduced, including for instance continuous-time quantum walk algorithms as well as adiabatic quantum algorithms. Unfortunately, very little is known today about the behavior of these Hamiltonian algorithms in the presence of noise. Here, we perform a fully analytical study of the resistance to noise of these algorithms using perturbation theory combined with a theoretical noise model based on random matrices drawn from the Gaussian orthogonal ensemble, whose elements vary in time and form a stationary random process.
Computing using a continuous-time evolution, based on the natural interaction Hamiltonian of the quantum computer hardware, is a promising route to building useful quantum computers in the near term. Adiabatic quantum computing, quantum annealing, computation by a continuous-time quantum walk, and special purpose quantum simulators all use this strategy. In this work, we carry out a detailed examination of adiabatic and quantum-walk implementation of the quantum search algorithm, using the more physically realistic hypercube connectivity, rather than the complete graph, for our base Hamiltonian. We calculate optimal adiabatic schedules both analytically and numerically for the hypercube and then interpolate between adiabatic and quantum-walk searching, obtaining a family of hybrid algorithms. We show that all of these hybrid algorithms provide the quadratic quantum speedup when run with optimal parameter settings, which we determine and discuss in detail. We incorporate the effects of multiple runs of the same algorithm, noise applied to the qubits, and two types of problem misspecification, determining the optimal hybrid algorithm for each case. Our results reveal a rich structure of how these different computational mechanisms operate and should be balanced in different scenarios. For large systems with low noise and good control, a quantum walk is the best choice, while hybrid strategies can mitigate the effects of many shortcomings in hardware and problem misspecification.
We present an analysis of the quantum adiabatic algorithm for solving hard instances of 3-SAT (an NP-complete problem) in terms of random matrix theory (RMT). We determine the global regularity of the spectral fluctuations of the instantaneous Hamiltonians encountered during the interpolation between the starting Hamiltonians and the ones whose ground states encode the solutions to the computational problems of interest. At each interpolation point, we quantify the degree of regularity of the average spectral distribution via its Brody parameter, a measure that distinguishes regular (i.e., Poissonian) from chaotic (i.e., Wigner-type) distributions of normalized nearest-neighbor spacings. We find that for hard problem instances---i.e., those having a critical ratio of clauses to variables---the spectral fluctuations typically become irregular across a contiguous region of the interpolation parameter, while the spectrum is regular for easy instances. Within the hard region, RMT may be applied to obtain a mathematical model of the probability of avoided level crossings and concomitant failure rate of the adiabatic algorithm due to nonadiabatic Landau-Zener-type transitions. Our model predicts that if the interpolation is performed at a uniform rate, the average failure rate of the quantum adiabatic algorithm, when averaged over hard problem instances, scales exponentially with increasing problem size.
Quantum mechanical computers can solve certain problems asymptotically faster than any classical computing device. Several fast quantum algorithms are known, but the nature of quantum speedup is not well understood, and inventing new quantum algorithms seems to be difficult. In this thesis, we explore two approaches to designing quantum algorithms based on continuous-time Hamiltonian dynamics. In quantum computation by adiabatic evolution, the computer is prepared in the known ground state of a simple Hamiltonian, which is slowly modified so that its ground state encodes the solution to a problem. We argue that this approach should be inherently robust against low-temperature thermal noise and certain control errors, and we support this claim using simulations. We then show that any adiabatic algorithm can be implemented in a different way, using only a sequence of measurements of the Hamiltonian. We illustrate how this approach can achieve quadratic speedup for the unstructured search problem. We also demonstrate two examples of quantum speedup by quantum walk, a quantum mechanical analog of random walk. First, we consider the problem of searching a region
This paper investigates the application of Random Matrix Theory (RMT) to the analytical complexity assessment of quantum algorithms. Traditional methods for estimating the computational complexity of quantum algorithms often rely on heuristics and approximations, frequently leading to overly pessimistic or overly optimistic results. We propose a novel approach utilizing RMT to model the statistical behavior of quantum circuits. Specifically, we leverage the eigenvalues and eigenvectors of random matrices to characterize the evolution of quantum states under arbitrary quantum circuits. This allows for a more precise estimation of the number of quantum gates (operations) required to achieve a desired level of accuracy in solving a given problem. We demonstrate, through illustrative examples, how RMT can provide tighter and more accurate bounds on the computational complexity compared to conventional techniques. The core claim of this work is that RMT offers a fundamentally new perspective on complexity analysis, promising to reveal deeper insights into the performance characteristics of quantum algorithms and potentially guide the design of more efficient quantum solutions.
A quantum system will stay near its instantaneous ground state if the Hamiltonian that governs its evolution varies slowly enough. This quantum adiabatic behavior is the basis of a new class of algorithms for quantum computing. We tested one such algorithm by applying it to randomly generated hard instances of an NP-complete problem. For the small examples that we could simulate, the quantum adiabatic algorithm worked well, providing evidence that quantum computers (if large ones can be built) may be able to outperform ordinary computers on hard sets of instances of NP-complete problems.
We investigate the effects of a generic noise source on a prototypical adiabatic quantum algorithm. We take an alternative eigenvalue dynamics viewpoint and derive a generalised, stochastic form of the Pechukas-Yukawa model. The distribution of avoided crossings in the energy spectra is then analysed in order to estimate the probability of level occupation. \nWe find that the probability of successfully finding the system in the solution state decreases polynomially with the computation speed and that this relationship is independent of the noise amplitude. The overall regularity of the eigenvalue dynamics is shown to be relatively unaffected by noise perturbations. These results imply that adiabatic quantum computation is a relatively stable process and possesses a degree of resistance against the effects of noise. We also show that generic noise will inherently break any symmetries, and therefore remove degeneracies, in the energy spectrum that might otherwise have impeded the computation process. This suggests that the conventional stipulation that the initial and final Hamiltonians do not commute is unnecessary in realistic physical systems. We explore the effects of an artificial noise source with a specifically engineered time-dependent amplitude and show that such a scheme could provide a significant enhancement to the performance of the computation.\nFinally, we formulate an extended version of the Pechukas-Yukawa formalism. This provides a complete description of the dynamics of a quantum system by way of an exact mapping to a system of classical equations of motion.