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

International Symposium on Information Theory and its Applications

Simple and efficient solution of the identifiability problem for hidden Markov sources and quantum random walks

Alexander Schönhuth

Published Dec 1, 2008• 5 citations
Publisher

Abstract

A solution of the identifiability problem (IP) for hidden Markov models (HMMs), based on a novel algebraic theory for random sources, is presented. It gives rise to an efficient and practical algorithm that can be easily implemented. Extant approaches are exponential in the number of hidden states and therefore only applicable to a limited degree. The algorithm can be equally applied to solve the IP for quantum random walks (QRWs) that have recently been presented as an analogon of Markov chains in quantum information theory. Moreover, the algorithm can be used to efficiently test HMMs and QRWs for ergodicity, which had remained an open problem so far.

DOI
10.1109/isita.2008.4895457

Related papers

Efficient Tests for Equivalence of Hidden Markov Processes and Quantum Random Walks

Ulrich Faigle, Alexander Schönhuth

While two hidden Markov process (HMP) resp. quantum random walk (QRW) parametrizations can differ from one another, the stochastic processes arising from them can be equivalent. Here a polynomial-time algorithm is presented which can determine equivalence of two HMP parametrizations M1, M2resp. two QRW parametrizations Q1, Q2in time O(|Σ| max(N1, N2)4), where N1,N2are the number of hidden states in M1, M2resp. the dimension of the state spaces associated with Q1, Q2, and Σ is the set of output symbols. Previously avail able algorithms for testing equivalence of HMPs were exponential in the number of hidden states. In case of QRWs, algorithms for testing equivalence had not yet been presented. The core subrou tines of this algorithm can also be used to efficiently test hidden Markov processes and quantum random walks for ergodicity.

arXiv:0808.2833•IEEE Transactions on Information Theory•Feb 18, 2011•11 citations

On Hidden States in Quantum Random Walks

Ulrich Faigle, Alexander Schönhuth

It was recently pointed out that identifiability of quantum random walks and hidden Markov processes underlie the same principles. This analogy immediately raises questions on the existence of hidden states also in quantum random walks and their relationship with earlier debates on hidden states in quantum mechanics. The overarching insight was that not only hidden Markov processes, but also quantum random walks are finitary processes. Since finitary processes enjoy nice asymptotic properties, this also encourages to further investigate the asymptotic properties of quantum random walks. Here, answers to all these questions are given. Quantum random walks, hidden Markov processes and finitary processes are put into a unifying model context. In this context, quantum random walks are seen to not only enjoy nice ergodic properties in general, but also intuitive quantum-style asymptotic properties. It is also pointed out how hidden states arising from our framework relate to hidden states in earlier, prominent treatments on topics such as the EPR paradoxon or Bell's inequalities.

arXiv:1601.02882•Dec 29, 2015•0 citations

Quantum Dimension Reduction of Hidden Markov Models

Rishi Sundar, Thomas J. Elliott

Hidden Markov models (HMMs) are ubiquitous in time-series modelling, with applications ranging from chemical reaction modelling to speech recognition. These HMMs are often large, with high-dimensional memories. A recently-proposed application of quantum technologies is to execute quantum analogues of HMMs. Such quantum HMMs (QHMMs) are strictly more expressive than their classical counterparts, enabling the construction of more parsimonious models of stochastic processes. However, state-of-the-art techniques for QHMM compression, based on tensor networks, are only applicable for a restricted subset of HMMs, where the transitions are deterministic. In this work we introduce a pipeline by which \emph{any} finite, ergodic HMM can be compressed in this manner, providing a route for effective quantum dimension reduction of general HMMs. We demonstrate the method on both a simple toy model, and on a speech-derived HMM trained from data, obtaining favourable memory--accuracy trade-offs in the examples studied, relative to a simple classical state-merging baseline.

quant-pharXiv:2601.16126•Physical Review A•Jan 23, 2026•0 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

Memory compression and thermal efficiency of quantum implementations of nondeterministic hidden Markov models

Thomas J. Elliott

Stochastic modeling is an essential component of the quantitative sciences, with hidden Markov models (HMMs) often playing a central role. Concurrently, the rise of quantum technologies promises a host of advantages in computational problems, typically in terms of the scaling of requisite resources such as time and memory. HMMs are no exception to this, with recent results highlighting quantum implementations of deterministic HMMs exhibiting superior memory and thermal efficiency relative to their classical counterparts. In many contexts, however, nondeterministic HMMs are viable alternatives; compared to them, the advantages of current quantum implementations do not always hold. Here, we provide a systematic prescription for constructing quantum implementations of nondeterministic HMMs that reestablish the quantum advantages against this broader class. Crucially, we show that whenever the classical implementation suffers from thermal dissipation due to its need to process information in a time-local manner, our quantum implementations will both mitigate some of this dissipation and achieve an advantage in memory compression.

