Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Surface codes, the 2D classical Ising model, and non-interacting fermions

Leonard Goff

Published Jan 1, 2011• 0 citations
Publisher

Abstract

In this thesis, we consider the task of simulating measurement-based quantum computation (MBQC) on surface code states: the generalization of Kitaev's toric code to graphs embedded on a surface of higher genus. We define a family of higher genus graphs and a simple ordering of single qubit measurements, and find that simulating MBQC on any of the associated surface code states is equivalent to evaluating the inner-product between a product state and a surface code state on another graph. We further find that such an inner-product can always be written as a sum of one or more 2D classical Ising model partition functions, with appropriate couplings. For certain higher genus square lattices, we develop a means to evaluate this partition function in a number of steps that scales polynomially in the number of qubits, but exponentially in the genus of the embedded graph. The method makes use of the transfer matrix formalism for the Ising partition function, and a subsequent mapping to fermion operators. We synthesize these results to relate the simulation of MBQC on certain surface code states to a system of fermions interacting with the encoded qubits of the surface code. We identify a family of states in the code space of the surface code on our higher genus graphs for which MBQC can be simulated efficiently in all parameters, including the genus of the embedded graph. Finally, we identify two connections between the complexity of this task and entanglement.

DOI
10.14288/1.0084720

Related papers

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

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 postmeasurement 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:1201.6319•Physical Review A•Oct 1, 2012•1 citation

Measurement-based quantum computation with the toric code states

Sergey B. Bravyi, Robert Raussendorf

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 the planar code state can be efficiently simulated on a classical computer if at each step of MQC the sets of measured and unmeasured qubits correspond to connected subsets of the lattice. The simulation scheme is built upon Barahona's algorithm for computing the partition function of the Ising model on a planar graph. Our results provide a simulation method for MQC centered around planarity of graphs.

arXiv:quant-ph/0610162•Physical Review A•Aug 6, 2007•69 citations

Completeness of the Classical 2D Ising Model and Universal Quantum Computation

M. Van den Nest, Wolfgang Dür, Hans J. Briegel

We prove that the 2D Ising model is complete in the sense that the partition function of any classical q-state spin model (on an arbitrary graph) can be expressed as a special instance of the partition function of a 2D Ising model with complex inhomogeneous couplings and external fields. In the case where the original model is an Ising or Potts-type model, we find that the corresponding 2D square lattice requires only polynomially more spins with respect to the original one, and we give a constructive method to map such models to the 2D Ising model. For more general models the overhead in system size may be exponential. The results are established by connecting classical spin models with measurement-based quantum computation and invoking the universality of the 2D cluster states.

arXiv:0708.2275•Physical Review Letters•Mar 17, 2008•63 citations

Quantum algorithm for an additive approximation of Ising partition functions

Akira Matsuo, Keisuke Fujii, Nobuyuki Imoto

We investigate quantum-computational complexity of calculating partition functions of Ising models. We construct a quantum algorithm for an additive approximation of Ising partition functions on square lattices. To this end, we utilize the overlap mapping developed by M. Van den Nest, W. D\"ur, and H. J. Briegel [Phys. Rev. Lett. 98, 117207 (2007)] and its interpretation through measurement-based quantum computation (MBQC). We specify an algorithmic domain, on which the proposed algorithm works, and an approximation scale, which determines the accuracy of the approximation. We show that the proposed algorithm performs a nontrivial task, which would be intractable on any classical computer, by showing that the problem that is solvable by the proposed quantum algorithm is BQP-complete. In the construction of the BQP-complete problem coupling strengths and magnetic fields take complex values. However, the Ising models that are of central interest in statistical physics and computer science consist of real coupling strengths and magnetic fields. Thus we extend the algorithmic domain of the proposed algorithm to such a real physical parameter region and calculate the approximation scale explicitly. We found that the overlap mapping and its MBQC interpretation improve the approximation scale exponentially compared to a straightforward constant-depth quantum algorithm. On the other hand, the proposed quantum algorithm also provides partial evidence that there exist no efficient classical algorithm for a multiplicative approximation of the Ising partition functions even on the square lattice. This result supports the observation that the proposed quantum algorithm also performs a nontrivial task in the physical parameter region.

arXiv:1405.2749•Physical Review A•Aug 5, 2014•17 citations

Encoder Circuit For Surface Code using Measurement-Based Quantum Computing Model

Priyam Srivastava, Vaibhav Katyal, Ankur Raina

Surface codes are one of the most important topological stabilizer codes in the theory of quantum error correction. In this paper, we provide an efficient way to obtain surface codes through Measurement-based quantum computation (MBQC) using cluster state as the resource state. Simple twodimensional surface codes are studied and analyzed using stabilizer formalism. We also present an algorithm to computationally obtain the stabilizer of the surface codes, through which we later determine the distance of the codes. We note the difference in the stabilizers of the surface codes obtained by Fowler et al. wherein they used CNOT entangling operation to create the resource state as opposed to the cluster state which is formed using CZ entangling operation. We provide a theoretical calculation to understand this difference. The obtained surface codes can be used practically as an encoder circuit to encode one logical qubit.

arXiv:2306.10267•Jun 17, 2023•0 citations

