Classical simulation of measurement-based quantum computation on higher-genus surface-code states
arXiv:1201.6319 · doi:10.1103/PhysRevA.86.042301
Abstract
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 in the genus 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.
arXiv comment21 pages, 13 figures
References in corpus (14)
- Fault-tolerant quantum computation by anyons
- Efficient classical simulation of slightly entangled quantum computations
- Topological quantum memory
- On the role of entanglement in quantum computational speed-up
- Simulating quantum computation by contracting tensor networks
- Classical simulation of noninteracting-fermion quantum circuits
- Most quantum states are too entangled to be useful as computational resources
- The Schmidt Measure as a Tool for Quantifying Multi-Particle Entanglement
- Matchgates and classical simulation of quantum circuits
- Generalized Flow and Determinism in Measurement-based Quantum Computation
- Are random pure states useful for quantum computation?
- Classical simulation versus universality in measurement based quantum computation
- On measurement-based quantum computation with the toric code states
- Classical spin models and the quantum stabilizer formalism