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

Journal of Mathematical Physics

Quantum Markov chains

Stanley Gudder

Published Jul 1, 2008• 108 citations
Publisher

Abstract

A new approach to quantum Markov chains is presented. We first define a transition operation matrix (TOM) as a matrix whose entries are completely positive maps whose column sums form a quantum operation. A quantum Markov chain is defined to be a pair (G,E) where G is a directed graph and E=[Eij] is a TOM whose entry Eij labels the edge from vertex j to vertex i. We think of the vertices of G as sites that a quantum system can occupy and Eij is the transition operation from site j to site i in one time step. The discrete dynamics of the system is obtained by iterating the TOM E. We next consider a special type of TOM called a transition effect matrix. In this case, there are two types of dynamics, a state dynamics and an operator dynamics. Although these two types are not identical, they are statistically equivalent. We next give examples that illustrate various properties of quantum Markov chains. We conclude by showing that our formalism generalizes the usual framework for quantum random walks.

DOI
10.1063/1.2953952

Related papers

Quantum walks in the density operator picture

Chaobin Liu

A new approach to quantum walks is presented. Considering a quantum system undergoing some unitary discrete-time evolution in a directed graph G, we think of the vertices of G as sites that are occupied by the quantum system, whose internal state is described by density operators. To formulate the unitary evolution, we define reflections in the tensor product of an internal Hilbert space and a spatial Hilbert space. We then construct unitary channels that govern the evolution of the system in the graph. The discrete dynamics of the system (called quantum walks) is obtained by iterating the unitary channel on the density operator of the quantum system. It turns out that in this framework, the action of the unitary channel on a density operator is described by the usual matrix multiplication.

arXiv:1506.02493•Jun 8, 2015•0 citations

Open Quantum Random Walks and Quantum Markov Chains

Ameur Dhahri, Farrukh Maksutovich Mukhamedov

In the present paper we construct quantum Markov chains associated with open quantum random walks in the sense that the transition operator of a chain is determined by an open quantum random walk and the restriction of the chain to the commutative subalgebra coincides with the distribution ℙ ρ of the walk. This sheds new light on some properties of the measure ℙ ρ . For example, this measure can be considered as the distribution of some functions of a certain Markov process.

Functional Analysis and Its Applications•Apr 1, 2019•11 citations

Discrete Quantum Markov Chains

Ulrich Faigle, Alexander Schönhuth

A framework for finite-dimensional quantum Markov chains on Hilbert spaces is introduced. Quantum Markov chains generalize both classical Markov chains with possibly hidden states and existing models of quantum walks on finite graphs. Quantum Markov chains are based on Markov operations that may be applied to quantum systems and include quantum measurements, for example. It is proved that quantum Markov chains are asymptotically stationary and hence possess ergodic and entropic properties. With a quantum Markov chain one may associate a quantum Markov process, which is a stochastic process in the classical sense. Generalized Markov chains allow a representation with respect to a generalized Markov source model with definite (but possibly hidden) states relative to which observables give rise to classical stochastic processes. It is demonstrated that this model allows for observables to violate Bell’s inequality.

•Nov 4, 2010•3 citations

Quantum Analogs of Markov Chains

Ashwin Nayak, Peter C. Richter

