{'fraction_non_alphanumeric': 0.032211110811612174, 'fraction_numerical': 0.008598614517911534, 'mean_word_length': 4.62291603516217, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Meron-Cluster Solution of Fermion and Other Sign Problems

Numerical simulations of numerous quantum systems suffer from the notorious sign problem. Important examples include QCD and other field theories at non-zero chemical potential, at non-zero vacuum angle, or with an odd number of flavors, as well as the Hubbard model for high-temperature superconductivity and quantum antiferromagnets in an external magnetic field. In all these cases standard simulation algorithms require an exponentially large statistics in large space-time volumes and are thus impossible to use in practice. Meron-cluster algorithms realize a general strategy to solve severe sign problems but must be constructed for each individual case. They lead to a complete solution of the sign problem in several of the above cases.


Introduction
Sign problems prevent the numerical solution of several important problems in physics. For example, QCD and other field theories at non-zero chemical potential or at non-zero vacuum angle have a complex action and hence complex Boltzmann weights which cannot be interpreted as probabilities in a Monte Carlo calculation. When the complex phase of the Boltzmann factor is included in measured observables, the fluctuations of the phase give rise to dramatic cancellations. Especially for large systems at low temperatures this leads to relative statistical errors that are exponentially large in both the volume and the inverse temperature. Similarly, the minus-signs that arise as a consequence of Fermi statistics cause severe sign problems in numerical simulations of strongly correlated electron systems such as the Hubbard model for high-temperature superconductors. Another class of systems that suffer from a sign problem are frustrated quantum spin systems -for example, quantum antiferromagnets in an external magnetic field. In all these cases it is impossible in practice to study these systems with standard numerical methods.
Recently, it has been shown to be possible to completely solve some severe sign problems using meron-cluster algorithms [1,2]. The solution of the problem proceeds in two steps. The idea of the first step is to decompose a field config-uration into independent clusters whose flip affects the sign in a definite way. Clusters whose flip changes the sign are referred to as merons. The flip of a meron-cluster leads to an exact cancellation between two contributions ±1. Using an improved estimator, this reduces the problem of canceling many contributions ±1 to the problem of averaging over non-negative contributions 0 and 1. An algorithm based on this first step has been successfully applied to the simulation of a bosonic model with a complex action -the 2-d O(3) model at non-vanishing θ-vacuum angle [3]. In this model the sign-changing clusters are halfinstantons -thus the name meron. However, the improved estimator alone solves only one half of the sign problem because most of the time one generates contributions of 0 to the average sign and very rarely one encounters a contribution of 1. In order to solve the other half of the problem a second step is necessary which guarantees that contributions of 0 and 1 are generated with similar probabilities. The idea behind the second step is to include a Metropolis decision in the process of cluster decomposition. The two basic ideas behind the algorithm are general and can be applied to a variety of systems. However, even though the meron concept is universal, the meron-cluster algorithm must be constructed for each individual case. Here we present several cases, from both particle and condensed matter physics, in which a meron-cluster algorithm has led to a complete solution of a severe sign problem.

General Nature of the Sign Problem
First of all, it should be stressed that the sign problem is strongly influenced by the choice of basis for the physical Hilbert space. When one constructs a path integral representation of a quantum statistical partition function Z = Tr exp(−βH), (1) one divides the Euclidean time interval of extent β into M small time-steps of size ǫ (with β = M ǫ) and one inserts complete sets of basis states |n between the operators exp(−ǫH). The product of the resulting transfer matrix elements n| exp(−ǫH)|n ′ defines the Boltzmann factor. Depending on the choice of basis |n , the Boltzmann weight may be positive, negative or even complex. When the Boltzmann weight is complex, one can always restrict oneself to the real part, because the total partition function is always real (as long as H is Hermitean The average sign in the modified ensemble is given by The last equality points to the heart of the sign problem. The expectation value of the sign is exponentially small in both the volume V and the inverse temperature β because the difference between the free energy densities ∆f = f − f ′ of the original and the modified systems is necessarily positive. Even in an ideal simulation of the modified ensemble which generates N completely uncorrelated configurations, the relative statistical error of the sign is Here we have used that Sign 2 = 1. To determine the average sign with sufficient accuracy one needs to generate on the order of N = exp(2βV ∆f ) configurations. For large volumes and small temperatures this is impossible in practice. It is possible to solve one half of the problem if one can match any contribution −1 with another contribution 1 to give 0, such that only a few unmatched contributions 1 remain. Then effectively Sign = 0, 1 and hence Sign 2 = Sign. This reduces the relative error to One gains an exponential factor in statistics, but one still needs to generate N ′ = √ N = exp(βV ∆f ) independent configurations in order to determine the average sign accurately. This difficulty still arises because one generates exponentially many vanishing contributions before one encounters a contribution 1. As explained below, in the meron-cluster algorithm an explicit matching of contributions −1 and 1 is achieved using an improved estimator. This step solves one half of the sign problem. In a second step involving a Metropolis decision, the algorithm ensures that contributions 0 and 1 occur with similar probabilities. This step saves another exponential factor in statistics and solves the other half of the sign problem.

Chiral Phase Transition with Staggered Fermions 2
To illustrate the power of the meron-cluster algorithm, we apply it to a model of (3 + 1)-d staggered fermions in the Hamiltonian formulation. The model has N = 2 flavors and a Z Z(2) chiral symmetry that is spontaneously broken at low temperatures. The fermion determinant can be negative in this model. Hence, due to the sign problem, standard fermion algorithms fail in this case. The meron-cluster algorithm is the only numerical method available to simulate this model. In our method we do not integrate out the fermions but describe them in a Fock state basis. The resulting bosonic model of fermion occupation numbers interacts locally, but has a non-local fermion permutation sign resulting from the Pauli exclusion principle. Standard numerical methods would suffer from severe cancellations of positive and negative contributions to the partition function. Like other cluster methods, the meron-cluster algorithm decomposes a configuration of fermion occupation numbers into clusters which can be flipped independently. Under a cluster flip an occupied site becomes empty and vice versa. The main idea of the meron-cluster algorithm is to construct the clusters such that they affect the fermion sign independently when they are flipped. In addition, it must always be possible to flip the clusters into a reference configuration with a positive sign. Like other cluster algorithms, the meron algorithm substantially reduces critical slowing down. This advantage allows us to work directly in the chiral limit.
We consider staggered fermions hopping on a 3-d cubic spatial lattice with V = L 3 sites x (L even) and with periodic or antiperiodic spatial boundary conditions. We start in the Hamiltonian formulation and then derive a path integral on a (3 + 1)-d Euclidean space-time lattice. The fermions are described by creation and annihilation operators Ψ + x and Ψ x with standard anticommutation relations The staggered fermion Hamilton operator takes the form that is a sum of nearest-neighbor couplings h x,i and a mass term mΨΨ. From here on, we work directly in the chiral limit m = 0, and only use ΨΨ as an observable. The term h x,i couples the fermion operators at the lattice sites x and x +î, whereî is a unit-vector in the i-direction, and Here η x,1 = 1, η x,2 = (−1) x1 and η x,3 = (−1) x1+x2 are the standard staggered fermion sign factors and G is a four-fermion coupling constant.
To construct a path integral for the partition function, we decompose the Hamilton operator into six terms H = H 1 + H 2 + ... + H 6 with The individual contributions to a given H i commute with each other, but two different H i do not commute. Using the Suzuki-Trotter formula, we express the fermionic partition function at inverse temperature β as We have introduced 6M Euclidean time slices with ǫ = β/M being the lattice spacing in the Euclidean time direction. Following Jordan and Wigner [4] we represent the fermion operators by Pauli matrices with Here l labels the lattice point x.
We now insert complete sets of fermion Fock states between the factors exp(−ǫH i ). Each site is either empty or occupied, i.e. n x has eigenvalue 0 or 1. In the Pauli matrix representation this corresponds to eigenstates |0 and |1 of σ 3 l with σ 3 l |0 = −|0 and σ 3 l |1 = |1 . The transfer matrix is a product of factors which is a 4×4 matrix in the Fock space basis |00 , |01 , |10 and |11 of two sites x and x +î. Here Σ = η x,i σ 3 l+1 σ 3 l+2 ...σ 3 m−1 includes the local sign η x,i as well as a non-local string of Pauli matrices running over consecutive labels between l and m, where l labels the lattice point x and m labels x +î. Note that Σ is diagonal in the occupation number basis.
The partition function is now expressed as a path integral Z = n Sign[n] exp(−S[n]) over configurations of occupation numbers n(x, t) = 0, 1 on a (3 + 1)-d space-time lattice of points (x, t). The Boltzmann factor is a product of space-time plaquette contributions with an action S[n(x, t), n(x +î, t), n(x, t + 1), n(x +î, t All the other Boltzmann weights are zero. The sign of a configuration, Sign[n], also is a product of space-time plaquette contributions Sign[n(x, t), n(x +î, t), n(x, t + 1), n(x +î, t + 1)] with It should be noted that Σ gets contributions from all lattice points with labels between l and m. This seems to make an evaluation of the fermion sign rather tedious. Also, it is not a priori obvious that Sign[n] is independent of the arbitrarily chosen order of the lattice points. Fortunately, there is a simple way to compute Sign[n], which is directly related to the Pauli exclusion principle and is manifestly order-independent. In fact, Sign[n] has a topological meaning. The occupied lattice sites define fermion world-lines which are closed around the Euclidean time direction.
Of course, during their Euclidean time evolution fermions can interchange their positions and the fermion world-lines define a permutation of particles. The Pauli exclusion principle dictates that the fermion sign is just the sign of that permutation. If we work with antiperiodic spatial boundary conditions, Sign[n] receives an extra minussign for every fermion world-line that crosses a spatial boundary. Figure 1 shows two configurations of fermion occupation numbers in (1 + 1) dimensions. The first configuration corresponds to two fermions at rest and has Sign[n] = 1.
In the second configuration two fermions interchange their positions with one fermion stepping over the spatial boundary. If one uses periodic spatial boundary conditions this configuration has Sign[n] = −1. Note that the same configuration would have Sign[n] = 1 when antiperiodic boundary conditions are used. Quantities of physical interest are the chiral condensate x t Figure 1. Two configurations of fermion occupation numbers in (1 + 1) dimensions. The shaded plaquettes carry the interaction. The dots represent occupied sites. In the second configuration, two fermions interchange their positions. The fat line represents a meron-cluster. Flipping this cluster changes one configuration into the other and changes the fermion sign.
and the corresponding chiral susceptibility Up to now we have derived a path integral representation for the fermion system in terms of bosonic occupation numbers and a fermion sign factor that encodes Fermi statistics. The system without the sign factor is bosonic and is characterized by the positive Boltzmann factor exp(−S[n]). Here the bosonic model is a quantum spin system with the Hamiltonian where S i x = 1 2 σ i l is a spin 1/2 operator associated with the lattice site x that was labeled by l. From here on, we restrict ourselves to G = 1, which corresponds to the antiferromagnetic quantum Heisenberg model. In the language of the spin model, the chiral condensate turns into the staggered magnetization The meron-cluster fermion algorithm is based on a cluster algorithm for the corresponding bosonic model without the sign factor. Bosonic quantum spin systems can be simulated very efficiently with cluster algorithms [5][6][7]. The first cluster algorithm for lattice fermions was described in [8].
These algorithms can be implemented directly in the Euclidean time continuum [9], i.e. the Suzuki-Trotter discretization is not even necessary. The decomposition of the lattice into clusters results from connecting neighboring sites on each individual space-time interaction plaquette following probabilistic cluster rules. A sequence of connected sites defines a cluster. In this case the clusters are sets of closed loops. The cluster rules are constructed to obey detailed balance. To show this constraint we write the plaquette Boltzmann factors as e −S[n(x,t),n(x+î,t),n(x,t+1),n(x+î,t+1)] = Aδ n(x,t),n(x,t+1) δ n(x+î,t),n(x+î,t+1) + Bδ n(x,t),1−n(x+î,t) δ n(x,t+1),1−n(x+î,t+1) .
The δ-functions specify which sites are connected and thus belong to the same cluster. The quantities A and B determine the relative probabilities for different cluster break-ups of an interaction plaquette. Inserting the expressions from eq.(15) one finds . Indeed, this is the algorithm that was used in [10]. It is extremely efficient, has almost no detectable autocorrelations, and has a dynamical exponent for critical slowing down that is compatible with zero. The cluster rules are illustrated in table 1. Table 1 Cluster break-ups of various plaquette configurations together with their relative probabilities A and B. The dots represent occupied sites and the fat lines are the cluster connections.
Eq.(21) can be viewed as a representation of the original model as a random cluster model. The cluster algorithm operates in two steps. First, a cluster break-up is chosen for each space-time interaction plaquette according to the above probabilities. This step effectively replaces the original Boltzmann weight of a plaquette configuration with a set of constraints represented by the δ-functions associated with the chosen break-up. The constraints imply that occupation numbers of connected sites can only be changed together. Second, every cluster is flipped with probability 1/2. When a cluster is flipped the occupation numbers of all sites that belong to the cluster are changed. Eq.(22) ensures that the cluster algorithm obeys detailed balance.
Let us now consider the effect of a cluster flip on the fermion sign. Each cluster can be characterized by its effect on the fermion sign independent of the orientation of all the other clusters. We refer to clusters whose flip changes Sign[n] as merons, while clusters whose flip leaves Sign[n] unchanged are called non-merons. The flip of a meron-cluster permutes the fermions and changes the topology of the fermion world-lines. The number of merons in a configuration is always even. An example of a meron-cluster is given in figure 1.
The meron concept alone allows us to gain an exponential factor in statistics. Since all clusters can be flipped independently, one can construct an improved estimator for Sign[n] by averaging analytically over the 2 NC configurations obtained by flipping the N C clusters in the configuration in all possible ways. For configurations that contain merons the average Sign[n] is zero because flipping a single meron leads to a cancellation of contributions of ±1. Hence, only the configurations without merons contribute to Sign . The vast majority of configurations contains merons and now contributes an exact 0 to Sign instead of a statistical average of contributions ±1. In fact, one can show that the contributions from the zero-meron sector are always positive, such that Sign[n] is 0 for configurations containing meronclusters and 1 in the zero-meron sector. According to the previous discussion, this method solves one half of the fermion sign problem. Before we can solve the other half of the problem we must discuss improved estimators for the physical observables.
Let us consider an improved estimator for (ΨΨ[n]) 2 Sign[n] which is needed to determine the chiral susceptibility χ. The total chiral condensate, ΨΨ[n] = C ΨΨ C is a sum of cluster contributions When a cluster is flipped, its condensate contri- where N is the number of meron-clusters in a configuration. Thus, to determine χ one must only sample the zero-and two-meron sectors.
The probability to find a configuration without merons is exponentially small in the spacetime volume since it is equal to Sign . Thus, although we have increased the statistics tremendously with the improved estimators, without a second step one would still need exponentially large statistics to accurately determine χ. Fortunately, the numerator in equation (24) receives contributions from the zero-and two-meron sectors only, while the denominator gets contributions only from the zero-meron sector. One can hence restrict oneself to the zero-and two-meron sectors and never generate configurations with more than two merons. This enhances both the numerator and the denominator by a factor that is exponentially large in the volume, but leaves the ratio of the two invariant. One purpose of the second step of the meron-cluster algorithm is to eliminate all configurations with more than two merons. To achieve this, we start with an initial configuration with zero or two merons. For example, a completely occupied configuration has no merons. We then visit all plaquette interactions one after the other and choose new pair connections between the four sites according to the above cluster rules. If the new connection increases the number of merons beyond two, it is not accepted and the old connection is kept for that plaquette. This procedure obeys detailed balance because configurations with more than two merons do not contribute to the observable we consider. This simple reject step eliminates almost all configurations with weight 0 and is the essential step to solving the second half of the fermion sign problem.
We have simulated the staggered fermion model with G = 1 on antiperiodic spatial volumes L 3 with L = 4, 6, ..., 16 and at various inverse temperatures β ∈ [0.5, 1.2] which includes the critical point. In the Euclidean time direction we have used M = 4, i.e. 24 time-slices. In all cases, we have performed at least 1000 thermalization sweeps followed by 10000 measurements. One sweep consists of a new choice of the cluster connections on each interaction plaquette and a flip of each cluster with probability 1/2.  Figure 3 shows the probability to have a certain number of merons in an algorithm that samples all meron-sectors. For small volumes the zero-meron sector and hence Sign is relatively large, while multi-meron configurations are rare. On the other hand, in larger volumes the vast majority of configurations has a large number of merons and hence Sign is exponentially small. For example, an extrapolation from smaller volumes gives a rough estimate Sign ≈ 10 −20 on the 16 3 lattice at β = 0.948. Hence, to achieve a similar accuracy without the meron-cluster algorithm one would have to increase the statistics by a factor 10 40 , which is obviously impossible in practice.
To study the critical behavior in detail, we have performed a finite-size scaling analysis for χ focusing on a narrow range β ∈ [0.9, 0.98] around the critical point. Since a Z Z(2) chiral symmetry gets spontaneously broken at finite temperature in this (3 + 1)-d model, one expects to find the critical behavior of the 3-d Ising model. For the 3-d Ising model the critical exponents are given by ν = 0.630(1) and γ/ν = 1.963(3). Fitting to our data, we find ν = 0.63(4) and γ/ν = 1.98 (2), which indicates that the chiral transition of the staggered fermion model is indeed in the 3-d Ising universality class. In figure 3 we have taken the values of the critical exponents from the 3-d Ising model and we have plotted χ/L γ/ν as a function of y = (β − β c )L 1/ν . Indeed all data collapse onto one universal curve.

Quantum Antiferromagnets in a Magnetic Field 4
As another problem of physical interest we consider antiferromagnetic quantum spin ladders in an external uniform magnetic field that competes with the spin-spin interaction. The competing interactions lead to a severe sign problem in numerical simulations. The most efficient algorithm for simulating quantum spin systems in the absence of an external magnetic field is the loop cluster algorithm [6,10,7] which can be implemented directly in the Euclidean time continuum [9]. This algorithm also underlies our staggered  fermion simulations and was described in detail in section 3. In the presence of a magnetic field pointing along the quantization axis of the spins, the Z Z(2) symmetry that allows the clusters to be flipped with probability 1/2 is explicitly broken. As a consequence, for large values of the magnetic field some clusters can only be flipped with very small probability and the algorithm becomes inefficient. An alternative strategy is to choose the spin quantization axis perpendicular to the direction of the magnetic field. Then all clusters can still be flipped with probability 1/2. This indeed leads to an efficient algorithm for ferromagnets in an external uniform magnetic field. Unfortunately, for antiferromagnets i.e. when the magnetic field competes with the spin-spin interaction -this formulation of the problem leads to a very severe sign problem. Here we show how this sign problem can be solved completely using a meroncluster algorithm.
Antiferromagnetic spin ladders -sets of several transversely coupled quantum spin chainsare interesting condensed matter systems which interpolate between single 1-d spin chains and 2-d quantum antiferromagnets. The ladders are spatially quasi 1-d systems whose low-energy dynamics are governed by (1 + 1)-d quantum field theories. We consider spin ladders in an external uniform magnetic field B, which corresponds to a chemical potential µ = B/c in the corresponding (1 + 1)-d quantum field theory. Chakravarty, Halperin and Nelson used a (2 + 1)-d effective field theory to describe the low-energy dynamics of spatially 2-d quantum antiferromagnets [11]. Chakravarty has applied this theory to quantum spin ladders with a sufficiently large even number of coupled spin 1/2 chains [12]. We consider spin ladders with the same value of the antiferromagnetic coupling along and between the chains. These systems are described by the action Here e(x, y, t) is a unit-vector field, ρ s is the spin stiffness and c is the spin-wave velocity. The coupled spin chains are oriented in the spatial x-direction with a large extent L, while the transverse y-direction has a much smaller extent L ′ ≪ L. Here we consider spin ladders with periodic boundary conditions in the transverse direction, and we limit ourselves to an even number of coupled spin 1/2 chains. The effective action for a ladder with an odd number of coupled chains would contain an additional topological term. When the spin ladder is placed in a uniform external magnetic field B, the field couples to a conserved quantity -the uniform magnetization. Hence, on the level of the effective theory, the magnetic field plays the role of a chemical potential -i.e. it appears as the time-component of an imaginary constant vector potential. The ordinary derivative ∂ t e is replaced by the covariant derivative ∂ t e + i B × e. For a sufficiently large even number of coupled chains (L ′ ≫ c/ρ s ) the ladder system undergoes dimensional reduction to the (1 + 1)-d O(3) symmetric quantum field theory with the action The effective coupling constant is given by 1/g 2 = ρ s L ′ /c and the magnetic field appears as a chemical potential of magnitude µ = B/c. We consider a system of quantum spins 1/2 on a d-dimensional cubic lattice with site label x and with periodic spatial boundary conditions. In particular, we are interested in ladder systems on a 2-d rectangular lattice of size L × L ′ with L ≫ L ′ . The spins located at the sites x are described by operators S i x with the usual commutation relations The Hamilton operator with J > 0, couples the spins at the lattice sites x and x +î, whereî is a unit-vector in the i- The central observable of our study is the uniform magnetization The expectation value of the magnetization M in the direction of the magnetic field is non-zero. The cluster algorithm for the quantum antiferromagnet is very similar to the one for stag- The probability to connect spins with their timelike neighbors is C/(C + D). The spins remain disconnected with probability D/(C + D). Inserting the expressions from eq.(30) one obtains C + D = cosh(ǫB/2), C = sinh(ǫB/2).
The cluster rules for the space-time plaquette terms are the same as in  Table 2 Cluster break-ups of time-like bond configurations together with their probabilities C and D. Filled dots represent spin up, open circles represent spin down, and the fat black line is the cluster connection.
The above cluster rules were first used in a simulation of the Heisenberg antiferromagnet [10] in the absence of a magnetic field. In that case there is no sign problem. Then the corresponding loop-cluster algorithm is extremely efficient and has almost no detectable autocorrelations. When a magnetic field is switched on the situation changes. When the magnetic field points in the direction of the spin quantization axis (the 3-direction in our case) there is no sign problem. However, the magnetic field then explicitly breaks the Z Z(2) flip symmetry on which the cluster algorithm is based, and the clusters can no longer be flipped with probability 1/2. Instead the flip probability is determined by the value of the magnetic field and by the magnetization of the cluster. When the field is strong, flips of magnetized clusters are rarely possible and the algorithm becomes very inefficient. To avoid this, we have chosen the magnetic field to point perpendicular to the spin quantization axis. In that case, the cluster flip symmetry is not affected by the magnetic field, and the clusters can still be flipped with probability 1/2. However, now a severe sign problem arises.
One can construct an improved estimator for the magnetization M , which gets non-vanishing contributions only from the zero-meron sector. Hence, it is unnecessary to generate any configurations that contain meron-clusters. In practice it is advantageous to occasionally generate configurations containing merons even though they do not contribute to our observable, because this reduces the autocorrelation times.  Figure 5. Thermalization of the magnetization for the loop-cluster algorithm versus the meroncluster algorithm. For B = J the loop algorithm takes more than 100000 sweeps to reach equilibrium while the meron-cluster algorithm has no thermalization problem.
We have performed numerical simulations with the meron-cluster algorithm for various quantum antiferromagnets in a uniform magnetic field B.
To demonstrate the efficiency of the algorithm, we have compared it with the standard loop-cluster algorithm. In case of the loop algorithm the magnetic field points in the direction of the spin quantization axis. In the meron-cluster algorithm, on the other hand, the magnetic field is perpendicular to the spin quantization axis and all clusters can still be flipped with probability 1/2. Of course the sign problem arises, but it is solved completely by the meron-cluster algorithm.   In the infinite volume, zero temperature limit one expects the magnetization to vanish for B < B c . The critical magnetic field B c corresponds to the critical chemical potential µ = B c /c = m, determined by the mass gap m of the (1 + 1)-d O(3) model. The expected behavior is indeed consistent with the numerical data.

Strongly correlated Electron Systems 3
Quantum Antiferromagnets may turn into high-temperature superconductors when they are doped with additional charge carriers. These systems are believed to be well described by the Hubbard model Hamiltonian Here Ψ + x,s and Ψ x,s are creation and annihilation operators for electrons with spin s =↑, ↓ hopping on the sites x of a quadratic lattice. The chemical potential µ couples to the occupation number per site n x = n x,↑ + n x,↓ = Ψ + x,↑ Ψ x,↑ + Ψ + x,↓ Ψ x,↓ and is used to dope the system away from half-filling. So far, high-temperature superconductivity has not been demonstrated convincingly in numerical simulations due to a very severe fermion sign problem. It is natural to ask if a meron-cluster algorithm can be used to solve this problem. Unfortunately, as it stands the meron concept does not apply directly to the Hubbard model because the clusters influence each other in their effect on the fermion sign.
Meron-cluster algorithms can solve the sign problem when two conditions are satisfied. First, the clusters must be independent in their effect on the sign in order to allow the construction of improved estimators. Second, it must always be possible to flip the clusters into a reference configuration with a positive sign. In case of the Hubbard model a completely antiferromagnetically ordered reference configuration suggests itself. In order to construct an efficient meron-cluster algorithm 3 Based on a talk presented by J. Cox based on that reference configuration, one must modify the original Hubbard model Hamiltonian. Of course, one would like to maintain the symmetry properties of the original Hamiltonian in order to stay in the same universality class. An obvious symmetry is the SU (2) s spin rotational symmetry that is generated by S = 1 2 x,s Ψ + x,s σ ss ′ Ψ x,s ′ . Another less obvious SU (2) n symmetry is generated by N with We have systematically investigated the space of SU (2) s ⊗ SU (2) n nearest neighbor interaction Hamiltonians for which an efficient meron-cluster algorithm can be constructed. One example of such a Hamiltonian is In particular, an additional antiferromagnetic coupling J S x · S x+î arises, which is constrained by J ≥ 2t. Furthermore, t ′ = t, U ≥ J and U ≥ 8V . Indeed the above system can be simulated reliably with a very efficient meroncluster algorithm. Figure 7 shows the density of charge carriers away from half-filling as a function of the chemical potential for various temperatures. At µ ≈ 0.45 there is a strong first order phase transition at which the system undergoes phase separation. So far we have not found hightemperature superconductivity. This result may be a consequence of the additional antiferromagnetic coupling. However, it could also indicate that even the original Hubbard model does not display high-temperature superconductivity. Another severe sign problem arises in simulations of field theories at non-zero chemical potential. Obviously, understanding QCD at nonzero baryon density is of great experimental and theoretical importance. Here we study a simpler toy model for QCD -the 2-d O(3) model. Like QCD, this model is asymptotically free and has a non-perturbatively generated mass gap, instantons and θ vacua. In addition, it also suffers from a very severe sign problem when coupled to a chemical potential. As already discussed in section 4, the action of the 2-d O(3) model with chemical potential µ takes the form Note that in this case the chemical potential is a vector because it couples to a non-Abelian conserved charge.
for quantum antiferromagnets in a magnetic field. The resulting particle density as a function of the chemical potential is shown in figure 8. The Monte Carlo results show the expected onset behavior when the chemical potential exceeds the mass gap m = 1/ξ. In the zero temperature limit no particles would be produced for µ < m. At finite temperatures, on the other hand, a small particle density which can be computed analytically exists in this region. As shown in figure  8, the Monte Carlo data are consistent with this analytic prediction. For larger values of µ finite temperature effects are small and one can compare with the thermodynamic Bethe ansatz solution of the 2-d O(3) model, which again is consistent with the numerical data. The steps taken here for the 2-d O(3) model can potentially all be generalized to QCD. In the Dtheory formulation, QCD is described as a quantum link model [14], and a chemical potential can be included exactly as in eq.(41). The quarks in quantum link QCD appear as domain wall fermions. Hence, to simulate QCD with chemical potential along these lines, one must first construct a meron-cluster algorithm for domain wall fermions.

Domain Wall Fermions 5
For simplicity, let us consider the Hamiltonian of free (2 + 1)-d domain wall fermions, which describes 2-d chiral fermions bound to the walls Here Ψ † x and Ψ x are quark creation and annihilation operators obeying canonical anticommutation relations. Following [17], the partition function is written as where |0 is a particular fermion Fock state. Taking the expectation value in that state implies that there are no left-handed quarks at x 3 = 0, and no right-handed quarks at x 3 = β.
Like for the Hubbard model, we have thus far not found an efficient meron-cluster algorithm for the original domain wall fermion Hamiltonian. Instead, we ask for which Hamiltonians an efficient algorithm can be constructed. In order to stay in the same universality class, we demand that these Hamiltonians have the same symmetry properties as the original domain wall fermion Hamiltonian. The relevant symmetries are charge conjugation C, parity P, and lattice rotations R by 90 degrees. As in the staggered fermion case of section 3, we decompose the Hamiltonian as H = x,i h x,i and we consider the transfer matrix T i = exp(−ǫh x,i ). In the Hilbert space, the symmetries C, P and R are represented by unitary transformations U C , U P and U R . The symmetry requirements on the (2 + 1)-dimensional transfer matrix thus take the form In order to stay in the right universality class, it is equally important not to have any additional symmetries that are broken in the original domain wall fermion Hamiltonian. This is particularly important for removing doubler fermions.
Like for the Hubbard model, we have systematically investigated all symmetry requirements, and we have identified the most general nearest neighbor interaction Hamiltonian for which an efficient meron-cluster algorithm can be constructed. Compared to previous cases an additional complication arises. The γ-matrices give rise to contributions ±i to the total Boltzmann weight. Hence, the flip of a general cluster may not only change the sign -it may change the complex phase of the Boltzmann weight by a factor i. Consequently, besides the sign-changing meron-clusters there are i-on clusters whose flip changes the phase of the Boltzmann weight by a factor i. At present, we have not fully explored the space of efficient cluster algorithms for domain wall fermions. The necessary modifications of the standard Hamiltonian are similar to the ones required in the Hubbard model. It remains to be seen if chiral fermions bound to the walls appear in the modified models that can be simulated with efficient meron-cluster algorithms.

Conclusion
In conclusion, the meron concept provides us with a powerful algorithmic tool -the meroncluster algorithm -which can lead to a complete solution of severe sign problems. Here we have demonstrated that this algorithm allows us to simulate staggered fermions with an unusually small number of flavors, certain strongly correlated electron systems, quantum antiferromagnets in a magnetic field, as well as the O(3) model at non-zero chemical potential. The next challenge is to construct meron-cluster algorithms for QCD at non-zero baryon density and for systems that show high-temperature superconductivity.