Bounds on classical simulation of simple quantum models from quantum supremacy.

Quantum simulation is a central application of quantum computing. Quantum supremacy defines systems whose efficient classical simulation is unlikely given complexity-theoretic assumptions. We consider simple physically motivated quantum models that can display quantum supremacy and hence whose efficient simulation by classical means is unlikely. We consider quantum extensions of classical hydrodynamic lattice gas models. We find that the existence of local conserved quantities strongly constrains such extensions. We find the only extensions that retain local conserved quantities correspond to changing the local encoding of a subset of the bits. These models maintain separability of the state throughout the evolution and are thus efficiently classically simulable. We then consider evolution of these models in the case where any of the bits can be encoded and measured in one of two local bases. For quantum extensions of classical models that are computationally universal such quantum extensions can encode Simon’s algorithm and demonstrate quantum supremacy, thus presenting an obstacle to efficient classical simulation.


On Quantum Extensions of Hydrodynamic Lattice Gas Automata Peter Love Condens. Matter 2019, 4(2), 48; https://doi.org/10.3390/condmat4020048