Semigroup Approach to the Sign Problem in Quantum Monte Carlo Simulations
Zhong-Chao Wei
cond-mat.str-el hep-lat math-ph math.MP nucl-th







zcwei@thp.uni-koeln.de



Institute for Theoretical Physics, Department of Physics

University of Cologne, Cologne 50937, Germany




We propose a new framework based on the concept of semigroup to understand
the fermion sign problem. By using properties of contraction semigroups,
we obtain new sufficient conditions for quantum lattice fermion models
to be sign-problem-free. Many previous results can be considered as
special cases of our new results. As a direct application of our new
results, we construct a new class of sign-problem-free fermion lattice
models, which cannot be understood by previous frameworks. This framework
also provides an interesting aspect in understanding related quantum
many-body systems. We establish a series of inequalities for all the
sign-problem-free fermion lattice models that satisfy our sufficient
conditions.


02.70.Ss, 71.10.Fd, 71.27.+a




Semigroup Approach to the Sign Problem in Quantum Monte Carlo Simulations
    Zhong-Chao Wei
    December 30, 2023
=========================================================================





§ INTRODUCTION


Understanding interacting many-body systems remains a great challenge
in current physics research. The quantum Monte Carlo (QMC) method
is an important numerical method for this purpose<cit.>.
It contains a class of stochastic algorithms based on sampling over
different configurations according to some sampling weights derived
from the model. However, for many quantum models it is often extremely
difficult to express the quantum partition function or expectation
values of physical variables in terms of efficiently computable, non-negative
real sampling weights. This obstacle, which often hampers the efficiency
of QMC simulations seriously, is called the sign problem. It prevents
us from getting numerical results for large systems, at low temperature
effectively.

Specifically speaking, for auxiliary field quantum Monte Carlo(AFQMC)
type algorithms<cit.>
that are frequently used in condensed matter physics, nuclear physics
and cold atoms, for each configuration of auxiliary fields the contribution
to the partition function can be expressed by the determinant resulting
from the fermionic Gaussian integral, which can be computed efficiently.
Unfortunately, in general a fermionic Gaussian integral is not necessarily
a real number, even less a non-negative real number. For fermion lattice
models, the sign problem will lead to an exponential growth of total
computational cost as the volume of the system and the inversed temperature
get larger<cit.>, if one wants
to retain the same numerical accuracy.

Despite the fact that a general unbiased solution to the sign problem
is either non-existent or elusive by its very nature<cit.>,
a lot of physically interesting models have been shown to be sign-problem-free,
which is of great significance to practical numerical studies. For
AFQMC and some related methods, a few general frameworks have been
proposed to understand sign-problem-free interacting fermion systems.
There have been approaches based on the Kramers time-reversal invariance<cit.>,
the fermion bag<cit.>,
the Majorana quantum Monte Carlo<cit.>, the split
orthogonal group<cit.>, the Majorana reflection
positivity<cit.>, and the Majorana-time-reversal
symmetries<cit.>. Each approach has
unified a class of sign-problem-free fermion models and brought new
examples of sign-problem-free QMC simulations.

In this work, we propose an essentially new approach to construct
fermion models without sign problem. We observe that semigroup structures
arise naturally from imaginary-time evolutions, which is made explicit
after introducing auxiliary fields. The semigroup is generated by
multiplication of exponentials of fermionic quadratic operators. It
is not necessarily a group, for the inverse elements of those exponentials
may not appear in the calculation. An important particular case is
when each element of the semigroup has non-negative trace, the QMC
sampling weights are exactly the traces. This fact serves as the stating
point of our approach.

A semigroup is a set with element multiplication that satisfies the
associative law. Compared with the concept of group, an inverse does
not necessarily exist for each element in a semigroup. Semigroups
appear frequently in different areas of theoretical research. Every
group is also a semigroup. In quantum mechanics, the quantum dynamical
semigroup<cit.> is employed to study the time
evolution of open quantum systems, where the concept of semigroup
reflects the irreversiblility of time for the concerned physical processes.
In quantum field theory and statistical physics, the renormalization
group(RG)<cit.> is actually more like
a semigroup than a group, due to the loss of information during RG
transformations.

