Quantum Simulation/Quantum MonteCarlo
Resource type: this resource contains a lecture or lecture notes. 
Quantumclassical mapping[edit]
We have seen in the previous chapter that exact diagonalization is an impossible task for more than a few particles. In quantum MonteCarlo simulations, the goal is to avoid considering the full Hilbert space, but randomly sample the most relevant degrees of freedom and try to extract the quantities of interest such as the magnetization by averaging over a stochastic process. To pursue this goal, we first need to establish a framework in which we can interpet quantummechanical observables in terms of (classical) probabilities. This process is called a "quantumclassical mapping" and allows us to reformulate quantum manybody problems in terms of models from classical statistical mechanic, albeit in higher dimensions.
Suppose we wish to calculate the partition function of the transverse Ising model, as knowledge of the partition function allows us to calculate all thermodynamic quanties that may be of interest. Specifically, we have
where in the last line we have used the SuzukiTrotter expansion
which can be proved using the BakerCampbellHausdorff formula. Using the same expansion, we can replace the exponential of the product by a product of the exponentials, i.e.,

(1)
The exponentiation to the power of can be written as a product, and we can insert identity operators according to
Let us now look more closely at the product involving the spinflip operators , where we will encounter terms of the form
 .
The crucial part of the quantumclassical mapping is to interpret the partition function of the onedimensional chain containing spins as the partition function of a corresponding twodimensional spin model containing spin ^{[1]}. In this interpretation, we can rewrite the spinflip operators in terms of an Ising interaction in the direction (plus a constant energy shift),
We now want to cast these terms back into an exponential form,
where we find for the coefficents and
We can now insert this expression back into the partition function Eq.(1) and carry out the multiplications. The boundary conditions for the Ising interaction along the direction are fixed by the final trace operation; as the trace is implemented by multiplying from the left and from the right, we have periodic boundary conditions. In total, we obtain
The constant prefactor in the partition function is irrelevant as it will drop out when calculating thermodynamic observables. Consequently, we can identify a corresponding twodimensional classical Ising model with anisotropic interactions which reproduces the same thermodynamics as the onedimensional quantum Ising model in a transverse field. The Hamiltonian for the classical model is given by
Note, however, that the classical temperature is different from the quantum temperature . Nevertheless, we can now proceed to calculate the thermodynamic properties of the quantum model by performing classical MonteCarlo simulations.
Metropolis algorithm[edit]
When trying to evaluate thermodynamic observables for a classical spin model, we still find ourselves in considerable difficulties as also the classical configuration space grows exponentially with system size. However, we are not really interested in a solution that incorporates all microscopic details, but rather we want to obtain information about macroscopic observables. So, we will be fine with any microscopic description of the model of interest, as long as it gets the macroscopic statistics right. Here, the goal is to find a microscopic description which can be efficiently (i.e., using resources that only grow polynomially with system size) implemented on a computer.
The most famous method for the MonteCarlo simulation of statistical mechanics models is the Metropolis algorithm ^{[2]}. Let us first state the basic steps of the algorithm for the Ising model and then analyze it in more detail.
 Pick an arbitrary initial state (e.g., all spins polarized) and compute its energy .
 Flip a random spin and calculate the energy of the new configuration
 If , always accept the new configuration.
 If , accept the new configuration with probability .
 Continue at step 2 until the macroscopic observables (averaged over a fixed number of steps) are equilibrated.
