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:1606.01898 · Physical Review Letters

Adiabatic Quantum Search in Open Systems

Dominik S. Wild, Sarang Gopalakrishnan, Michael Knap, Norman Y. Yao, Mikhail D. Lukin

Published Oct 6, 2016• 28 citations
arXivHTMLPDF

Abstract

Adiabatic quantum algorithms represent a promising approach to universal quantum computation. In isolated systems, a key limitation to such algorithms is the presence of avoided level crossings, where gaps become extremely small. In open quantum systems, the fundamental robustness of adiabatic algorithms remains unresolved. Here, we study the dynamics near an avoided level crossing associated with the adiabatic quantum search algorithm, when the system is coupled to a generic environment. At zero temperature, we find that the algorithm remains scalable provided the noise spectral density of the environment decays sufficiently fast at low frequencies. By contrast, higher order scattering processes render the algorithm inefficient at any finite temperature regardless of the spectral density, implying that no quantum speedup can be achieved. Extensions and implications for other adiabatic quantum algorithms will be discussed.

DOI
10.1103/physrevlett.117.150501

Related papers

Quantum search at low temperature in the singleavoided crossing model

Parth Patel

We begin with an n-qubit quantum search algorithm and formulate it in terms of quantum walk and adiabatic quantum computation. We then represent and transform the n-qubit search algorithm into a two-level system and hence the single avoided crossing model. We perform and present the analytical calculations and numerical simulations of the dynamics of quantum walk search algorithm and AQC search algorithm in a thermal bath. We use the master equations formulation to represent the open quantum system. We nd out that while generally the performance of algorithms worsen with increase in temperature and the system size, there are interesting features in quantum walk search where there is an optimal low temperature for the best performance for other specied parameters. Similarly for AQC search, the performance generally worsens with increase in temperature, but for specied parameter ranges, the system is more robust against temperature eects.

•Jan 1, 2019•0 citations

Quantum Zeno effect versus adiabatic quantum computing and quantum annealing

Naser Ahmadiniaz, Dennis Kraft, Gernot Schaller +1 more

Abstract For the adiabatic version of Grover’s quantum search algorithm as proposed by Roland and Cerf, we study the impact of decoherence caused by a rather general coupling to some environment. For quite generic conditions, we find that the quantum Zeno effect poses strong limitations on the performance (quantum speed-up) since the environment effectively measures the state of the system permanently and thereby inhibits or slows down quantum transitions. Generalizing our results, we find that similar restrictions should apply universally to adiabatic quantum algorithms and quantum annealing schemes which are based on analogous isolated Landau–Zener type transitions at avoided level crossings (similar to first-order phase transitions). As a possible resort, more gradual changes of the quantum state (as in second-order phase transitions) or suitable error-correcting schemes such as the spin-echo method may alleviate this problem.

arXiv:2509.04057•New Journal of Physics•May 15, 2026•1 citation

Unstructured Adiabatic Quantum Optimization: Optimality with Limitations

Arthur Braida, Shantanav Chakraborty, Alapan Chaudhuri +4 more

In the circuit model of quantum computing, amplitude amplification techniques can be used to find solutions to NP-hard problems defined on n -bits in time poly(n)2n/2 . In this work, we investigate whether such general statements can be made for adiabatic quantum optimization, as provable results regarding its performance are mostly unknown. Although a lower bound of Ω(2n/2) has existed in such a setting for over a decade, a purely adiabatic algorithm with this running time has been absent. We show that adiabatic quantum optimization using an unstructured search approach results in a running time that matches this lower bound (up to a polylogarithmic factor) for a broad class of classical local spin Hamiltonians. For this, it is necessary to bound the spectral gap throughout the adiabatic evolution and compute beforehand the position of the avoided crossing with sufficient precision so as to adapt the adiabatic schedule accordingly. However, we show that the position of the avoided crossing is approximately given by a quantity that depends on the degeneracies and inverse gaps of the problem Hamiltonian and is NP-hard to compute even within a low additive precision. Furthermore, computing it exactly (or nearly exactly) is #P-hard. Our work indicates a possible limitation of adiabatic quantum optimization algorithms, leaving open the question of whether provable Grover-like speed-ups can be obtained for any optimization problem using this approach.

arXiv:2411.05736•Quantum•Jul 11, 2025•10 citations

On Quantum Simulators and Adiabatic Quantum Algorithms

Sarah Mostame