In this work, we are mainly concerned with a special kind of Lie semigroups
called the contraction semigroups. We construct two kinds of contraction
semigroups. When the parameter region is contained in such semigroups,
the fermionic Gaussian integral is always non-negative real. As a
result, the related AFQMC calculations do not have any sign problem.

The currently existing approaches mentioned above appear different
and unrelated at first glance, but now they can be unified in this
new framework. The Kramers time-reversal invariance leads to Kramers
pairs of eigenvalues of matrices, which results in the non-negativity
of fermion determiants<cit.>. In Ref. <cit.>,
the relation between the split orthogonal group and sign-problem-free
models has been revealed using some inequality for group elements.
Those results have been extended by recent studies<cit.>.
We show that all those approaches based on consideration of symmetries
are related to subgroups of the semigroups considered here. We also
explain that in the context of the AFQMC sign problem, the condition
of Majorana reflection positivity<cit.> is actually
equivalent to one of the two kinds of contraction semigroups treated
in this work. In short, to our best knowledge, all the known results
for fermion lattice models can be understood in our framework.

Our results open up new possibilities to sign-problem-free Monte Carlo
simulations. As an example, we construct a kind of interacting fermion
lattice model which involves the paring term, the Kramers time-reversal
invariant hopping term, and the interaction term. This class of model
is sign-problem-free, which could not find explanation in previous
frameworks.

We believe that this framework will find more applications in both
numerical and analytical studies. To illustrate the latter case, we
establish certain inequalities for the expectation values of physical
observables in many-body systems.




§ PROBLEM SETTING


In AFQMC algorithms for interacting fermion lattice models, interaction
terms are decoupled by auxiliary fields into fermionic quadratic forms<cit.>.
After integrating out the fermion degrees of freedom, one will obtain
an action in terms of auxiliary fields. One can treat this action
with random sampling numerically. The sampling weight for each configuration
of auxiliary fields usually has the form<cit.>

    p=        tr(e^h_1e^h_2⋯ e^h_k)
    
    =        (I+e^A_1e^A_2⋯ e^A_k)^1/2.



The expression of sampling weight in Eq. (<ref>) is the
main object of study in this work. Here h_i=γ^TA_iγ/4
(i=1,…,k) denote a set of fermionic quadratic forms. They come
from both single-body terms and auxiliary field decoupling of interaction
terms, and depend on the configuration of auxiliary fields. γ_n
(n=1,…,2N) are Majorana fermion operators, which satisfy anticommutation
relations {γ_l, γ_m} =2δ_lm.
The Majorana fermion basis is used for convenience, it is (unitary)
equivalent to the complex fermion basis with N species. Unless
we specify a particular example, in principle h_i could contain
an arbitrary particle number conserving part and an arbitrary pairing
part. That is to say the coefficients A_i=-A_i^T could be
arbitrary skew-symmetric complex matrices.

If we do not put any restrictions on h_i, the fermionic Gaussian
integral p could be non-positive, due to both the complex nature
of the coefficients and the two-valuedness of the spin representation.
Under those circumstances statistical sampling methods may fail to
obtain desired physical quantities with useful accuracy at reasonable
cost. This is the so-called sign problem in AFQMC methods.

In practical calculations, the possible forms of e^h_i are
given by the quantum partition function. They could come from both
the single-body term in the Trotter-Suzuki decomposition and the Hubbard-Stratonovich(HS)
transformations for interaction terms. Their inverse elements e^-h_i,
however, are not necessarily involved in any fermionic Gaussian integrals[The single-body term in the Hamiltonian could be a typical example.].
By taking products along the imaginary-time axis, they form a semigroup,
with elements representing different sorts of paths of the partition
function. This observation allows us to study the sign problem in
terms of semigroup.

Furthermore, if a Lie semigroup S⊂ Spin(2N,ℂ)
has property p≥0 for all its elements, then it corresponds to
a class of sign-problem-free fermion models. In the following sections,
we show that two specific kinds of Lie semigroups indeed possess this
good property.




§ DEFINITIONS AND USEFUL FACTS