Spatial search and walk processes. Spatial search by quantum walk is database search with the additional constraint that one is required to move through the search space that obeys some locality structure. For example, the data items may be stored at the vertices of a two-dimensional grid. The requirement of moves along the edges of the grid captures the cost of accessing different items starting from some fixed position in the database. One of possible ways of carrying out spatial search is by performing a random walk on the search space or its quantum analog, a quantum walk. The complexity of spatial search by quantum walk is strongly tied to the quantum hitting time [19] of the walk. Let S , with jS j D n, be a finite set of states. Assume that a subset M S of states are marked. We are given a procedure C that, on input x 2 S and an associated data structure d.x/, checks whether the state x is marked. The goal is either to find a marked state when promised that M ¤ ; (search version) or to determine whether M is nonempty (decision version). The algorithm progresses in stages. In the setup stage, we access some state of S (usually a random state). In the walk stage we move from state to state, performing a spatial walk as described below. The moves are called updates. In addition, in the walk stage we perform checks to see if the current state is marked at steps selected by the algorithm. In the classical setting, the transition probabilities of the spatial walk are described by a stochastic matrix P D .px;y/x;y2S . This makes the walk a Markov chain. In every move the algorithm must perform a random transition according to P . The possible x ! y moves, i.e., those with px;y ¤ 0, form the edges of a (directed) graph G, and we say that the Markov chain P has locality structure G. We define the search problem in the classical setting, which carries over to the quantum case with little modification:

•Jan 1, 2015•1 citation

Asymptotic properties of quantum Markov chains

J Novotný, G Alber, I Jex

The asymptotic dynamics of discrete quantum Markov chains generated by the most general physically relevant quantum operations is investigated. It is shown that it is confined to an attractor space in which the resulting quantum Markov chain is diagonalizable. A construction procedure of a basis of this attractor space and its associated dual basis of 1-forms is presented. It is applicable whenever a strictly positive quantum state exists which is contracted or left invariant by the generating quantum operation. Moreover, algebraic relations between the attractor space and Kraus operators involved in the definition of a quantum Markov chain are derived. This construction is not only expected to offer significant computational advantages in cases in which the dimension of the Hilbert space is large and the dimension of the attractor space is small, but it also sheds new light onto the relation between the asymptotic dynamics of discrete quantum Markov chains and fixed points of their generating quantum operations. Finally, we show that without any restriction our construction applies to all initial states whose support belongs to the so-called recurrent subspace.

arXiv:1208.0764•Journal of Physics A Mathematical and Theoretical•Nov 19, 2012•22 citations

Unitary and open scattering quantum walks on graphs

Alain Joye

In this paper, we consider a class of Unitary Quantum Walks on arbitrary graphs, parameterized by a family of scattering matrices. These Scattering Quantum Walks model the discrete dynamics of a system on the graph’s edges, where a scattering process at the vertices is governed by the scattering matrices assigned to each vertex. We show the Scattering Quantum Walks encompass several known Quantum Walks. We further introduce two classes of Scattering Open Quantum Walks on arbitrary graphs, also parameterized by scattering matrices: one defined on the edges, the other on the vertices of the graph. We show these walks give rise to proper quantum channels and describe their main spectral and dynamical properties, relating them to naturally associated classical Markov chains.

