Extending classical probabilistic reasoning using the quantum mechanical view of probability has been of recent interest, particularly in the development of hidden quantum Markov models (HQMMs) to model stochastic processes. However, there has been little progress in characterizing the expressiveness of such models and learning them from data. We tackle these problems by showing that HQMMs are a special subclass of the general class of observable operator models (OOMs) that do not suffer from the \emph{negative probability problem} by design. We also provide a feasible retraction-based learning algorithm for HQMMs using constrained gradient descent on the Stiefel manifold of model parameters. We demonstrate that this approach is faster and scales to larger models than previous learning algorithms.
In 1985, David Deutsch introduced quantum Turing machines (QTMs for short) as Turing machines which can perform so called quantum parallel computations. Algorithms executed on QTMs are called quantum algorithms. It is well known that Peter Shor designed a polynomial time quantum algorithm for integer factoring in 1994. In this paper, we first illustrate several major methods of designing efficient quantum algorithms with Shor's algorithm as an example. On the other hand, many researchers are studying how to physically implement quantum computers based on QTM. Among others, NMR (Nuclear Magnetic Resonance) offers an appealing prospect for implementation of quantum computers because of a number of reasons. But, quantum computations performed on NMR is slightly different from those performed on QTMs. For example, Shor's factoring algorithm cannot be executed on an NMR quantum computer as it is. In this paper, we show how to factor integers in polynomial time by using NMR quantum computers.