1201.6319 (Leonard Goff et al.)

Classical simulation of measurement-based quantum computation on
higher-genus surface code states    [PDF]

Leonard Goff, Robert Raussendorf

We consider the efficiency of classically simulating measurement-based
quantum computation on surface code states. We devise a method for calculating
the elements of the probability distribution for the classical output of the
quantum computation. The operational cost of this method is polynomial in the
size of the surface code state, but in the worst case scales as $2^{2g}$ in the
genus $g$ of the surface embedding the code. However, there are states in the
code space for which the simulation becomes efficient. In general, the
simulation cost is exponential in the entanglement contained in a certain
effective state, capturing the encoded state, the encoding and the local
post-measurement states. The same efficiencies hold, with additional
assumptions on the temporal order of measurements and on the tessellations of
the code surfaces, for the harder task of sampling from the distribution of the
computational output.

View original: http://arxiv.org/abs/1201.6319