We list some basic definitions and facts before going into details.
For general mathematical accounts of Lie semigroups, the reader may
refer to Refs. <cit.>.

For any square complex matrix X, consider an anti-linear symmetry
operation X↦η X^†η given by a Hermitian matrix
η=η^† with η^2=I, together with Hermitian
conjugation. We say that the matrix is η-Hermitian or η-anti-Hermitian
respectively, if it is invariant or changes sign under this transformation.
All the square complex matrices X with property η X+X^†η≤0
generate a Lie semigroup by taking exponentials and element products.
Semigroups of this kind are called contraction semigroups. Equivalently,
one can say that the contraction semigroup consists of all the square
matrices g that satisfy g^†η g-η≤0. They contract
the “length” of any vector given by the metric η. Similarly,
one can define the expansion semigroup by changing the direction of
the inequlity. We will work on the contraction semigroup and leave
the expansion case to the reader.

Obviously, the contraction semigroup defined above has the η-unitary
group as its maximal subgroup, which is generated by η-anti-Hermitian
matrices. Each element g in the contraction semigroup possesses
a polar decomposition g=g_Uexp(X_0), where X_0
is η-Hermitian and η X_0≤0, and g_U belongs
to the η-unitary group, i.e., g_U^†η g_U=η.
The set of X_0 forms a invariant cone, under adjoint action of
the η-unitary group.

Specially, let us consider strict contraction elements, which remain
strict contractions when multiplied by any semigroup elements. In
strict contraction case g^†η g-η<0, which implies
that η X_0<0 and g cannot have eigenvalues of magnitude
1.




§ SIGN-PROBLEM-FREE SEMIGROUPS


Let us give the outline of the discussions in this section. Firstly
we restrict the range of parameters by an anti-linear symmetry to
make the sampling weight p real. Then we observe that p never
vanishes for strict contraction elements inside some contraction semigroups,
while the non-strict contraction elements can be viewed as some limit
of strict contraction elements. These two conditions together ensure
that p is non-negative as a continuous function of the coefficients.

Each condition requires a definition of anti-linear involution for
complex skew-symmetric matrices. Consider any complex skew-symmetric
matrix A. Adopting the Majorana fermion basis, it is natural to
assume that those two operations are expressed by real orthogonal
transformations acting on A, J_1 and J_2 respectively,
along with the complex conjugation.

Firstly, we assume the complex skew-symmetric matrices are fixed under
the operation A↦ J_1^TA̅J_1. Here J_1 could
be either symmetric J_1^2=I_2N, or skew-symmetric J_1^2=-I_2N.
It is easy to see that p is real under this assumption.

Secondly, to define a contraction semigroup, J_2 should be chosen
to be either symmetric or skew-symmetric, so that J_2 or iJ_2
can serve as the aforementioned indefinite metric η. The coefficient
matrices that are not changed under the transformation A↦ J_2^TA̅J_2
generate the maximal subgroup of the contraction semigroup. Meanwhile,
elements in the invariant cone change sign under this operation, iJ_2A=-iA̅J_2≤0.
Since A is skew-symmetric, if J_2 were symmetric, the invariant
cone would be trivial, i.e., it contains only zero element. Therefore
we have to assume J_2 to be skew-symmetric. According to Eq. (<ref>),
p is nonzero for any such defined strict contraction element, because
the matrix inside the determinant does not have zero eigenvalues.

Finally, we have to check the consistency of the two conditions. The
resulting invariant cone should statify both constraints given by
J_1 and J_2. However, in order to make our argument stand,
we have to ensure that the resulting invariant cone always contains
strict contraction elements. This cannot be achieved by an arbitrary
choice of J_1 and J_2[For example, the cone is trivial when [J_1, J_2]=0. ].
Under the current assumption, the only possibility is that J_1
and J_2 satisfy the anticommutation relation { J_1, J_2} =0.
See Supplemental Material[[URL will be inserted by publisher]]
for more detailed arguments. 

Now we have two sign-problem-free semigroups on which p≥0, and
they are defined by

    J_1^TAJ_1    =    A̅,
    
    i(J_2A-A̅J_2)    ≤    0.

