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/0608123 · Physical Review A

Non-Markovian decoherence in the adiabatic quantum search algorithm

Markus Tiersch, Ralf Schützhold

Published Jun 12, 2007• 41 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.75.062313

Related papers

Decoherence in a dynamical quantum phase transition

Sarah Mostame, Gernot Schaller, Ralf Schützhold

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.

arXiv:0910.1750•Physical Review A•Mar 8, 2010•8 citations

Accelerated adiabatic quantum search algorithm via pulse control in a non-Markovian environment

Feng-Hua Ren, Zhao-Ming Wang, Lian-Ao Wu

Adiabatic quantum computation requires that the system remains in its ground state. However, an adiabatic process often loses partly or entirely its quantumness, such as entanglement in its long runtime, due to the system-environment interactions. Here we put forward an effective quantum control technique to realize the adiabatic quantum search algorithm in a nonadiabatic regime and in the presence of environment. Using the non-Markovian quantum state diffusion equation approach, we numerically study the system dynamics characterized by the success probability. The results show that the probability increases with decreasing coupling strength and temperature. In particular, non-Markovianity from the environment can help to enhance the success probability. By choosing a suitable pulse intensity and period, a high success probability can be obtained in a short runtime for weak system-bath coupling, low temperature, and strong non-Markovian heat baths.

Physical Review A•Dec 4, 2020•18 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

Role of single-qubit decoherence time in adiabatic quantum computation

M. H. S. Amin, C. J. S. Truncik, D. V. Averin

We have studied numerically the evolution of an adiabatic quantum computer in the presence of a Markovian Ohmic environment by considering Ising spin-glass systems with up to 20 qubits independently coupled to this environment via two conjugate degrees of freedom. The required computation time is demonstrated to be of the same order as that for an isolated system and is not limited by the single-qubit decoherence time ${T}_{2}^{\ensuremath{\ast}}$, even when the minimum gap is much smaller than the temperature and decoherence-induced level broadening. For small minimum gap, the system can be described by an effective two-state model coupled only longitudinally to environment.

arXiv:0803.1196•Physical Review A•Aug 4, 2009•63 citations

Quantum search in a non-Markovian environment

Sheikh Parvez Mandal

This MS thesis explores the effects and origins of a 'noise with memory' in the dynamics of an open quantum system. The system considered here is a multi-qubit register performing the Grover's quantum search algorithm. We show that a Markovian-correlated noise can enhance the efficiency of the algorithm over a time correlation-less noise. We also analytically find the set of necessary and sufficient conditions for the algorithm's success probability to remain invariant with respect to the number of noisy sites in the register and point out that these conditions hold irrespective of the presence of time-correlations in the noise. We then investigate the origins of the type of noise considered. In this regard, a 'collisional model' is constructed that exactly reproduces the noisy evolution of the open system. Non-Markovianity in the system's evolution is then assessed using two well-known measures and they are shown to be non-coincident. Our model is then slightly modified to accommodate an elementary thermal bath. There we show that increasing the bath's temperature increases information drainage from the system.

arXiv:2303.14121•Mar 23, 2023•0 citations

Convergence Guarantees for Discrete Mode Approximations to Non-Markovian Quantum Baths

Rahul Trivedi, Daniel Malz, J. Ignacio Cirac

Non-Markovian effects are important in modeling the behavior of open quantum systems arising in solid-state physics, quantum optics as well as in study of biological and chemical systems. The non-Markovian environment is often approximated by discrete bosonic modes, thus mapping it to a Lindbladian or Hamiltonian simulation problem. While systematic constructions of such modes have been previously proposed, the resulting approximation lacks rigorous and general convergence guarantees. In this Letter, we show that under some physically motivated assumptions on the system-environment interaction, the finite-time dynamics of the non-Markovian open quantum system computed with a sufficiently large number of modes is guaranteed to converge to the true result. Furthermore, we show that this approximation error typically falls off polynomially with the number of modes. Our results lend rigor to classical and quantum algorithms for approximating non-Markovian dynamics.

arXiv:2107.07196•Physical Review Letters•Dec 15, 2021•20 citations
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.
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.
Adiabatic quantum computation requires that the system remains in its ground state. However, an adiabatic process often loses partly or entirely its quantumness, such as entanglement in its long runtime, due to the system-environment interactions. Here we put forward an effective quantum control technique to realize the adiabatic quantum search algorithm in a nonadiabatic regime and in the presence of environment. Using the non-Markovian quantum state diffusion equation approach, we numerically study the system dynamics characterized by the success probability. The results show that the probability increases with decreasing coupling strength and temperature. In particular, non-Markovianity from the environment can help to enhance the success probability. By choosing a suitable pulse intensity and period, a high success probability can be obtained in a short runtime for weak system-bath coupling, low temperature, and strong non-Markovian heat baths.
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 have studied numerically the evolution of an adiabatic quantum computer in the presence of a Markovian Ohmic environment by considering Ising spin-glass systems with up to 20 qubits independently coupled to this environment via two conjugate degrees of freedom. The required computation time is demonstrated to be of the same order as that for an isolated system and is not limited by the single-qubit decoherence time ${T}_{2}^{\ensuremath{\ast}}$, even when the minimum gap is much smaller than the temperature and decoherence-induced level broadening. For small minimum gap, the system can be described by an effective two-state model coupled only longitudinally to environment.
This MS thesis explores the effects and origins of a 'noise with memory' in the dynamics of an open quantum system. The system considered here is a multi-qubit register performing the Grover's quantum search algorithm. We show that a Markovian-correlated noise can enhance the efficiency of the algorithm over a time correlation-less noise. We also analytically find the set of necessary and sufficient conditions for the algorithm's success probability to remain invariant with respect to the number of noisy sites in the register and point out that these conditions hold irrespective of the presence of time-correlations in the noise. We then investigate the origins of the type of noise considered. In this regard, a 'collisional model' is constructed that exactly reproduces the noisy evolution of the open system. Non-Markovianity in the system's evolution is then assessed using two well-known measures and they are shown to be non-coincident. Our model is then slightly modified to accommodate an elementary thermal bath. There we show that increasing the bath's temperature increases information drainage from the system.
Non-Markovian effects are important in modeling the behavior of open quantum systems arising in solid-state physics, quantum optics as well as in study of biological and chemical systems. The non-Markovian environment is often approximated by discrete bosonic modes, thus mapping it to a Lindbladian or Hamiltonian simulation problem. While systematic constructions of such modes have been previously proposed, the resulting approximation lacks rigorous and general convergence guarantees. In this Letter, we show that under some physically motivated assumptions on the system-environment interaction, the finite-time dynamics of the non-Markovian open quantum system computed with a sufficiently large number of modes is guaranteed to converge to the true result. Furthermore, we show that this approximation error typically falls off polynomially with the number of modes. Our results lend rigor to classical and quantum algorithms for approximating non-Markovian dynamics.