Generalized contextuality as a necessary resource for universal quantum computation

Abstract

A universal and well-motivated notion of classicality for an operational theory is explainability by a generalized-noncontextual ontological model. I will here explain what notion of classicality this implies within the framework of generalized probabilistic theories. I then prove that for any locally tomographic theory, every such classical model is given by a complete frame representation. Using this powerful constraint on the space of possible classical representations, I will then prove that the stabilizer subtheory has a unique classical representation—namely Gross's discrete Wigner function. This provides deep insights into the relevance of Gross's representation within quantum computation. It also implies that generalized contextuality is also a necessary resource for universal quantum computation in the state injection model.