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:0910.1750 · Physical Review A

Decoherence in a dynamical quantum phase transition

Sarah Mostame, Gernot Schaller, Ralf Schützhold

Published Mar 8, 2010• 8 citations
arXivHTMLPDF

Abstract

Motivated by 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, which displays a first-order quantum phase transition. For site-independent and site-dependent coupling strengths as well as different operator couplings, the results show (in contrast to first-order transitions) that the impact of decoherence caused by a weak coupling to a rather general environment increases with system size (i.e., number of spins or qubits). This might limit the scalability of the corresponding adiabatic quantum algorithm.

DOI
10.1103/physreva.81.032305

Related papers

Decoherence in a dynamical quantum phase transition of the transverse Ising chain

Sarah Mostame, Gernot Schaller, Ralf Schützhold

For the prototypical example of the Ising chain in a transverse field, we study the impact of decoherence on the sweep through a second-order quantum phase transition. Apart from the advance in the general understanding of the dynamics of quantum phase transitions, these findings are relevant for adiabatic quantum algorithms due to the similarities between them. It turns out that (in contrast to first-order transitions studied previously) the impact of decoherence caused by a weak coupling to a rather general environment increases with system size (i.e., number of spins or qubits), which might limit the scalability of the system.

arXiv:quant-ph/0703153•Physical Review A•Sep 14, 2007•36 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

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

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

Adiabatic quantum algorithms as quantum phase transitions: First versus second order

Ralf Schützhold, Gernot Schaller

In the continuum limit (large number of qubits), adiabatic quantum algorithms display a remarkable similarity to sweeps through quantum phase transitions. We find that transitions of second or higher order are advantageous in comparison to those of first order. With this insight, we propose an adiabatic quantum algorithm for the solution of 3-satisfiability (3-SAT) problems (exact cover), which is significantly faster than previous proposals according to numerical simulations (up to 20 qubits). These findings suggest that adiabatic quantum algorithms can solve NP-complete problems such as 3-SAT much faster than the Grover search routine (yielding a quadratic enhancement), possibly even with an exponential speedup.

arXiv:quant-ph/0608017•Physical Review A•Dec 28, 2006•82 citations

Decoherence in Grover’s quantum algorithm: Perturbative approach

Hiroo Azuma

In this paper, we study decoherence in Grover's quantum searching algorithm using a perturbative method. We assume that each two-state system (qubit) suffers ${\ensuremath{\sigma}}_{z}$ error with probability $p(0<~p<~1)$ independently at every step in the algorithm. Considering an n-qubit density operator to which Grover's operation is applied M times, we expand it in powers of $2Mnp$ and derive its matrix element order by order under the $\stackrel{\ensuremath{\rightarrow}}{n}\ensuremath{\infty}$ limit. (In this large-n limit, we assume p is small enough, so that $2Mnp(>~0)$ can take any real positive value or $0.)$ This approach gives us an interpretation about creation of new modes caused by ${\ensuremath{\sigma}}_{z}$ error and an asymptotic form of an arbitrary-order correction. Calculating the matrix element up to the fifth-order term numerically, we investigate a region of $2Mnp$ (perturbative parameter), where the algorithm finds the correct item with a threshold of probability ${P}_{\mathrm{th}}$ or more. It satisfies $2Mnp<(8/5)(1\ensuremath{-}{P}_{\mathrm{th}})$ around $2Mnp\ensuremath{\simeq}0$ and ${P}_{\mathrm{th}}\ensuremath{\simeq}1,$ and this linear relation is applied to a wide range of ${P}_{\mathrm{th}}$ approximately. This observation is similar to a result obtained by Bernstein and Vazirani concerning accuracy of quantum gates for general algorithms. We cannot investigate a quantum-to-classical phase transition of the algorithm, because it is outside the reliable domain of our perturbation theory.

arXiv:quant-ph/0110101•Physical Review A•Apr 1, 2002•27 citations
Motivated by 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, which displays a first-order quantum phase transition. For site-independent and site-dependent coupling strengths as well as different operator couplings, the results show (in contrast to first-order transitions) that the impact of decoherence caused by a weak coupling to a rather general environment increases with system size (i.e., number of spins or qubits). This might limit the scalability of the corresponding adiabatic quantum algorithm.
For the prototypical example of the Ising chain in a transverse field, we study the impact of decoherence on the sweep through a second-order quantum phase transition. Apart from the advance in the general understanding of the dynamics of quantum phase transitions, these findings are relevant for adiabatic quantum algorithms due to the similarities between them. It turns out that (in contrast to first-order transitions studied previously) the impact of decoherence caused by a weak coupling to a rather general environment increases with system size (i.e., number of spins or qubits), which might limit the scalability of the system.
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.
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.
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.
In the continuum limit (large number of qubits), adiabatic quantum algorithms display a remarkable similarity to sweeps through quantum phase transitions. We find that transitions of second or higher order are advantageous in comparison to those of first order. With this insight, we propose an adiabatic quantum algorithm for the solution of 3-satisfiability (3-SAT) problems (exact cover), which is significantly faster than previous proposals according to numerical simulations (up to 20 qubits). These findings suggest that adiabatic quantum algorithms can solve NP-complete problems such as 3-SAT much faster than the Grover search routine (yielding a quadratic enhancement), possibly even with an exponential speedup.
In this paper, we study decoherence in Grover's quantum searching algorithm using a perturbative method. We assume that each two-state system (qubit) suffers ${\ensuremath{\sigma}}_{z}$ error with probability p(0< p< 1)p(0<~p<~1)p(0< p< 1) independently at every step in the algorithm. Considering an n-qubit density operator to which Grover's operation is applied M times, we expand it in powers of 2Mnp2Mnp2Mnp and derive its matrix element order by order under the $\stackrel{\ensuremath{\rightarrow}}{n}\ensuremath{\infty}$ limit. (In this large-n limit, we assume p is small enough, so that 2Mnp(> 0)2Mnp(>~0)2Mnp(> 0) can take any real positive value or 0.)0.)0.) This approach gives us an interpretation about creation of new modes caused by ${\ensuremath{\sigma}}_{z}$ error and an asymptotic form of an arbitrary-order correction. Calculating the matrix element up to the fifth-order term numerically, we investigate a region of 2Mnp2Mnp2Mnp (perturbative parameter), where the algorithm finds the correct item with a threshold of probability Pth{P}_{\mathrm{th}}Pth​ or more. It satisfies $2Mnp<(8/5)(1\ensuremath{-}{P}_{\mathrm{th}})$ around $2Mnp\ensuremath{\simeq}0$ and ${P}_{\mathrm{th}}\ensuremath{\simeq}1,$ and this linear relation is applied to a wide range of Pth{P}_{\mathrm{th}}Pth​ approximately. This observation is similar to a result obtained by Bernstein and Vazirani concerning accuracy of quantum gates for general algorithms. We cannot investigate a quantum-to-classical phase transition of the algorithm, because it is outside the reliable domain of our perturbation theory.