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:0808.2833 · IEEE Transactions on Information Theory

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

Ulrich Faigle, Alexander Schönhuth

Published Feb 18, 2011• 11 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/tit.2011.2104511

Related papers

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

Alexander Schönhuth

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.

International Symposium on Information Theory and its Applications•Dec 1, 2008•5 citations

Hidden quantum Markov processes

Luigi Accardi, El Gheteb Soueidi, Yun Gang Lu +1 more

Starting from the notion of algebraic hidden processes introduced in Ref. 9 , we propose a definition of quantum hidden Markov process which extends the notion of quantum Markov chain (QMC) in the same sense in which classical hidden Markov processes (HMPs) extend classical Markov chains. We give several structure theorems for this new family of quantum states which shares with the QMCs the unique property that the finite dimensional joint expectations are explicitly given without these states being linearly equivalent to product states (as the Gaussian ones). The special feature of this new class of quantum states is best exemplified by looking at their restrictions to diagonal sub-algebras: we prove that they lead to a new family of classical stochastic processes that generalize in a non-trivial way the classical HMPs.

Infinite Dimensional Analysis Quantum Probability and Related Topics•May 9, 2024•9 citations

A Polynomial-Time Algorithm for the Equivalence between Quantum Sequential Machines

Lvzhou Li, Daowen Qiu

Quantum sequential machines (QSMs) are a quantum version of stochastic sequential machines (SSMs). Recently, we showed that two QSMs M_1 and M_2 with n_1 and n_2 states, respectively, are equivalent iff they are (n_1+n_2)^2--equivalent (Theoretical Computer Science 358 (2006) 65-74). However, using this result to check the equivalence likely needs exponential expected time. In this paper, we consider the time complexity of deciding the equivalence between QSMs and related problems. The main results are as follows: (1) We present a polynomial-time algorithm for deciding the equivalence between QSMs, and, if two QSMs are not equivalent, this algorithm will produce an input-output pair with length not more than (n_1+n_2)^2. (2) We improve the bound for the equivalence between QSMs from (n_1+n_2)^2 to n_1^2+n_2^2-1, by employing Moore and Crutchfield's method (Theoretical Computer Science 237 (2000) 275-306). (3) We give that two MO-1QFAs with n_1 and n_2 states, respectively, are equivalent iff they are (n_1+n_2)^2--equivalent, and further obtain a polynomial-time algorithm for deciding the equivalence between two MO-1QFAs. (4) We provide a counterexample showing that Koshiba's method to solve the problem of deciding the equivalence between MM-1QFAs may be not valid, and thus the problem is left open again.

arXiv:quant-ph/0604085•Apr 12, 2006•2 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

Algebraic Hidden processes and Hidden Markov processes

Luigi Accardi, El Gheteb Soueidi, Yun Gang Lu +1 more

In this paper, we propose an algebraic approach to the definition of Hidden Markov Processes (HMP) which has two advantages: on the one hand, it prepares the ground for the quantum extension of these processes (discussed in the second part of this paper), on the other hand it suggests two natural extensions of these processes: one of them highlights a different notion of conditional independence between the observable and the hidden process; the other one drops the assumption that the hidden process is Markov. The latter extension is motivated by the examples of hidden, but not hidden Markov processes produced in the second part of the paper. Furthermore, we prove that any hidden Markov process can be interpreted as a restriction, to a suitable sub-algebra, of a Markov process.

Infinite Dimensional Analysis Quantum Probability and Related Topics•May 9, 2024•7 citations

Characterizing the Relationship Between Unitary Quantum Walks and Non-Homogeneous Random Walks

Matheus Guedes de Andrade, Franklin de Lima Marquezino, Daniel R. Figueiredo

Quantum walks on graphs are ubiquitous in quantum computing finding a myriad of applications. Likewise, random walks on graphs are a fundamental building block for a large number of algorithms with diverse applications. While the relationship between quantum and random walks has been recently discussed in specific scenarios, this work establishes a formal equivalence between the two processes on arbitrary finite graphs and general conditions for shift and coin operators. It requires empowering random walks with time heterogeneity, where the transition probability of the walker is non-uniform and time dependent. The equivalence is obtained by equating the probability of measuring the quantum walk on a given node of the graph and the probability that the random walk is at that same node, for all nodes and time steps. The first result establishes procedure for a stochastic matrix sequence to induce a random walk that yields the exact same vertex probability distribution sequence of any given quantum walk, including the scenario with multiple interfering walkers. The second result establishes a similar procedure in the opposite direction. Given any random walk, a time-dependent quantum walk with the exact same vertex probability distribution is constructed. Interestingly, the matrices constructed by the first procedure allows for a different simulation approach for quantum walks where node samples respect neighbor locality and convergence is guaranteed by the law of large numbers, enabling efficient (polynomial-time) sampling of quantum graph trajectories. Furthermore, the complexity of constructing this sequence of matrices is discussed in the general case.

