Contextuality and memory cost of simulation of Majorana fermions*

Contextuality has been reported to be a resource for quantum computation, analogous to non-locality which is a known resource for quantum communication and cryptography. We show that the presence of contextuality places new lower bounds on the memory cost for classically simulating restricted classes of quantum computation. We apply this result to the simulation of a model of quantum computation based on the braiding of Majorana fermions, namely topological quantum computation (TQC) with Ising anyons, finding a saturable lower bound in log-linear in the number of physical modes for the memory cost. TQC model lies in the intersection between two computational models: the Clifford group and the fermionic linear optics (FLO), a framework analogous to bosonic linear optics. We extend our results and prove that the lower bound in the memory required in an approximate simulation of the FLO model is quadratic in the number of physical modes.