J_1 and J_2 are two anti-commuting, real orthogonal matrices.
While J_1 could be symmetric or skew-symmetric, J_2 should
be skew-symmetric. If all A_i matrices in Eq. (<ref>)
satisfy the conditions above, the corresponding quantum Monte Carlo
simulations will be sign-problem-free.

Throughout the above discussions we do not require the Hermitian condition
of Majorana fermion operators γ_n=γ_n^†.
Instead, the anticommutation relations for Majorana fermion operators
are preserved under complex orthogonal transformations of Majorana
fermion operators. So the condition for positive trace given above
also holds for this complex orthogonal generalization of the Majorana
fermion basis.




§ APPLICATIONS


Eq. (<ref>) and Eq. (<ref>)
consititute the main result of this work. They cover all the results
on sign-problem-free QMC simulations of fermion lattice models known
to us.

Firstly, when the inequality in Eq. (<ref>)
becomes equality, we will have two anti-linear symmetries J_1^TAJ_1=J_2^TAJ_2=A̅.
Under this circumstance our result goes back to the known results
based on symmetry considerations<cit.>.
In this case parameters actually live in the maximal subgroup of the
semigroup. Many models in practical studies fall into this case, which
can be simulated by quantum Monte Carlo without sign problem<cit.>.
Below we list a few important examples.

(a)The negative-U Hubbard models, the positive-U Hubbard models
at half-filling on bipartite lattices<cit.>, and
the Kane-Mele-Hubbard model<cit.>
at half-filling can all be regarded as good examples of this case.
For those models J_1 could either be symmetric or skew-symmetric,
depending on different choices of the Majorana fermion basis.

(b)A class of interacting spinless fermion models on bipartite lattices
at half-filling have been shown to be sign-problem-free using the
fermion bag approach<cit.> for continuous-time
quantum Monte Carlo(CTQMC) method<cit.>. They
have also been treated without sign problem using AFQMC under the
Majorana fermion basis<cit.>, and using CTQMC under
the framework of the split orthogonal group<cit.>.
Actually our result applies to several different kinds of QMC methods
despite their differences in practice. That class of spinless fermion
models are typical examples of the case with symmetric J_1. Another
example is a model for helical topological superconductors with interactions<cit.>.

(c)For the case with skew-symmetric J_1, the related fermion
lattice models have Kramers time-reversal invariance <cit.>.
Applications can also be found in high-spin interacting fermion systems,
e.g. the nuclear shell model<cit.> and the high-spin
Hubbard model<cit.>. This sign-problem-free
property of Kramers time-reversal invariant models also has applications
in the research of high-temperature superconductors<cit.>.

Secondly, when J_1 is symmetric, the parameter region given by
Eq. (<ref>) and Eq. (<ref>)
coincides with the result obtained from Majorana reflection positivity.
To see this clearly, one may choose a Majorana fermion basis such
that J_1=σ_1⊗ I_N, J_2=iσ_2⊗ I_N.
The fermion degrees of freedom are grouped into two parts under this
new basis γ=([ γ^(1); γ^(2) ]), while the condition of reflection symmetry is given by Eq. (<ref>),
and the condition of positivity is ensured by Eq. (<ref>).
We have γ^TAγ=γ^(1)TBγ^(1)+γ^(2)TB̅γ^(2)+2iγ^(1)TCγ^(2),
with block matrices B and C. C is positive semidefinite Hermitian
matrix. This can be immediately compared to the related definitions
in Ref. <cit.>. All the models studied by the
fermion bag approach and the split orthogonal group approach can also
be treated by Majorana reflection positivity. 

The set of operators with Majorana reflection positivity is closed
under multiplication<cit.>,
which accounts the semigroup property. Each strict contraction element
corresponds to a strictly positive operator in the sense of Majorana
reflection positivity. We mention that this strict reflection positivity
can also be used to show the uniqueness of the ground state for finite
systems<cit.>.

