The computation of classical Ising partition functions, coming from statistical physics, is a natural generalization of binary optimization. This is a notoriously hard problem in general, which makes it an especially interesting task to consider in the search for practical quantum advantage in near term quantum computers. In this work we view classical Ising models (on certain graphs) as quantum imaginary time evolution, which is enabled by the use of the transfer matrix mapping. We study this mapping from two points of view: (1) following Onsager and Kaufman’s original solution of the 2D Ising model, which serves as a starting point, we consider more general models and the possibility of a similar Lie-theoretic solution; (2) we consider quantum algorithms for the computation of partition functions and thermal averages via transfer matrices, which can be implemented either with block encodings inside larger unitaries or by approximating the state trajectories with unitary operators.
The computation of classical Ising partition functions, coming from statistical physics, is a natural generalization of binary optimization. This is a notoriously hard problem in general, which makes it an especially interesting task to consider in the search for practical quantum advantage in near term quantum computers. In this work we view classical Ising models (on certain graphs) as quantum imaginary time evolution, which is enabled by the use of the transfer matrix mapping. We study this mapping from two points of view: (1) following Onsager and Kaufman’s original solution of the 2D Ising model, which serves as a starting point, we consider more general models and the possibility of a similar Lie-theoretic solution; (2) we consider quantum algorithms for the computation of partition functions and thermal averages via transfer matrices, which can be implemented either with block encodings inside larger unitaries or by approximating the state trajectories with unitary operators.
We have thus far looked at the classical statistical mechanics of a collection of Ising spins in terms of their partition function. We have seen how to extract the free energy per site and correlation functions of the d = 1 Ising model. We will now consider a second way to do this. While the results are, of course, going to be the same, the method exposes a deep connection between classical statistical mechanics in d = 1 and the quantum mechanics of a single spin-12 particle. This is the simplest way to learn about a connection that has a much wider range of applicability: the classical statistical mechanics of a problem in d dimensions may be mapped on to a quantum problem in d – 1 dimensions. The nature of the quantum variable will depend on the nature of the classical variable. In general, the allowed values of the classical variable ( s =±1 in our example) will correspond to the maximal set of simultaneous eigenvalues of the operators in the quantum problem ( σz in our example). Subsequently we will study a problem where the classical variable called x lies in the range –∞ < x < ∞ and will correspond to the eigenvalues of the familiar position operator X that appears in the quantum problem. The correlation functions will become the expectation values in the ground state of a certain transfer matrix . The different sites in the d = 1 lattice will correspond to different, discrete, times in the life of the quantum degree of freedom. By the same token, a quantum problem may be mapped into a statistical mechanics problem in one-higher dimensions, essentially by running the derivation backwards. In this case the resulting partition function is also called the path integral for the quantum problem. There is, however, no guarantee that the classical partition function generated by a legitimate quantum problem (with a Hermitian Hamiltonian) will always make physical sense: the corresponding Boltzmann weights may be negative, or even complex! In the quantum mechanics we first learn, time t is a real parameter. For our purposes we also need to get familiar with quantum mechanics in which time takes on purely imaginary values t = –iτ , where τ is real. It turns out that it is possible to define such a Euclidean quantum mechanics .
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.
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.
Computing the partition function of the Ising model on a graph has been investigated from both sides of computer science and statistical physics, with producing fertile results of P cases, FPTAS/FPRAS cases, inapproximability and intractability. Recently, measurement-based quantum computing as well as quantum annealing open up another bridge between two fields by relating a tree tensor network representing a quantum graph state to a rank decomposition of the graph. This paper makes this bridge wider in both directions. An O∗(22ωbw(G))-time algorithm is developed for the partition function on n-vertex graph G with branch decomposition of width bw(G), where O* ignores a polynomial factor in n and ω is the matrix multiplication parameter less than 2.37287. Related algorithms of O∗(4rw(G~)) time for the tree tensor network are given which are of interest in quantum computation, given rank decomposition of a subdivided graph G~ with width rw(G~). These algorithms are parameter-exponential, i.e., O*(cp) for constant c and parameter p, and such an algorithm is not known for a more general case of computing the Tutte polynomial in terms of bw(G) (the current best time is O*(min{2n, bw(G)O(bw(G))})) with a negative result in terms of the clique-width, related to the rank-width, under ETH.
Instantaneous quantum polynomial-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 there is a classical algorithm that can simulate IQP efficiently, the polynomial hierarchy collapses to the third level, which is highly implausible. However, the origin of the classical intractability is still less understood. Here we establish a relationship between IQP and computational complexity of calculating the imaginary-valued partition functions of Ising models. We apply the established relationship in two opposite directions. One direction is to find subclasses of IQP that are classically efficiently simulatable by using exact solvability of certain types of Ising models. Another direction is applying quantum computational complexity of IQP to investigate (im)possibility of efficient classical approximations of Ising partition functions with imaginary coupling constants. Specifically, we show that a multiplicative approximation of Ising partition functions is #P-hard for almost all imaginary coupling constants even on planar lattices of a bounded degree.
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