Exponentially improved classical and quantum algorithms for three-body Ising models

M. Van den Nest, Wolfgang Dür

We present an algorithm to approximate partition functions of three-body classical Ising models on two-dimensional lattices of arbitrary genus, in the real-temperature regime. Even though our algorithm is purely classical, it is designed by exploiting a connection to topological quantum systems, namely, the color codes. The algorithm performance (in achievable accuracy) is exponentially better than other approaches that employ mappings between partition functions and quantum state overlaps. In addition, our approach gives rise to a protocol for quantum simulation of such Ising models by simply measuring local observables on color codes.

arXiv:1304.2879•Physical Review A•Jan 29, 2014•2 citations
In this thesis, we consider the task of simulating measurement-based quantum computation (MBQC) on surface code states: the generalization of Kitaev's toric code to graphs embedded on a surface of higher genus. We define a family of higher genus graphs and a simple ordering of single qubit measurements, and find that simulating MBQC on any of the associated surface code states is equivalent to evaluating the inner-product between a product state and a surface code state on another graph. We further find that such an inner-product can always be written as a sum of one or more 2D classical Ising model partition functions, with appropriate couplings. For certain higher genus square lattices, we develop a means to evaluate this partition function in a number of steps that scales polynomially in the number of qubits, but exponentially in the genus of the embedded graph. The method makes use of the transfer matrix formalism for the Ising partition function, and a subsequent mapping to fermion operators. We synthesize these results to relate the simulation of MBQC on certain surface code states to a system of fermions interacting with the encoded qubits of the surface code. We identify a family of states in the code space of the surface code on our higher genus graphs for which MBQC can be simulated efficiently in all parameters, including the genus of the embedded graph. Finally, we identify two connections between the complexity of this task and entanglement.
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 22g{2}^{2g}22g in the genus ggg 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 postmeasurement 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.
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 the planar code state can be efficiently simulated on a classical computer if at each step of MQC the sets of measured and unmeasured qubits correspond to connected subsets of the lattice. The simulation scheme is built upon Barahona's algorithm for computing the partition function of the Ising model on a planar graph. Our results provide a simulation method for MQC centered around planarity of graphs.
We prove that the 2D Ising model is complete in the sense that the partition function of any classical q-state spin model (on an arbitrary graph) can be expressed as a special instance of the partition function of a 2D Ising model with complex inhomogeneous couplings and external fields. In the case where the original model is an Ising or Potts-type model, we find that the corresponding 2D square lattice requires only polynomially more spins with respect to the original one, and we give a constructive method to map such models to the 2D Ising model. For more general models the overhead in system size may be exponential. The results are established by connecting classical spin models with measurement-based quantum computation and invoking the universality of the 2D cluster states.
We investigate quantum-computational complexity of calculating partition functions of Ising models. We construct a quantum algorithm for an additive approximation of Ising partition functions on square lattices. To this end, we utilize the overlap mapping developed by M. Van den Nest, W. D\"ur, and H. J. Briegel [Phys. Rev. Lett. 98, 117207 (2007)] and its interpretation through measurement-based quantum computation (MBQC). We specify an algorithmic domain, on which the proposed algorithm works, and an approximation scale, which determines the accuracy of the approximation. We show that the proposed algorithm performs a nontrivial task, which would be intractable on any classical computer, by showing that the problem that is solvable by the proposed quantum algorithm is BQP-complete. In the construction of the BQP-complete problem coupling strengths and magnetic fields take complex values. However, the Ising models that are of central interest in statistical physics and computer science consist of real coupling strengths and magnetic fields. Thus we extend the algorithmic domain of the proposed algorithm to such a real physical parameter region and calculate the approximation scale explicitly. We found that the overlap mapping and its MBQC interpretation improve the approximation scale exponentially compared to a straightforward constant-depth quantum algorithm. On the other hand, the proposed quantum algorithm also provides partial evidence that there exist no efficient classical algorithm for a multiplicative approximation of the Ising partition functions even on the square lattice. This result supports the observation that the proposed quantum algorithm also performs a nontrivial task in the physical parameter region.
Surface codes are one of the most important topological stabilizer codes in the theory of quantum error correction. In this paper, we provide an efficient way to obtain surface codes through Measurement-based quantum computation (MBQC) using cluster state as the resource state. Simple twodimensional surface codes are studied and analyzed using stabilizer formalism. We also present an algorithm to computationally obtain the stabilizer of the surface codes, through which we later determine the distance of the codes. We note the difference in the stabilizers of the surface codes obtained by Fowler et al. wherein they used CNOT entangling operation to create the resource state as opposed to the cluster state which is formed using CZ entangling operation. We provide a theoretical calculation to understand this difference. The obtained surface codes can be used practically as an encoder circuit to encode one logical qubit.
We present an algorithm to approximate partition functions of three-body classical Ising models on two-dimensional lattices of arbitrary genus, in the real-temperature regime. Even though our algorithm is purely classical, it is designed by exploiting a connection to topological quantum systems, namely, the color codes. The algorithm performance (in achievable accuracy) is exponentially better than other approaches that employ mappings between partition functions and quantum state overlaps. In addition, our approach gives rise to a protocol for quantum simulation of such Ising models by simply measuring local observables on color codes.