Thirdly, when J_1 is skew-symmetric, the result above implies
new sign-problem-free models. For convenience in practical applications,
we reexpress our result for this J_1 skew-symmetric case in terms
of the complex fermion basis. Without losing generality, we can choose
a Majorana fermion basis γ=([ γ^(1); γ^(2); γ^(3); γ^(4) ]) so that the two skew-symmetric orthogonal matrices have the form
J_1=σ_x⊗ iσ_y⊗ I_N/2, J_2=-iσ_y⊗ I_2⊗ I_N/2.
Then we define the complex fermion basis as c_l=(γ_l^(1)+iγ_l^(2))/2,
d_l=(γ_l^(4)+iγ_l^(3))/2,
here l=1,…,N/2 labels different components. There is a one-to-one
correspondence between the coefficient matrices A which satisfy
the conditions in Eq. (<ref>), and the fermionic
quadratic forms with Kramers time-reversal invariance,


    h     =    1/4γ^TAγ=h^(0)+h^(p),
    
    h^(0)    =    (c^†, d^†)M([ c; d ])-(c, d)M^T([ c^†; d^† ]),
    
    h^(p)    =    (c, d)RK([ c; d ])-(c^†, d^†)SK([ c^†; d^† ]).

 M, R, and S are complex coefficient matrices, and K=iσ_y⊗ I_N/2.
RK and SK are skew-symmetric, in accordance with the fermion
anticommutation relations. The time reversal operation is given by
the unitary transformation K followed by a complex conjugation
of the coefficients under complex fermion basis. It is not difficult
to check that K^TMK=M̅, K^TRK=R̅, K^TSK=S̅.
Then the condition in Eq. (<ref>) is now
converted to two inequalities for Hermitian matrices R and S,
R≥0, S≥0 under this complex fermion basis. The particle
number conserving part h^(0) corresponds to the maximal
subgroup of the contraction semigroup, while the pairing term h^(p)
corresponds to the invariant cone.

Consider a Kramers time-reversal invariant effective band Hamiltonian
defined on an arbitrary lattice, with time-reversal symmetry that
satisfies K^2=-I. We add an attractive on-site Hubbard-U term
to the Hamiltonian. With appropriate HS transformations to decouple
the interaction term[To treat some interaction terms like Hubbard-U term, it might be
useful to notice that (1-2n)=exp(iπ n) for any fermion
number operator n with eigenvalues 0 and 1. That kind of
interaction term can be expressed by exponential of quadratic forms. ], sign-problem-free AFQMC simulations can be carried out for this
type of models<cit.>. Now we can extend this
model by adding a new pairing term that satisfies the sign-problem-free
conditions to study the proximity effect of superconductivity to topological
matters with correlation effects. Actually, by particle-hole transformation
one can also map an attractive interaction term to a repulsive one,
or a pairing term to a hopping term to study more physical problems
in strongly correlated electron systems. Those possibilities have
not been shown by any previous research.

We note that for some models both cases, symmetric and skew-symmetric
J_1, are suitable, depending on the choice of Majorana basis.
Those models correspond to the intersection of the two semigroups.
A generalized Kane-Mele-Hubbard model on a bipartite lattice with
staggered magnetic field, considered in Ref. <cit.>,
can be seen as an example.

For many models the system contains several different kinds of degrees
of freedom. Suppose each subsystem satisfies sign-problem-free condition,
e.g., with its own choice of matrices J_1 and J_2. If the
coupling terms between the two sign-problem-free subsystems are carefully
selected, the whole system can still be sign-problem-free. In that
case, our sign-problem-free conditions are to be applied to each building
block of the whole system. This observation can be useful in the study
of multilayer systems.