This Thesis focuses on different aspects of quantum computation theory: adiabatic quantum algorithms, decoherence during the adiabatic evolution and quantum simulators. After an overview on the area of quantum computation and setting up the formal ground for the rest of the Thesis we derive a general error estimate for adiabatic quantum computing. We demonstrate that the first-order correction, which has frequently been used as a condition for adiabatic quantum computation, does not yield a good estimate for the computational error. Therefore, a more general criterion is proposed, which includes higher-order corrections and shows that the computational error can be made exponentially small – which facilitates significantly shorter evolution times than the first-order estimate in certain situations. Based on this criterion and rather general arguments and assumptions, it can be demonstrated that a run-time of order of the inverse minimum energy gap is sufficient and necessary. Furthermore, exploiting the similarity between adiabatic quantum algorithms and quantum phase transitions, we study the impact of decoherence on the sweep through a second-order quantum phase transition for the prototypical example of the Ising chain in a transverse field and compare it to the adiabatic version of Grover’s search algorithm. It turns out that (in contrast to first-order transitions) the impact of decoherence caused by a weak coupling to a rather general environment increases with system size (i.e., number of spins/qubits), which might limit the scalability of the system. Finally, we propose the use of electron systems to construct laboratory systems based on present-day technology which reproduce and thereby simulate the quantum dynamics of the Ising model and the O(3) nonlinear sigma model.

•Oct 2, 2008•0 citations

Non-Markovian decoherence in the adiabatic quantum search algorithm

Markus Tiersch, Ralf Schützhold

