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:0901.4954

A note on adiabatic theorem for Markov chains and adiabatic quantum computation

Yevgeniy Kovchegov

Published Jan 30, 2009• 0 citations
arXivHTMLPDF

Abstract

We derive an adiabatic theorem for Markov chains using well known facts about mixing and relaxation times. We discuss the results in the context of the recent developments in adiabatic quantum computation.
DOI
10.48550/arxiv.0901.4954

Related papers

INTRODUCING ADIABATIC QUANTUM COMPUTATION

Huazhong Li

Recent applications of quantum adiabatic approximation to quantum computation are reviewed.We discuss the adiabatic quantum algorithm and the recent discovery of inconsistency of quantum adiabatic theorem giving impact to this application.

Progress in physics•Jan 1, 2008•0 citations

Consistency of the Adiabatic Theorem

M. H. S. Amin

The adiabatic theorem provides the basis for the adiabatic model of quantum computation. Recently the conditions required for the adiabatic theorem to hold have become a subject of some controversy. Here we show that the reported violations of the adiabatic theorem all arise from resonant transitions between energy levels. In the absence of fast driven oscillations the traditional adiabatic theorem holds. Implications for adiabatic quantum computation are discussed.

arXiv:0810.4335•Physical Review Letters•Jun 3, 2009•186 citations

Reexamination of the quantum adiabatic theorem

Yan Zhao

The quantum adiabatic theorem is a widely applied result in quantum mechanics. However, recently, counterexamples were produced, indicating that the transition probabilities in some systems do not converge as predicted by the adiabatic theorem [K. P. Marzlin and B. C. Sanders, Phys. Rev. Lett. 93, 160408 (2004)]. In this paper, we examine a proof of the adiabatic theorem, paying specific attention to the validity of the assumptions made in the proof. We show that the convergence of the transition probabilities is path dependent when the change in the Hamiltonian is large. Finally, we consider the application of this reformulated form of the adiabatic theorem to the adiabatic evolution paradigm in quantum computation.

Physical Review A•Mar 21, 2008•23 citations

Adiabatic quantum computation

Lukáš Charamza

In this thesis we summarize the principles of quantum computing. We specifically consider adiabatic quantum computing, whose principles are explained and shown on several examples. To explain the principle of adiabatic quantum computing we review the adiabatic theorem. We also outline possibility of using a particular Hamiltonian by Berry, which enables us to evolve system adiabatically in arbitrarily short time. In the final part of this thesis, we explain the concept of quantum phase transitions. We discuss a relationship between quantum phase transitions and adiabatic quantum computing and show that adiabatic quantum computing scales polynomially with the number of qubits only for quantum phase transitions of second or higher order. Powered by TCPDF (www.tcpdf.org)

•Jan 1, 2014•0 citations

Quantum Computation, Markov Chains and Combinatorial Optimisation

Danial Dervovic

This thesis addresses two questions related to the title, Quantum Computation, Markov Chains and Combinatorial Optimisation. The first question involves an algorithmic primitive of quantum computation, quantum walks on graphs, and its relation to Markov Chains. Quantum walks have been shown in certain cases to mix faster than their classical counterparts. Lifted Markov chains, consisting of a Markov chain on an extended state space which is projected back down to the original state space, also show considerable speedups in mixing time. We design a lifted Markov chain that in some sense simulates any quantum walk. Concretely, we construct a lifted Markov chain on a connected graph G with n vertices that mixes exactly to the average mixing distribution of a quantum walk on G. Moreover, the mixing time of this chain is the diameter of G. We then consider practical consequences of this result. In the second part of this thesis we address a classic unsolved problem in combinatorial optimisation, graph isomorphism. A theorem of Kozen states that two graphs on n vertices are isomorphic if and only if there is a clique of size n in the weak modular product of the two graphs. Furthermore, a straightforward corollary of this theorem and Lovász’s sandwich theorem is if the weak modular product between two graphs is perfect, then checking if the graphs are isomorphic is polynomial in n. We enumerate the necessary and sufficient conditions for the weak modular product of two simple graphs to be perfect. Interesting cases include complete multipartite graphs and disjoint unions of cliques. We find that all perfect weak modular products have factors that fall into classes of graphs for which testing isomorphism is already known to be polynomial in the number of vertices. Open questions and further research directions are discussed.

•Mar 28, 2020•1 citation

An Elementary Proof of the Quantum Adiabatic Theorem

Andris Ambainis, Oded Regev

We provide an elementary proof of the quantum adiabatic theorem.

arXiv:quant-ph/0411152•Nov 20, 2004•65 citations
The quantum adiabatic theorem is a widely applied result in quantum mechanics. However, recently, counterexamples were produced, indicating that the transition probabilities in some systems do not converge as predicted by the adiabatic theorem [K. P. Marzlin and B. C. Sanders, Phys. Rev. Lett. 93, 160408 (2004)]. In this paper, we examine a proof of the adiabatic theorem, paying specific attention to the validity of the assumptions made in the proof. We show that the convergence of the transition probabilities is path dependent when the change in the Hamiltonian is large. Finally, we consider the application of this reformulated form of the adiabatic theorem to the adiabatic evolution paradigm in quantum computation.
In this thesis we summarize the principles of quantum computing. We specifically consider adiabatic quantum computing, whose principles are explained and shown on several examples. To explain the principle of adiabatic quantum computing we review the adiabatic theorem. We also outline possibility of using a particular Hamiltonian by Berry, which enables us to evolve system adiabatically in arbitrarily short time. In the final part of this thesis, we explain the concept of quantum phase transitions. We discuss a relationship between quantum phase transitions and adiabatic quantum computing and show that adiabatic quantum computing scales polynomially with the number of qubits only for quantum phase transitions of second or higher order. Powered by TCPDF (www.tcpdf.org)
This thesis addresses two questions related to the title, Quantum Computation, Markov Chains and Combinatorial Optimisation. The first question involves an algorithmic primitive of quantum computation, quantum walks on graphs, and its relation to Markov Chains. Quantum walks have been shown in certain cases to mix faster than their classical counterparts. Lifted Markov chains, consisting of a Markov chain on an extended state space which is projected back down to the original state space, also show considerable speedups in mixing time. We design a lifted Markov chain that in some sense simulates any quantum walk. Concretely, we construct a lifted Markov chain on a connected graph G with n vertices that mixes exactly to the average mixing distribution of a quantum walk on G. Moreover, the mixing time of this chain is the diameter of G. We then consider practical consequences of this result. In the second part of this thesis we address a classic unsolved problem in combinatorial optimisation, graph isomorphism. A theorem of Kozen states that two graphs on n vertices are isomorphic if and only if there is a clique of size n in the weak modular product of the two graphs. Furthermore, a straightforward corollary of this theorem and Lovász’s sandwich theorem is if the weak modular product between two graphs is perfect, then checking if the graphs are isomorphic is polynomial in n. We enumerate the necessary and sufficient conditions for the weak modular product of two simple graphs to be perfect. Interesting cases include complete multipartite graphs and disjoint unions of cliques. We find that all perfect weak modular products have factors that fall into classes of graphs for which testing isomorphism is already known to be polynomial in the number of vertices. Open questions and further research directions are discussed.