To evaluate the algorithm, let us consider two configurations and with energies and ,respectively. The probalities for these configurations are denoted by , and . Let us assume that , so the transition probability satisfy and for the inverse process. In equilibrium, the system will satisfy detailed balance (absence of currents), i.e,
or equivalently
which reproduces the Boltzmann distribution and thus gives rise to the correct thermodynamic behavior. The convergence of the Metropolis algorithm can be improved by also including unphysical processes that flip a large domain of spins at once (socalled "cluster updates") ^{[3]}, as constructing these processes from individual spin flips will consume a lot of time. Fig. 1 shows results of MonteCarlo simulations for two different values of for the isotropic twodimensional Ising model.
From classical to quantum phase transitions[edit]
Let us now come back to the anisotropic Ising model that we obtained using the quantumclassical mapping. If we play around with and , we find that the phase transition between the paramagnet and the ferromagnet occurs on a critical line that is given by
where is the critical inverse temperature ^{[1]}. Remarkably, the condition at a fixed classical temperature means that the corresponding quantum phase transition takes place at , i.e., at zero temperature. At finite temperature, the extension in the direction will be finite and the classical model belongs to the universality class of the onedimensional Ising model, which does not exhibit a phase transition. If we substitute the definitions for the coupling constants into the equation for the critical line, we obtain
which immediately gives us the critical transverse field , in agreement with the exact solution of the quantum model. From our knowledge of the classical 2D Ising model, we can also immediate extract the scaling of observables close to the critical point, e.g., for the magnetization
as the critical exponents for the 1D quantum model are identical to the ones of the classical 2D model.
The sign problem[edit]
While quantum MonteCarlo methods are indeed very powerful for tackling a large variety of manybody problems, they are also constrained by inherent limitations. One possible problem we can run into is that the partition function of the classical model cannot be computed efficiently. For example, consider the classical Hamiltonian
on a threedimensional cubic lattice, where the nearestneighbor interactions are randomly chosen from the values . This model exhibits glassy behavior and finding its ground state is known to be NPcomplete ^{[4]}, i.e., it is widely believed that there is no efficient way to simulate this model. On the other hand, we can safely assume that precisely due to the glassy properties that makes the model hard to study, the ground state is irrelevant as a physical state as the system will take exponentially long to reach it even if we put it into heat bath at zero temperature. A more subtle issue can arise as the result of the quantumclassical mapping, which is known as the "sign problem".
To be explicit, let us assume that during our quantumclassical mapping procedure, we encounter the following term in the Hamiltonian:
where we have used the spinflip operators and . Within the quantumclassical mapping, we will encounter terms of the form
The constant term and the Ising interaction are unproblematic and can be cast into the classical partition function as in the case of the transverse Ising model. Whether we can do the same for the spinflip term (which will ultimately result in a fourbody interaction for the classical Ising spins), depends on the sign of . For the ferromagnetic case, , the coefficient will be positive and we can turn this interaction into a term of the form with being positive so the interpretation in terms of a classical partition function remains valid. On the other hand, for an antiferromagnetic interaction with , we find to be negative and therefore we do not obtain the equivalent of a classical partition function. In some cases, we can work around this by using a unitary transformation that maps onto a model that does not exhibit this problem. For instance on a bipartite lattice, we can fix this problem by flipping spins on one of the sublattices by transforming , turning the antiferromagnetic interaction into a ferromagnetic one. However, this does not work in general, nevertheless there is still a way to perform classical MonteCarlo sampling. When sampling over our classical configuration space, the problematic contributions correspond to negative probabilities, i.e., when we compute the value of an observable ,
we find some of the to be negative. This can be resolved by taking the absolute value of these probabilities and dividing by the expectation value of the sign, i.e.,
However, this modification comes at a hefty price: as the uncertainty of the denominator will typically increase exponentially with the size of the system ^{[5]}, we will no longer have an efficient algorithm.
Despite these difficulties, it may sometimes still be more favorable to perform MonteCarlo simulation than performing exact diagonalization, but this certainly depends on details of the model at hand. Finally, the sign problem is not limited to models of the type outlined above. As a rough guidance, frustrated spin models and fermionic models tend to have a sign problem, while bosonic models tend to be free of it.
References[edit]
 ↑ ^{1.0} ^{1.1} Batrouni, G.G; Scalettar, R. T. (20110505). "Quantum phase transitions". In Christian Miniatura, LeongChuan Kwek, Martial Ducloy, Benoît Grémaud, BertholdGeorg Englert, Leticia Cugliandolo, Artur Ekert, and Kok Khoo Phua (eds.) (eds.). Ultracold Gases and Quantum Information. Oxford University Press. ISBN 9780199603657. Retrieved 20130409.CS1 maint: uses editors parameter (link)
 ↑ Metropolis, Nicholas; Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, Edward Teller (19530601). "Equation of State Calculations by Fast Computing Machines". The Journal of Chemical Physics 21 (6): 10871092. doi:doi:10.1063/1.1699114. ISSN 00219606. http://jcp.aip.org/resource/1/jcpsa6/v21/i6/p1087_s1. Retrieved 20130411.
 ↑ Krauth, Werner (2004). "Cluster Monte Carlo algorithms". In Alexander K Hartmann and Heiko Rieger (ed.) (eds.). New optimization algorithms in physics. Weinheim; Chichester: WileyVCH ; John Wiley. ISBN 3527404066 9783527404063 Check
isbn=
value: length (help).CS1 maint: uses editors parameter (link)  ↑ Barahona, F. (19821001). "On the computational complexity of Ising spin glass models". Journal of Physics A: Mathematical and General 15 (10): 3241. doi:10.1088/03054470/15/10/028. ISSN 03054470. http://iopscience.iop.org/03054470/15/10/028. Retrieved 20130416.
 ↑ Troyer, Matthias; UweJens Wiese (20050504). "Computational Complexity and Fundamental Limitations to Fermionic Quantum Monte Carlo Simulations". Physical Review Letters 94 (17): 170201. doi:10.1103/PhysRevLett.94.170201. http://link.aps.org/doi/10.1103/PhysRevLett.94.170201. Retrieved 20130416.