Consistent theories have been proposed in which spacetime is treated classically while matter remains quantum. Here, the authors prove that such theories are constrained by a trade-off between the decoherence induced in the quantum system, and stochasticity in the classical one, providing a way to experimentally test the quantum nature of gravity.