Accuracy vs Memory Advantage in the Quantum Simulation of Stochastic
  Processes
Leonardo Banchi
Many inference scenarios rely on extracting relevant information from known
data in order to make future predictions. When the underlying stochastic
process satisfies certain assumptions, there is a direct mapping between its
exact classical and quantum simulators, with the latter asymptotically using
less memory. Here we focus on studying whether such quantum advantage persists
when those assumptions are not satisfied, and the model is doomed to have
imperfect accuracy. By studying the trade-off between accuracy and memory
requirements, we show that quantum models can reach the same accuracy with less
memory, or alternatively, better accuracy with the same memory. Finally, we
discuss the implications of this result for learning tasks.