Extreme Quantum Advantage when Simulating Strongly Coupled Classical Systems

ABSTRACT: Classical stochastic processes can be generated by quantum simulators instead of the more standard classical ones, such as hidden Markov models. One reason for using quantum simulators has recently come to the fore: they generally require less memory than their classical counterparts. Here, we examine this quantum advantage for strongly coupled spin systems—the Dyson-like one-dimensional Ising spin chain with variable interaction length. We find that the advantage scales with both interaction range and temperature, growing without bound as interaction increases. In particular, it is impossible to classically simulate Dyson's original spin chain since it requires infinite memory, while quantum simulators can do so since they use only finite memory. Thus, quantum systems can very efficiently simulate strongly coupled classical systems.