We consider a family of quantum spin systems which includes, as special cases, the ferromagnetic XY model and ferromagnetic Ising model on any graph, with or without a transverse magnetic field. We prove that the partition function of any model in this family can be efficiently approximated to a given relative error ε using a classical randomized algorithm with runtime polynomial in ε^{-1}, system size, and inverse temperature. As a consequence, we obtain a polynomial time algorithm which approximates the free energy or ground energy to a given additive error. We first show how to approximate the partition function by the perfect matching sum of a finite graph with positive edge weights. Although the perfect matching sum is not known to be efficiently approximable in general, the graphs obtained by our method have a special structure which facilitates efficient approximation via a randomized algorithm due to Jerrum and Sinclair.
This paper discusses a classical simulation to compute the partition function (or free energy) of generic one-dimensional quantum many-body systems. Many numerical methods have previously been developed to approximately solve one-dimensional quantum systems. However, there exists no exact proof that arbitrary one-dimensional quantum Gibbs states can be efficiently solved by a classical computer. Therefore, the aim of this paper is to prove this with the clustering properties for arbitrary finite temperatures
β−1. We explicitly show an efficient algorithm that approximates the partition function up to an error
ε with a computational cost that scales as
n⋅poly(1/ε), where the degree of the polynomial depends on
β as
eO(β). Extending the analysis to higher dimensions at high temperatures, we obtain a weaker result for the computational cost n\cdot (1/ε)^{\log^{D-1} (1/ε)}, where
D is the lattice dimension.
We exploit a recently constructed mapping between quantum circuits and graphs in order to prove that circuits corresponding to certain planar graphs can be efficiently simulated classically. The proof uses an expression for the Ising model partition function in terms of quadratically signed weight enumerators (QWGTs), which are polynomials that arise naturally in an expansion of quantum circuits in terms of rotations involving Pauli matrices. We combine this expression with a known efficient classical algorithm for the Ising partition function of any planar graph in the absence of an external magnetic field, and the Robertson–Seymour theorem from graph theory. We give as an example a set of quantum circuits with a small number of non-nearest-neighbor gates which admit an efficient classical simulation.
We provide a quantum algorithm for the exact evaluation of the Potts partition function for a certain class of restricted instances of graphs that correspond to irreducible cyclic codes. We use the same approach to demonstrate that quantum computers can provide an exponential speed up over the best classical algorithms for the exact evaluation of the weight enumerator polynomial for a family of classical cyclic codes. In addition to this we also provide an efficient quantum approximation algorithm for a function (signed-Euler generating function) closely related to the Ising partition function and demonstrate that this problem is BQP-complete. \n\nWe accomplish the above for the Potts partition function by using a series of links between Gauss sums, classical coding theory, graph theory and the partition function. We exploit the fact that there exists an efficient approximation algorithm for Gauss sums and the fact that this problem is equivalent in complexity to evaluating discrete log. A theorem of McEliece allows one to turn the Gauss sum approximation into an exact evaluation of the Potts partition function. Stripping the physics from this result leaves one with the result for the weight enumerator polynomial. \n\nThe result for the approximation of the signed-Euler generating function was accomplished by fashioning a new mapping between quantum circuits and graphs. The mapping provided us with a way of relating the cycle structure of graphs with quantum circuits. Using a slight variant of this mapping, we present the final result of this thesis which presents a way of testing families of quantum circuits for their classical simulatability. We thus provide an efficient way of deciding whether a quantum circuit provides any additional computational power over classical computation and this is achieved by exploiting the fact that planar instances of the Ising partition function (with no external magnetic field) can be efficiently classically computed.
Quantum impurity models are paradigmatic models of interacting quantum matter, as well as key computational primitives for modern electronic-structure methods. They describe a small subsystem of interacting fermions coupled to a large, noninteracting bath. We perform a comprehensive study of the computational complexity of simulating impurity models, delineating the boundary between classical and quantum tractability for this class of problems. Our main finding is that static properties of quantum impurity models can be calculated efficiently on a classical computer. Specifically, we give classical algorithms that (1) estimate the ground-state energy to additive precision
δ in time
poly(n,δ−1), and (2) estimate the partition function at inverse temperature
β to relative precision
δ in time
poly(n,β,δ−1), where
n is the system size. These results improve the previous best-known complexity for ground-state energy estimation from quasipolynomial to polynomial time, while establishing for the first time rigorous polynomial-time guarantees for simulating impurity models in thermal equilibrium. On the other hand, we find that simulating dynamical properties of impurity models is hard for classical computers but easy on a quantum computer. As a canonical example, we show that computing their nonequilibrium Green's functions captures the full power of quantum computation, even at finite temperature. Taken together, our results rule out superpolynomial quantum speedups for computing static properties, but provide an avenue for quantum advantage in simulating impurity physics out of equilibrium.
We study the transverse field Ising model, defined by the Hamiltonian
H=21∑i,j∈[n]JijZiZj+∑i=1nhizZi+η∑iXi where $J $ is the symmetric interaction matrix, and
η is the transverse field strength. Let
Δ(J)=λmax(J)−λmin(J) be the spectral width of
J. When the inverse temperature
β≥0 satisfies
Δ(J)⋅ηtanh(βη)≤1, we give a randomized classical algorithm that approximates the partition function
Z(β)=Tr(e−βH) to a given relative error
ε∈(0,1) in time polynomial in
n,
β, the model parameters, and
ε−1. When $ Δ(J) \cdot \frac{\tanh(βη)}η > 1 ,$ we show that approximating $ Z(β)$ within an
exp(o(n))-multiplicative factor is
NP-hard, and thus unlikely to admit an efficient classical or quantum algorithms under standard complexity theoretic assumptions. Furthermore, in the regime
Δ(J)⋅ηtanh(βη)≤1, we provide an efficient randomized classical algorithm that approximates Pauli string observables of the Gibbs state $ ρ_β= \frac{e^{-βH}}{\operatorname{Tr}(e^{-βH})}$ within an arbitrarily small additive error. In the special case when the observable is also diagonal in the
X-basis, i.e.
P∈{I,X}⊗n, the algorithm further achieves arbitrarily small relative error.