arXiv:2409.08428•Reviews in Mathematical Physics•Apr 17, 2026•0 citations
A new approach to quantum Markov chains is presented. We first define a transition operation matrix (TOM) as a matrix whose entries are completely positive maps whose column sums form a quantum operation. A quantum Markov chain is defined to be a pair (G,E) where G is a directed graph and E=[Eij] is a TOM whose entry Eij labels the edge from vertex j to vertex i. We think of the vertices of G as sites that a quantum system can occupy and Eij is the transition operation from site j to site i in one time step. The discrete dynamics of the system is obtained by iterating the TOM E. We next consider a special type of TOM called a transition effect matrix. In this case, there are two types of dynamics, a state dynamics and an operator dynamics. Although these two types are not identical, they are statistically equivalent. We next give examples that illustrate various properties of quantum Markov chains. We conclude by showing that our formalism generalizes the usual framework for quantum random walks.
A new approach to quantum walks is presented. Considering a quantum system undergoing some unitary discrete-time evolution in a directed graph G, we think of the vertices of G as sites that are occupied by the quantum system, whose internal state is described by density operators. To formulate the unitary evolution, we define reflections in the tensor product of an internal Hilbert space and a spatial Hilbert space. We then construct unitary channels that govern the evolution of the system in the graph. The discrete dynamics of the system (called quantum walks) is obtained by iterating the unitary channel on the density operator of the quantum system. It turns out that in this framework, the action of the unitary channel on a density operator is described by the usual matrix multiplication.
A framework for finite-dimensional quantum Markov chains on Hilbert spaces is introduced. Quantum Markov chains generalize both classical Markov chains with possibly hidden states and existing models of quantum walks on finite graphs. Quantum Markov chains are based on Markov operations that may be applied to quantum systems and include quantum measurements, for example. It is proved that quantum Markov chains are asymptotically stationary and hence possess ergodic and entropic properties. With a quantum Markov chain one may associate a quantum Markov process, which is a stochastic process in the classical sense. Generalized Markov chains allow a representation with respect to a generalized Markov source model with definite (but possibly hidden) states relative to which observables give rise to classical stochastic processes. It is demonstrated that this model allows for observables to violate Bell’s inequality.
Spatial search and walk processes. Spatial search by quantum walk is database search with the additional constraint that one is required to move through the search space that obeys some locality structure. For example, the data items may be stored at the vertices of a two-dimensional grid. The requirement of moves along the edges of the grid captures the cost of accessing different items starting from some fixed position in the database. One of possible ways of carrying out spatial search is by performing a random walk on the search space or its quantum analog, a quantum walk. The complexity of spatial search by quantum walk is strongly tied to the quantum hitting time [19] of the walk. Let S , with jS j D n, be a finite set of states. Assume that a subset M S of states are marked. We are given a procedure C that, on input x 2 S and an associated data structure d.x/, checks whether the state x is marked. The goal is either to find a marked state when promised that M ¤ ; (search version) or to determine whether M is nonempty (decision version). The algorithm progresses in stages. In the setup stage, we access some state of S (usually a random state). In the walk stage we move from state to state, performing a spatial walk as described below. The moves are called updates. In addition, in the walk stage we perform checks to see if the current state is marked at steps selected by the algorithm. In the classical setting, the transition probabilities of the spatial walk are described by a stochastic matrix P D .px;y/x;y2S . This makes the walk a Markov chain. In every move the algorithm must perform a random transition according to P . The possible x ! y moves, i.e., those with px;y ¤ 0, form the edges of a (directed) graph G, and we say that the Markov chain P has locality structure G. We define the search problem in the classical setting, which carries over to the quantum case with little modification:
The asymptotic dynamics of discrete quantum Markov chains generated by the most general physically relevant quantum operations is investigated. It is shown that it is confined to an attractor space in which the resulting quantum Markov chain is diagonalizable. A construction procedure of a basis of this attractor space and its associated dual basis of 1-forms is presented. It is applicable whenever a strictly positive quantum state exists which is contracted or left invariant by the generating quantum operation. Moreover, algebraic relations between the attractor space and Kraus operators involved in the definition of a quantum Markov chain are derived. This construction is not only expected to offer significant computational advantages in cases in which the dimension of the Hilbert space is large and the dimension of the attractor space is small, but it also sheds new light onto the relation between the asymptotic dynamics of discrete quantum Markov chains and fixed points of their generating quantum operations. Finally, we show that without any restriction our construction applies to all initial states whose support belongs to the so-called recurrent subspace.
In this paper, we consider a class of Unitary Quantum Walks on arbitrary graphs, parameterized by a family of scattering matrices. These Scattering Quantum Walks model the discrete dynamics of a system on the graph’s edges, where a scattering process at the vertices is governed by the scattering matrices assigned to each vertex. We show the Scattering Quantum Walks encompass several known Quantum Walks. We further introduce two classes of Scattering Open Quantum Walks on arbitrary graphs, also parameterized by scattering matrices: one defined on the edges, the other on the vertices of the graph. We show these walks give rise to proper quantum channels and describe their main spectral and dynamical properties, relating them to naturally associated classical Markov chains.