•Jun 29, 2021•0 citations
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.
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.
Starting from the notion of algebraic hidden processes introduced in Ref. 9 , we propose a definition of quantum hidden Markov process which extends the notion of quantum Markov chain (QMC) in the same sense in which classical hidden Markov processes (HMPs) extend classical Markov chains. We give several structure theorems for this new family of quantum states which shares with the QMCs the unique property that the finite dimensional joint expectations are explicitly given without these states being linearly equivalent to product states (as the Gaussian ones). The special feature of this new class of quantum states is best exemplified by looking at their restrictions to diagonal sub-algebras: we prove that they lead to a new family of classical stochastic processes that generalize in a non-trivial way the classical HMPs.
Quantum sequential machines (QSMs) are a quantum version of stochastic sequential machines (SSMs). Recently, we showed that two QSMs M_1 and M_2 with n_1 and n_2 states, respectively, are equivalent iff they are (n_1+n_2)^2--equivalent (Theoretical Computer Science 358 (2006) 65-74). However, using this result to check the equivalence likely needs exponential expected time. In this paper, we consider the time complexity of deciding the equivalence between QSMs and related problems. The main results are as follows: (1) We present a polynomial-time algorithm for deciding the equivalence between QSMs, and, if two QSMs are not equivalent, this algorithm will produce an input-output pair with length not more than (n_1+n_2)^2. (2) We improve the bound for the equivalence between QSMs from (n_1+n_2)^2 to n_1^2+n_2^2-1, by employing Moore and Crutchfield's method (Theoretical Computer Science 237 (2000) 275-306). (3) We give that two MO-1QFAs with n_1 and n_2 states, respectively, are equivalent iff they are (n_1+n_2)^2--equivalent, and further obtain a polynomial-time algorithm for deciding the equivalence between two MO-1QFAs. (4) We provide a counterexample showing that Koshiba's method to solve the problem of deciding the equivalence between MM-1QFAs may be not valid, and thus the problem is left open again.
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.
In this paper, we propose an algebraic approach to the definition of Hidden Markov Processes (HMP) which has two advantages: on the one hand, it prepares the ground for the quantum extension of these processes (discussed in the second part of this paper), on the other hand it suggests two natural extensions of these processes: one of them highlights a different notion of conditional independence between the observable and the hidden process; the other one drops the assumption that the hidden process is Markov. The latter extension is motivated by the examples of hidden, but not hidden Markov processes produced in the second part of the paper. Furthermore, we prove that any hidden Markov process can be interpreted as a restriction, to a suitable sub-algebra, of a Markov process.
Quantum walks on graphs are ubiquitous in quantum computing finding a myriad of applications. Likewise, random walks on graphs are a fundamental building block for a large number of algorithms with diverse applications. While the relationship between quantum and random walks has been recently discussed in specific scenarios, this work establishes a formal equivalence between the two processes on arbitrary finite graphs and general conditions for shift and coin operators. It requires empowering random walks with time heterogeneity, where the transition probability of the walker is non-uniform and time dependent. The equivalence is obtained by equating the probability of measuring the quantum walk on a given node of the graph and the probability that the random walk is at that same node, for all nodes and time steps. The first result establishes procedure for a stochastic matrix sequence to induce a random walk that yields the exact same vertex probability distribution sequence of any given quantum walk, including the scenario with multiple interfering walkers. The second result establishes a similar procedure in the opposite direction. Given any random walk, a time-dependent quantum walk with the exact same vertex probability distribution is constructed. Interestingly, the matrices constructed by the first procedure allows for a different simulation approach for quantum walks where node samples respect neighbor locality and convergence is guaranteed by the law of large numbers, enabling efficient (polynomial-time) sampling of quantum graph trajectories. Furthermore, the complexity of constructing this sequence of matrices is discussed in the general case.