Simulating classical probabilistic algorithms
Let $S$ be a stochastic $n$-bit matrix, that is, $S$ is a $(2^n \times 2^n)$-matrix $(a_{ij})$ such that each $a_{ij} \in [0,1]$ and $\sum_{j=0}^{2^n-1} a_{ij} = 1$, for each $i = 0, \dots, 2^n-1$. Writing $|i\rangle$ for the $2^n$-vector representing the binary state of the $n$ bits coding the number $i$, we have $$S|i\rangle =…