Abstract

In measurement-based quantum computation, adaptive single qubit measurement on a many-qubit entangled resource state (e.g. a cluster state) together with simple and efficient classical side-processing provides a model of computation equivalent to the quantum circuit model. A variety of entangled resource state families beyond the cluster states have been proposed, and it is natural to ask what roles the entanglement in these states is playing in the computation. To consider this, we study measurement based computation on resource states with no entanglement or quantum discord – essentially states which are equivalent to classical probability distributions. We show that studying the computable functions in this model is equivalent to studying families CHSH -Bell inequalities, and that the lack of computational expressiveness in these models provides a compact unified description of all CHSH -type inequalities. We then consider whether these simple computations can still possess any non-classical attributes. Surprisingly, by modifying an argument of Bremner, Shepherd and Josza, we can show among these computations exist uniform families which are unlikely to be exactly efficiently simulatable on a classical computation. These computations – which can be cast as simple classical sampling problems – form a subset of the families introduced by Bremner, Shepherd and Josza and are striking for their simplicity.