arXiv:2105.06285•Physical Review A•May 28, 2021•16 citations

Quantum hidden Markov models based on transition operation matrices

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.

arXiv:1503.08760•Quantum Information Processing•Mar 1, 2017•17 citations
A solution of the identifiability problem (IP) for hidden Markov models (HMMs), based on a novel algebraic theory for random sources, is presented. It gives rise to an efficient and practical algorithm that can be easily implemented. Extant approaches are exponential in the number of hidden states and therefore only applicable to a limited degree. The algorithm can be equally applied to solve the IP for quantum random walks (QRWs) that have recently been presented as an analogon of Markov chains in quantum information theory. Moreover, the algorithm can be used to efficiently test HMMs and QRWs for ergodicity, which had remained an open problem so far.
While two hidden Markov process (HMP) resp. quantum random walk (QRW) parametrizations can differ from one another, the stochastic processes arising from them can be equivalent. Here a polynomial-time algorithm is presented which can determine equivalence of two HMP parametrizations M1, M2resp. two QRW parametrizations Q1, Q2in time O(|Σ| max(N1, N2)4), where N1,N2are the number of hidden states in M1, M2resp. the dimension of the state spaces associated with Q1, Q2, and Σ is the set of output symbols. Previously avail able algorithms for testing equivalence of HMPs were exponential in the number of hidden states. In case of QRWs, algorithms for testing equivalence had not yet been presented. The core subrou tines of this algorithm can also be used to efficiently test hidden Markov processes and quantum random walks for ergodicity.
It was recently pointed out that identifiability of quantum random walks and hidden Markov processes underlie the same principles. This analogy immediately raises questions on the existence of hidden states also in quantum random walks and their relationship with earlier debates on hidden states in quantum mechanics. The overarching insight was that not only hidden Markov processes, but also quantum random walks are finitary processes. Since finitary processes enjoy nice asymptotic properties, this also encourages to further investigate the asymptotic properties of quantum random walks. Here, answers to all these questions are given. Quantum random walks, hidden Markov processes and finitary processes are put into a unifying model context. In this context, quantum random walks are seen to not only enjoy nice ergodic properties in general, but also intuitive quantum-style asymptotic properties. It is also pointed out how hidden states arising from our framework relate to hidden states in earlier, prominent treatments on topics such as the EPR paradoxon or Bell's inequalities.
Hidden Markov models (HMMs) are ubiquitous in time-series modelling, with applications ranging from chemical reaction modelling to speech recognition. These HMMs are often large, with high-dimensional memories. A recently-proposed application of quantum technologies is to execute quantum analogues of HMMs. Such quantum HMMs (QHMMs) are strictly more expressive than their classical counterparts, enabling the construction of more parsimonious models of stochastic processes. However, state-of-the-art techniques for QHMM compression, based on tensor networks, are only applicable for a restricted subset of HMMs, where the transitions are deterministic. In this work we introduce a pipeline by which \emph{any} finite, ergodic HMM can be compressed in this manner, providing a route for effective quantum dimension reduction of general HMMs. We demonstrate the method on both a simple toy model, and on a speech-derived HMM trained from data, obtaining favourable memory--accuracy trade-offs in the examples studied, relative to a simple classical state-merging baseline.
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.
Stochastic modeling is an essential component of the quantitative sciences, with hidden Markov models (HMMs) often playing a central role. Concurrently, the rise of quantum technologies promises a host of advantages in computational problems, typically in terms of the scaling of requisite resources such as time and memory. HMMs are no exception to this, with recent results highlighting quantum implementations of deterministic HMMs exhibiting superior memory and thermal efficiency relative to their classical counterparts. In many contexts, however, nondeterministic HMMs are viable alternatives; compared to them, the advantages of current quantum implementations do not always hold. Here, we provide a systematic prescription for constructing quantum implementations of nondeterministic HMMs that reestablish the quantum advantages against this broader class. Crucially, we show that whenever the classical implementation suffers from thermal dissipation due to its need to process information in a time-local manner, our quantum implementations will both mitigate some of this dissipation and achieve an advantage in memory compression.
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.