# Classical simulation of measurement-based quantum computation on higher-genus surface-code states

@article{Goff2012ClassicalSO, title={Classical simulation of measurement-based quantum computation on higher-genus surface-code states}, author={Leonard Goff and Robert Raussendorf}, journal={Physical Review A}, year={2012}, volume={86}, pages={042301} }

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… Expand

#### Figures from this paper

#### 3 Citations

Quantum Commuting Circuits and Complexity of Ising Partition Functions

- Physics, Mathematics
- ArXiv
- 2013

It is shown that there is no fully polynomial randomized approximation scheme (FPRAS) for Ising models with almost all imaginary coupling constants even on a planar graph of a bounded degree, unless the PH collapses at the third level. Expand

Commuting quantum circuits and complexity of Ising partition functions

- 2017

Instantaneous quantumpolynomial-time (IQP) computation is a class of quantum computation consisting only of commuting two-qubit gates and is not universal. Nevertheless, it has been shown that if… Expand

Title Commuting quantum circuits and complexity of Ising partitionfunctions

- 2018

Instantaneous quantumpolynomial-time (IQP) computation is a class of quantum computation consisting only of commuting two-qubit gates and is not universal. Nevertheless, it has been shown that if… Expand

#### References

SHOWING 1-10 OF 42 REFERENCES

Measurement-based quantum computation with the toric code states

- Physics
- 2007

We study measurement-based quantum computation (MQC) using as a quantum resource the planar code state on a two-dimensional square lattice (planar analog of the toric code). It is shown that MQC with… Expand

Topological quantum memory

- Physics
- 2002

We analyze surface codes, the topological quantum error-correcting codes introduced by Kitaev. In these codes, qubits are arranged in a two-dimensional array on a surface of nontrivial topology, and… Expand

Classical simulation versus universality in measurement-based quantum computation

- Physics
- 2007

We investigate for which resource states an efficient classical simulation of measurement-based quantum computation is possible. We show that the Schmidt-rank width, a measure recently introduced to… Expand

Generalized flow and determinism in measurement-based quantum computation

- Physics
- 2007

We extend the notion of quantum information flow defined by Danos and Kashefi (2006 Phys. Rev. A 74 052310) for the one-way model (Raussendorf and Briegel 2001 Phys. Rev. Lett. 86 910) and present a… Expand

Are random pure States useful for quantum computation?

- Mathematics, Physics
- Physical review letters
- 2009

A randomly chosen pure state as a resource for measurement-based quantum computation is-with overwhelming probability-of no greater help to a polynomially bounded classical control computer, than a string of random bits. Expand

On the role of entanglement in quantum-computational speed-up

- Mathematics, Physics
- Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences
- 2003

For any quantum algorithm operating on pure states, we prove that the presence of multi‐partite entanglement, with a number of parties that increases unboundedly with input size, is necessary if the… Expand

Classical simulation of noninteracting-fermion quantum circuits

- Physics, Computer Science
- ArXiv
- 2001

It is shown that a class of quantum computations that was recently shown to be efficiently simulatable on a classical computer by Valiant corresponds to a physical model of noninteracting fermions in one dimension. Expand

Matchgates and classical simulation of quantum circuits

- Mathematics, Physics
- Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences
- 2008

Let G(A, B) denote the two-qubit gate that acts as the one-qubit SU(2) gates A and B in the even and odd parity subspaces, respectively, of two qubits. Using a Clifford algebra formalism, we show… Expand

Most quantum States are too entangled to be useful as computational resources.

- Physics, Medicine
- Physical review letters
- 2009

It is shown that quantum states can be too entangled to be useful for the purpose of computation, in that high values of the geometric measure of entanglement preclude states from offering a universal quantum computational speedup. Expand

Simulating Quantum Computation by Contracting Tensor Networks

- Mathematics, Computer Science
- SIAM J. Comput.
- 2008

It is proved that a quantum circuit with T gates whose underlying graph has a treewidth d can be simulated deterministically in T^{O(1)}\exp[O(d)]$ time, which, in particular, is polynomial in $T$ if d=O(\log T)$. Expand