Classical descriptions of quantum computations: Foundations of quantum computation via hidden variable models, quasiprobability representations, and classical simulation algorithms

[abstract] Quasiprobability representations serve as a bridge between classical and quantum descriptions of physical systems. In these representations, nonnegativity allows for a probabilistic interpretation, aligning the description with classical physics. 

However, the capacity to model quantum systems hinges on the use of negative quasiprobabilities. Accordingly, negativity is considered a hallmark of genuinely quantum behaviour. This principle has been applied to quantum information processing where negativity in the Wigner function is necessary for a quantum computational advantage. This is demonstrated by an efficient classical simulation algorithm for quantum computations in which all components of the computation remain nonnegative.

However, when constructing quasiprobability representations for quantum computation to which this statement applies, a marked difference arises between the cases of even and odd Hilbert space dimension. We find that Wigner functions with the properties required to describe quantum computation do not exist in any even dimension. We establish that the obstructions to the existence of such Wigner functions are cohomological.

In order to recover the properties required for classical simulation of quantum computation in any dimension, some constraints that traditionally define a Wigner function must be relaxed. We consider several examples of these generalized quasiprobability representations, and we find that when sufficiently general representations are admitted, no negativity is required to represent universal quantum computation. 

The result is a hidden variable model that represents all elements of universal quantum computation probabilistically. Since this model can simulate any quantum computation, the simulation must be inefficient in general. However, in certain restricted settings, the simulation is efficient, allowing for a broader class of magic state quantum circuits to be efficiently classically simulated than those covered by the stabilizer formalism and Wigner function methods.

With this hidden variable model, we present a formulation of quantum mechanics that replaces the central notion of state, as a complex vector or density operator, with a bit string. This formulation applies to universal quantum computation, and hence all finite-dimensional quantum mechanics. Thus, we present a surprising response to Wheeler’s "It from Bit" challenge. Alongside coherence, entanglement, and contextuality, this provides a new approach to characterizing quantum advantage.