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.
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.
We find that the overlap of a topological quantum color-code state, representing a quantum memory, with a factorized state of qubits can be written as the partition function of a three-body classical Ising model on triangular or Union Jack lattices. This mapping allows us to test that different computational capabilities of color codes correspond to qualitatively different universality classes of their associated classical spin models. By generalizing these statistical mechanical models for arbitrary inhomogeneous and complex couplings, it is possible to study a measurement-based quantum computation with a color-code state and we find that their classical simulability remains an open problem. We complement the measurement-based computation with the construction of a cluster state that yields the topological color code and this also gives the possibility to represent statistical models with external magnetic fields.
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.
We study mappings between distinct classical spin systems that leave the partition function invariant. As recently shown in [Phys. Rev. Lett. 100, 110501 (2008)], the partition function of the 2D square lattice Ising model in the presence of an inhomogeneous magnetic field, can specialize to the partition function of any Ising system on an arbitrary graph. In this sense the 2D Ising model is said to be "complete". However, in order to obtain the above result, the coupling strengths on the 2D lattice must assume complex values, and thus do not allow for a physical interpretation. Here we show how a complete model with real -and, hence, "physical"- couplings can be obtained if the 3D Ising model is considered. We furthermore show how to map general q-state systems with possibly many-body interactions to the 2D Ising model with complex parameters, and give completeness results for these models with real parameters. We also demonstrate that the computational overhead in these constructions is in all relevant cases polynomial. These results are proved by invoking a recently found cross-connection between statistical mechanics and quantum information theory, where partition functions are expressed as quantum mechanical amplitudes. Within this framework, there exists a natural correspondence between many-body quantum states that allow universal quantum computation via local measurements only, and complete classical spin systems.
A scheme for measuring complex temperature partition functions of Ising models is introduced. In the context of ordered qubit registers this scheme finds a natural translation in terms of global operations, and single particle measurements on the edge of the array. Two applications of this scheme are presented. First, through appropriate Wick rotations, those amplitudes can be analytically continued to yield esti-mates for partition functions of Ising models. Bounds on the estimation error, valid with high confidence, are provided and shown to be compatible with previous results. Interestingly, the kind of state prepa-rations and measurements involved in this application can in principle be made “instantaneous", i.e. independent of the system size or the parameters being simulated. Second, the scheme allows to accu-rately estimate some non-trivial invariants of links. A third result concerns the computational power of estimations of partition functions for real temperature classical ferromagnetic Ising models on a square lattice. We provide conditions under which estimating such partition functions allow to reconstruct scat-tering amplitudes of quantum circuits making the problem BQP-hard. Using this mapping, we show that wavefunction overlaps for ground states of quantum Hamiltonians, which can serve as a witness to quantum phase transitions, can be estimated from classical Ising model partition functions. Finally, we show that the ability to accurately measure corner magnetisations on thermal states of two-dimensional Ising models with magnetic field leads to fully polynomial random approximation schemes (FPRAS) for the partition function. Each of these results corresponds to a section of the text that can be essentially read independently. 1
We give efficient quantum algorithms to estimate the partition function of (i) the six-vertex model on a two-dimensional (2D) square lattice, (ii) the Ising model with magnetic fields on a planar graph, (iii) the Potts model on a quasi-2D square lattice and (iv) the Z 2 lattice gauge theory on a 3D square lattice.Moreover, we prove that these problems are BQP-complete, that is, that estimating these partition functions is as hard as simulating arbitrary quantum computation.The results are proven for a complex parameter regime of the models.The proofs are based on a mapping relating partition functions to quantum circuits introduced by Van den Nest et al (2009 Phys.Rev. A 80 052334) and extended here.
We study the problem of approximating the partition function of the transverse-field Ising model (TFIM), a widely studied quantum many-body model with important applications in quantum simulation and quantum annealing. Despite its fundamental importance, the algorithmic landscape for computing the TFIM partition function has remained poorly understood beyond restricted parameter regimes. We provide a precise characterization of the temperature regimes in which efficient approximation is possible, establishing a sharp computational phase transition. Let J denote the symmetric interaction matrix and Δ(J) = λ_{max}(J)-λ_{min}(J) denote its spectral width. We show that, for all inverse temperatures β ∈ [0,1/Δ(J)], there exists an efficient classical randomized algorithm that approximates the partition function tr(e^{-β H}) to within an arbitrarily small multiplicative factor. To obtain this result, we apply the standard Trotter decomposition to map the quantum model to a classical spin system, and then leverage new techniques in Markov chain analysis to derive an efficient algorithm that samples from and computes the partition function of the resulting distribution. This temperature threshold is tight: for β > 1/Δ(J), we show that there exists interaction matrix J for which approximating the partition function, even within an exponential factor, is NP-hard and thus is unlikely to admit an efficient classical or quantum algorithm.