The max-flow and max-coflow problem on directed graphs is studied in the common generalization to regular spaces, i.e., to kernels or row spaces of totally unimodular matrices. Exhibiting a submodular structure of the family of paths within this model we generalize the Edmonds-Karp variant of the classical Ford-Fulkerson method and show that the number of augmentations is quadratically bounded if augmentations are chosen along shortest possible augmenting paths.
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 $cM_1,cM_2$ resp. two QRW parametrizations $cQ_1,cQ_2$ in time $O(|S|max(N_1,N_2)^{4})$, where $N_1,N_2$ are the number of hidden states in $cM_1,cM_2$ resp. the dimension of the state spaces associated with $cQ_1,cQ_2$, and $S$ is the set of output symbols. Previously available 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 subroutines of this algorithm can also be used to efficiently test hidden Markov processes and quantum random walks for ergodicity.
While the standard approach to quantum systems studies length preserving linear transformations of wave functions, the Markov picture focuses on trace preserving operators on the space of Hermitian (self-adjoint) matrices. The Markov approach extends the standard one and provides a refined analysis of measurements and quantum Markov chains. In particular, Bells inequality becomes structurally clear. It turns out that hidden state models are natural in the Markov context. In particular, a violation of Bells inequality is seen to be compatible with the existence of hidden states. The Markov model moreover clarifies the role of the negative probabilities in Feynmans analysis of the EPR paradox.
