Transition Effect Matrices and Quantum Markov Chains

Ameur Dhahri, Franco Fagnola

Luigi Accardi

Adam Connolly, Steven Herbert, Julien Sorci

This paper proposes a quantum algorithm for Markov chain spectral gap estimation that is quasi-optimal (i.e., optimal up to a polylogarithmic factor) in the number of vertices for all parameters, and additionally quasi-optimal in the reciprocal of the spectral gap itself, if the permitted relative error is above some critical value. In particular, these results constitute an almost quadratic advantage over the best-possible classical algorithm. Our algorithm also improves on the quantum state of the art, and we contend that this is not just theoretically interesting but also potentially practically impactful in real-world applications: knowing a Markov chain's spectral gap can speed-up sampling in Markov chain Monte Carlo. Our approach uses the quantum singular value transformation, and as a result we also develop some theory around block-encoding Markov chain transition matrices, which is potentially of independent interest. In particular, we introduce explicit block-encoding methods for the transition matrices of two algebraically-defined classes of Markov chains.

Jocelyne Marbeau, Stanley Gudder

A quantum chain is analogous to a classical stationary Markov chain except that the probability measure is replaced by a complex amplitude measure and the transition probability matrix is replaced by a transition amplitude matrix. After considering the general situation, we study a particular example of a quantum chain whose transition amplitude matrix has the form of a Dirichlet matrix. Such matrices generate a discrete analog of the usual continuum Feynman amplitude. We then compute the probability distribution for these quantum chains Une chai←ne de Markov quantique est analogue a une chai←ne de Markov stationnaire classique avec la difference que la mesure de probabilite est remplacee par une mesure d'amplitude complexe, et la matrice des probabilites de transition est remplacee par une matrice d'amplitude de transition. Apres avoir considere le cas general, nous etudions le cas particulier d'une chaine quantique dont la matrice de transition est une matrice de Dirichlet. De telles matrices conduisent a un analogue discret des amplitudes de Feynman continues. Nous calculons ensuite les distributions de probabilite de ces chaines quantiques

Michał Cholewa, Piotr Gawron, Przemysław Głomb +1 more

In this work, we extend the idea of quantum Markov chains (Gudder in J Math Phys 49(7):072105 [ 3 ]) in order to propose quantum hidden Markov models (QHMMs). For that, we use the notions of transition operation matrices and vector states, which are an extension of classical stochastic matrices and probability distributions. Our main result is the Mealy QHMM formulation and proofs of algorithms needed for application of this model: Forward for general case and Vitterbi for a restricted class of QHMMs. We show the relations of the proposed model to other quantum HMM propositions and present an example of application.

Crispin W. Gardiner, P. Zoller