  Stochastic modelling 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, non-deterministic 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
non-deterministic HMMs that re-establish 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.