For sign-problem-free models studied in this work, the partition function
can be seen as a summation of contraction semigroup elements. This
structure can have interesting consequences, including the sign structure
of expectation values of observables. For example, for any positive
integer m, we have 

    tr(h'_1g_1h'_2g_2… h'_mg_m)≥0,

where the coefficient matrices of fermionic quadratic operators h'_s
belong to the invariant cone and g_s can take any elements of
the semigroup, s=1,…,m. The proof is straightforward for the
case with symmetric J_1 owing to Majorana reflection positivity.
A proof for the case with skew-symmetric J_1 using Wick's theorem
and the Kramers degeneracy theorem can be found in Supplemental Material.
This set of inequalities also provide an alternative route to the
sign-problem-free property.




§ CONCLUSION AND DISCUSSION


In this work we have presented sufficient conditions for sign-problem-free
QMC simulations of fermion lattice models. A new framework based on
the concept of semigroup has been proposed to understand this problem
in a systematic way. New sufficient conditions have been obtained,
as stated in Eq. (<ref>) and Eq. (<ref>).
All previous results based on symmetry considerations and Majorana
reflection positivity can be understood well and unified naturally
within our new approach. New sign-problem-free models have been constructed
to show the power of our method. Such sign-problem-free interacting
fermion models share some general physical properties, as we have
demonstrated.

Although we have focused on applications in quantum lattice models
in condensed matter physics, our framework is not limited to those
cases and can also help with the sign problems in the other branches
of physics<cit.>.

We would like to mention that the techniques used in this work can
be extended to systems with bosonic degrees of freedom.

The author would like to thank Alexander Alldridge, Lei Wang and Martin
Zirnbauer for illuminating discussions, with special thanks to Alexander
Alldridge for introducing knowledge of Lie semigroups, and Martin
Zirnbauer for the help during the revision process. We acknowledge
the financial support of the German Science Foundation under CRC TR
183.


apsrev4-1







§ SUPPLEMENTAL MATERIAL





§ PROOF OF THE SKEW-SYMMETRY PROPERTY OF J_2


If J_2 were symmetric, for any element A in the invariant
cone with metric J_2, let A^'=(A+A̅)/2.
From J_2^TAJ_2=-A̅ we know that { J_2, A^'} =0.
Then we would have

    tr(J_2A)=tr(J_2A')=-tr(A'J_2)=0.

That is to say the only possible element in the invariant cone would
be zero matrix, which does not suit our purpose. So J_2 can only
be skew-symmetric.




§ PROOF OF THE ANTICOMMUTATION RELATION BETWEEN J_1 AND J_2


Let A be any strict contractive element in the invariant cone with
metric iJ_2, and A^'=i(A-A̅)/2. In
this case [J_2, A^']=0, and the real symmetric
matrix Q=J_2A^' is positive definite. We also have { J_1, A^'}=0,
because J_1^TAJ_1=A̅.

Now consider the real skew-symmetric matrix

    X=-J_1A^'=J_1J_2Q=-QJ_2J_1.

X has real orthogonal matrix J_1J_2 and positive real symmetric
matrix Q as its unique polar decomposition, which implies that
[J_1J_2, Q]=0. Hence { J_1, J_2}=0.




§ PROOF OF A SERIES OF TRACE INEQUALITES


Now we prove the inequality in Eq. (<ref>) of
the main text for the case with skew-symmetric J_1. To this purpose,
we show an equivalent result that any trace with the form


    W=(-1)^rtr[f_4rf_2r-1… f_2f_1exp(h)]

is non-negative for any non-negative integer r, where h can
take any particle number conserving fermionic quadratic forms with
Kramers time-reversal invariance. f_2s-1 (s=1,…,2r) can
take any fermion annihilation or creation operators(which we do not
require to form an orthogonal basis), while f_2s are their images
under the time-reversal operation respectively. 

Let Z=tr[exp(h)]≥0 and assume
Z≠0 so that the Green's function G can be defined by

    G_ij=-1/Ztr{[θ(i-j)f_if_j-θ(j-i)f_jf_i]exp(h)}

with i, j=1,…,4r, and θ is the unit step function.
Only the contractions between anihilation and creation operators lead
to non-zero elements of G. In the non-trivial case there are 2r
creation operators and 2r annihilation operators in total. Therefore
one can select an appropriate permuation matrix P such that

    G=P^T([    0    M; -M^T    0 ])P

with P=1, meanwhile the Kramers time-reversal symmetry leads
to the relation 

    J_M^TMJ_M=M̅,

where J_M is a skew-symmetric real orthogonal matrix. So all
the eigenvalues of M occur in complex conjugate pairs even when
they are real numbers, which is ensured by the Kramers degeneracy
theorem.

By Wick's theorem we have the Pfaffian expression for the the expectation

    W=(-1)^rpf(G)Z=(M)Z,

which is clearly non-negative.