We consider an adiabatic quantum algorithm (Grover's search routine) weakly coupled to a rather general environment, i.e., without using the Markov approximation. Markovian errors generally require high-energy excitations (of the reservoir) and tend to destroy the scalability of the adiabatic quantum algorithm. We find that, under appropriate conditions (such as low temperatures), the low-energy (i.e., non-Markovian) modes of the bath are most important. It turns out that the scalability of the adiabatic quantum algorithm just depends on the infrared behavior of the environment: a reasonably small coupling to the three-dimensional electromagnetic field, for example, does not destroy the scaling behavior, whereas phonons or localized degrees of freedom can be problematic.

arXiv:quant-ph/0608123•Physical Review A•Jun 12, 2007•43 citations

Avoided crossings in spin-boson systems: consequences for adiabatic state preparation

Joona Marjamäki, Robert van Leeuwen, Riku Tuovinen

Avoided crossings in the correlated many-body spectrum play a central role in determining the conditions for adiabatic state preparation in interacting quantum systems. We investigate this connection in finite spin-boson systems by combining exact diagonalization of the many-body spectrum with time-dependent simulations of adiabatic switching protocols. By comparing the adiabatically prepared state with the exact ground state, we determine the switching times required for reliable preparation as a function of the spin-boson coupling strength and bosonic mode structure. We show that regions of small many-body level spacings, associated with avoided crossings, impose the strongest constraints on adiabatic preparation and explain the observed dependence of the required switching times on the interaction strength. Furthermore, while the ground-state energy follows the overall spectral trends, local observables such as Pauli matrix expectation values exhibit additional non-monotonic behavior arising from coherent oscillations in finite systems. These findings can provide concrete benchmarks for both the theoretical treatment of open quantum systems and practical implementations in quantum simulation and qubit control.

quant-pharXiv:2609.29858•Sep 25, 2026•0 citations
Adiabatic quantum algorithms represent a promising approach to universal quantum computation. In isolated systems, a key limitation to such algorithms is the presence of avoided level crossings, where gaps become extremely small. In open quantum systems, the fundamental robustness of adiabatic algorithms remains unresolved. Here, we study the dynamics near an avoided level crossing associated with the adiabatic quantum search algorithm, when the system is coupled to a generic environment. At zero temperature, we find that the algorithm remains scalable provided the noise spectral density of the environment decays sufficiently fast at low frequencies. By contrast, higher order scattering processes render the algorithm inefficient at any finite temperature regardless of the spectral density, implying that no quantum speedup can be achieved. Extensions and implications for other adiabatic quantum algorithms will be discussed.
We begin with an n-qubit quantum search algorithm and formulate it in terms of quantum walk and adiabatic quantum computation. We then represent and transform the n-qubit search algorithm into a two-level system and hence the single avoided crossing model. We perform and present the analytical calculations and numerical simulations of the dynamics of quantum walk search algorithm and AQC search algorithm in a thermal bath. We use the master equations formulation to represent the open quantum system. We nd out that while generally the performance of algorithms worsen with increase in temperature and the system size, there are interesting features in quantum walk search where there is an optimal low temperature for the best performance for other specied parameters. Similarly for AQC search, the performance generally worsens with increase in temperature, but for specied parameter ranges, the system is more robust against temperature eects.
Abstract For the adiabatic version of Grover’s quantum search algorithm as proposed by Roland and Cerf, we study the impact of decoherence caused by a rather general coupling to some environment. For quite generic conditions, we find that the quantum Zeno effect poses strong limitations on the performance (quantum speed-up) since the environment effectively measures the state of the system permanently and thereby inhibits or slows down quantum transitions. Generalizing our results, we find that similar restrictions should apply universally to adiabatic quantum algorithms and quantum annealing schemes which are based on analogous isolated Landau–Zener type transitions at avoided level crossings (similar to first-order phase transitions). As a possible resort, more gradual changes of the quantum state (as in second-order phase transitions) or suitable error-correcting schemes such as the spin-echo method may alleviate this problem.
In the circuit model of quantum computing, amplitude amplification techniques can be used to find solutions to NP-hard problems defined on n -bits in time poly(n)2n/2 . In this work, we investigate whether such general statements can be made for adiabatic quantum optimization, as provable results regarding its performance are mostly unknown. Although a lower bound of Ω(2n/2) has existed in such a setting for over a decade, a purely adiabatic algorithm with this running time has been absent. We show that adiabatic quantum optimization using an unstructured search approach results in a running time that matches this lower bound (up to a polylogarithmic factor) for a broad class of classical local spin Hamiltonians. For this, it is necessary to bound the spectral gap throughout the adiabatic evolution and compute beforehand the position of the avoided crossing with sufficient precision so as to adapt the adiabatic schedule accordingly. However, we show that the position of the avoided crossing is approximately given by a quantity that depends on the degeneracies and inverse gaps of the problem Hamiltonian and is NP-hard to compute even within a low additive precision. Furthermore, computing it exactly (or nearly exactly) is #P-hard. Our work indicates a possible limitation of adiabatic quantum optimization algorithms, leaving open the question of whether provable Grover-like speed-ups can be obtained for any optimization problem using this approach.
This Thesis focuses on different aspects of quantum computation theory: adiabatic quantum algorithms, decoherence during the adiabatic evolution and quantum simulators. After an overview on the area of quantum computation and setting up the formal ground for the rest of the Thesis we derive a general error estimate for adiabatic quantum computing. We demonstrate that the first-order correction, which has frequently been used as a condition for adiabatic quantum computation, does not yield a good estimate for the computational error. Therefore, a more general criterion is proposed, which includes higher-order corrections and shows that the computational error can be made exponentially small – which facilitates significantly shorter evolution times than the first-order estimate in certain situations. Based on this criterion and rather general arguments and assumptions, it can be demonstrated that a run-time of order of the inverse minimum energy gap is sufficient and necessary. Furthermore, exploiting the similarity between adiabatic quantum algorithms and quantum phase transitions, we study the impact of decoherence on the sweep through a second-order quantum phase transition for the prototypical example of the Ising chain in a transverse field and compare it to the adiabatic version of Grover’s search algorithm. It turns out that (in contrast to first-order transitions) the impact of decoherence caused by a weak coupling to a rather general environment increases with system size (i.e., number of spins/qubits), which might limit the scalability of the system. Finally, we propose the use of electron systems to construct laboratory systems based on present-day technology which reproduce and thereby simulate the quantum dynamics of the Ising model and the O(3) nonlinear sigma model.
We consider an adiabatic quantum algorithm (Grover's search routine) weakly coupled to a rather general environment, i.e., without using the Markov approximation. Markovian errors generally require high-energy excitations (of the reservoir) and tend to destroy the scalability of the adiabatic quantum algorithm. We find that, under appropriate conditions (such as low temperatures), the low-energy (i.e., non-Markovian) modes of the bath are most important. It turns out that the scalability of the adiabatic quantum algorithm just depends on the infrared behavior of the environment: a reasonably small coupling to the three-dimensional electromagnetic field, for example, does not destroy the scaling behavior, whereas phonons or localized degrees of freedom can be problematic.
Avoided crossings in the correlated many-body spectrum play a central role in determining the conditions for adiabatic state preparation in interacting quantum systems. We investigate this connection in finite spin-boson systems by combining exact diagonalization of the many-body spectrum with time-dependent simulations of adiabatic switching protocols. By comparing the adiabatically prepared state with the exact ground state, we determine the switching times required for reliable preparation as a function of the spin-boson coupling strength and bosonic mode structure. We show that regions of small many-body level spacings, associated with avoided crossings, impose the strongest constraints on adiabatic preparation and explain the observed dependence of the required switching times on the interaction strength. Furthermore, while the ground-state energy follows the overall spectral trends, local observables such as Pauli matrix expectation values exhibit additional non-monotonic behavior arising from coherent oscillations in finite systems. These findings can provide concrete benchmarks for both the theoretical treatment of open quantum systems and practical implementations in quantum simulation and qubit control.