# Perturbative Removal of a Sign Problem

Scott Lawrence<EMAIL_ADDRESS>Department of Physics,
University of Colorado, Boulder, CO 80309, USA

###### Abstract

This paper presents a method for alleviating sign problems in lattice path
integrals, including those associated with finite fermion density in
relativistic systems. The method makes use of information gained from some
systematic expansion — such as perturbation theory — in order to accelerate
the Monte Carlo. The method is exact, in the sense that no approximation to
the lattice path integral is introduced. Thanks to the underlying systematic
expansion, the method is systematically improvable, so that an arbitrary
reduction in the sign problem can in principle be obtained. The Thirring model
(in $0+1$ and $1+1$ dimensions) is used to demonstrate the ability of this
method to reduce the finite-density sign problem.

##  I Introduction

Lattice Monte Carlo methods are able to provide nonperturbative access to
observables in quantum field theories. They are unique in this respect for
many strongly coupled theories. Under certain circumstances, such as at finite
density of relativistic fermions and the Hubbard model away from half-filling,
lattice methods are made dramatically less efficient by the so-called sign
problem. This sign problem is a central obstacle to first-principles
calculations in many regimes of strongly coupled theories, including _ab
initio_ studies of the nuclear equation of state.

In lattice field theory, spacetime is treated as discrete and observables are
obtained from the high-dimensional lattice path integral. Lattice field theory
is ordinarily used to study a system in thermal equilibrium, and the partition
function is written as $Z=\int\mathcal{\mathcal{missing}}DA\;e^{-S(\phi)}$,
where $S$ is the (Euclidean) action and the integral is taken over all
configurations of a field $A$. Observables are given by various derivatives of
the logarithm of the partition function. These derivatives are ordinarily
sampled by importance sampling, which hinges on the treatment of the
normalized Boltzmann factor $e^{-S}/Z$ as a probability distribution. For some
systems, including those with a finite density of relativistic fermions, the
action $S$ is complex, and this is not possible — this is the sign problem.

Importance sampling commonly takes a polynomial amount of time in the
spacetime volume being simulated (although this is proven only in a few cases
Jerrum and Sinclair (1993); Guo and Jerrum (2016); Collevecchio  _et al._
(2016)). Importance sampling can be modified to work even where $S$ is
complex, but at the cost of efficiency. In this modification, the “quenched”
Boltzmann factor $|e^{-S}|/Z$ is treated as a probability with respect to
which sampling is performed. Ordinary expectation values are obtained in terms
of quenched expectation values:
$\langle\mathcal{O}\rangle=\langle\mathcal{O}e^{-iS_{I}}\rangle_{Q}/\langle
e^{-iS_{I}}\rangle_{Q}$. The loss of efficiency comes primarily from the
denominator. The average of the exponential of the imaginary part of the
action, often termed the “average phase”, is equal to the ratio of the
physical to quenched partition functions $Z/Z_{Q}$, and characteristically
scales like $e^{-\beta V}$. Resolving this exponentially small quantity, by
averaging many quantities of unit magnitude, requires $\sim e^{2\beta V}$
samples; thus the reweighting procedure incurs an exponential cost in the
volume. This failure affects a wide variety of models, and a correspondingly
wide variety of methods have been proposed to mitigate it: complex Langevin
Aarts and Stamatescu (2008), the density of states method Langfeld and Lucini
(2016), canonical methods Alexandru  _et al._ (2005); de Forcrand and
Kratochvila (2006), reweighting methods Fodor and Katz (2002), series
expansions in the chemical potential Allton  _et al._ (2002), fermion bags
Chandrasekharan (2013), field complexification Alexandru  _et al._ (2020), and
analytic continuation from imaginary chemical potentials de Forcrand and
Philipsen (2007).

In this paper we will examine a new method, inspired by two observations:
first, that the partition function is unchanged if a function that integrates
to zero is added to the Boltzmann factor, and second, that lattice methods can
encounter a fatal sign problem even in regimes under good control by
perturbation theory (or any other systematic expansion). To any fixed order in
perturbation theory, the sign problem can be (non-uniquely) identified with
some oscillating part of the Bolzmann factor which integrates to zero, and
this part can then be subtracted off, without changing the partition function
or any observables. In fact, we will see that this subtraction can be
performed in such a way that even the nonperturbative partition function and
observables remain unchanged. Where the model is under good control by
perturbation theory, meaning that the partition function is well-approximated
by the integral of a perturbative expansion of the integrand, this subtraction
is nearly the entire sign problem. In regimes where perturbation theory is a
poor approximation, we may hope to isolate and remove a single component of
the sign problem, thereby improving the efficiency of the necessary
nonperturbative calculation.

The method described in this paper exhibits two favorable characteristics
worth noting before we begin. Firstly, it is an _exact_ method, in the sense
that the modified form of the partition function is precisely equal to the
original, physical form. As a consequence, all observables retain their
physical values, and the only errors are statistical ones associated to the
sampling process. This is true regardless of the quality of the systematic
expansion used: the removal of the sign problem is approximate, but the
observables computed are exact. Secondly, although the removal of the sign
problem is approximate, it is _systematically improvable_. If a certain order
in perturbation theory does not yield a sufficiently moderate sign problem, a
higher order can in principle be used. As long as the expansion converges (on
the lattice), a sufficiently high order is guaranteed to remove the sign
problem to any desired degree. Of course, an exponential cost is associated
with going to higher orders in most expansions, and it is to be expected that
this property of systematic improvability is not a practical way to solve many
problems, as it merely trades one exponential cost for another. Nevertheless,
this is an unusual and promising combination.

This paper uses the Thirring model Thirring (1958) in $0+1$ and $1+1$
dimensions as a testbed for the method of subtractions. This model has
frequently been used, in varying dimensions, to test methods for treating the
fermion sign problem in the past, including complexification Alexandru  _et
al._ (2017, 2016a) and complex Langevin Pawlowski and Zielinski (2013).

In the next section, the general method of subtractions is described in
detail, with an emphasis on subtractions that are constructed via some
systematic expansion. In Sec. III, the heavy-dense limit is used to construct
a subtraction for the Thirring model in $0+1$ dimensions. This is extended in
Sec. IV, where the $1+1$-dimensional Thirring model is treated with a variety
of expansions. A nonperturbative method of optimizing subtractions is
described in Sec. V. Finally we conclude in Sec. VI, discussing in particular
a relation between this method and the method of field complexification.

##  II General Method

For brevity, let us write the Boltzmann factor as $f(A)\equiv e^{-S(A)}$, so
that the unmodified form of the partition function is
$Z=\int\mathcal{D}A\;f(A)$. If we let $g(A)$ be some function which integrates
to $0$ (e.g. a total derivative of a function with appropriate behavior on the
boundary of configuration space), then the numerical value of the partition
function is unmodified by the subtraction of $g(A)$ from the Boltzmann factor:

$Z=\int\mathcal{D}A\;f(A)=\int\mathcal{D}A\;f(A)-g(A)\text{.}$ (1)

The quenched partition function, and therefore the average phase
$\langle\sigma\rangle\equiv Z/Z_{Q}$, is generically changed by this
operation. Therefore, a suitable $g(A)$ may improve the sign problem. In fact,
a subtraction always exists which removes the sign problem entirely:

$g_{\mathrm{ideal}}(A)=f(A)-\frac{\int\mathcal{D}A^{\prime}\;f(A^{\prime})}{\int\mathcal{D}A^{\prime}}\text{.}$
(2)

This particular subtraction is unusable in practice, as computing it requires
exact knowledge of the partition function. Indeed, using this subtraction is
equivalent to performing the entire computation analytically.

Particularly in the case where $g$ is constructed from a perturbative
expansion (described below) this method can be thought of as splitting the
path integrand into a few terms, and integrating some analytically. In the
case of the ideal subtraction of Eq. (2), the entire path integral is
performed analytically.

Once a subtraction is selected, it remains to compute an observable. We must
express $\langle\mathcal{O}\rangle$ (an expectation value over $f$) as an
expectation value taken over the distribution $f-g$. It is tempting to write

$\langle\mathcal{O}\rangle=\frac{\int\mathcal{D}A\;(f(A)-g(A))\frac{\mathcal{O}(A)f(A)}{f(A)-g(A)}}{\int\mathcal{D}A\;f(A)-g(A)}\text{.}$
(3)

This equation is correct, but not useful for computing the expectation value,
as the measurement of the modified observable encounters a signal-to-noise
problem comparable to the original sign problem. This is particularly clear in
the case of $\mathcal{O}=1$, where the numerator is equal to
$\int\mathcal{D}A\;f(A)$, the highly oscillatory integral we wanted to avoid
in the first place.

Consider a conjugate variable $\xi$ to $\mathcal{O}$, such that
$\langle\mathcal{O}\rangle=\frac{\partial}{\partial\xi}\log Z$. The previous
approach corresponds to treating $g$ as constant in $\xi$. Instead, take $g$
to vary with $\xi$, in such a way that $\int g=0$ for any value of $\xi$. The
desired expectation value is now

$\langle\mathcal{O}\rangle=\frac{\int\mathcal{D}A\;\mathcal{O}(A)f(A)-\frac{\partial}{\partial\xi}g(A)}{\int\mathcal{D}A\;f(A)-g(A)}\text{,}$
(4)

which does not necessarily (and does not in practice, as we will see) suffer
from the same magnitude of signal-to-noise problem.

We now discuss how to construct a suitable subtraction $g(A)$ in a systematic
manner. One strategy is to attempt to approximate Eq. (2) as closely as
possible, with an analytic expansion. For the purposes of removing the sign
problem, however, it is sufficient to replace $f(\cdot)$ in Eq. (2) by just
the part of the Boltzmann factor that oscillates. Removing the oscillations
will cure the sign problem, even if the rest of the partition function is not
approximated well at all.

To make this concrete, suppose a perturbative expansion of $f(A)$

$f(A)=f_{0}(A)+\lambda f_{1}(A)+\frac{\lambda^{2}}{2}f_{2}(A)+\cdots$ (5)

is available, such that the partition functions at low order are readily
(perhaps analytically) obtained. Defining $Z_{n}=\int\mathcal{D}A\;f_{n}(A)$,
we can construct a wide variety of functions which integrate to $0$ and
approximate various parts of the original Boltzmann factor. It is often
convenient to pick (some linear combination of)

$g_{n}(A)=f_{n}(A)-\frac{f_{0}(A)}{Z_{0}}Z_{n}\text{.}$ (6)

The factor of the free theory Boltzmann factor is somewhat arbitrary — any
function of $A$ with unit integral will do.

This procedure does not depend on the precise nature of the systematic
expansion. Our first application of this method (in Sec. III) will use the
heavy-dense limit to construct a subtraction, instead of an expansion around
free field theory.

Because the subtracton was constructed from a systematic expansion, $g_{n}$
naturally depends on $\xi$. Applying Eq. (4) to this construction, the
physical expectation value of $\mathcal{O}$ is given by

$\langle\mathcal{O}\rangle=\left\langle\frac{\mathcal{O}f-\frac{\partial}{\partial\xi}f_{n}+\frac{f_{0}}{Z_{0}}\frac{\partial}{\partial\xi}Z_{n}}{f-g_{n}}\right\rangle_{\\!f-g_{n}}\text{.}$
(7)

Note that it is not in general true that
$\frac{\partial}{\partial\xi}f_{n}=\mathcal{O}f_{n}$, nor is it generally true
that the same derivative of $\log Z_{n}$ yields a perturbative expectation
value.

In deriving this expression, we have chosen for convenience not to let
$f_{0}$, and therefore $Z_{0}$, vary with $\xi$. This, like the precise manner
of constructing the subtraction, is an arbitrary choice. We will not, in this
paper, explore the question of what the optimal construction of a modified
observable is.

Of course, even after the subtraction, a residual sign problem typically
remains, which is addressed by reweighting.

##  III Quantum Mechanics

In this section we demonstrate the method on a $0+1$-dimensional variant of
the Thirring model. Described in Alexandru  _et al._ (2016b, a), this model is
defined by the lattice action

$S=\frac{1}{2g^{2}}\sum_{t}\left(1-\cos A(t)\right)-\log\det K[A].$ (8)

The Dirac matrix $K[A]$ is given by

$K[A]_{tt^{\prime}}=\frac{1}{2}\big{[}e^{\mu+iA(t)}\delta_{(t+1)t^{\prime}}-e^{-\mu-
iA(t^{\prime})}\delta_{(t^{\prime}+1)t}-e^{\mu+iA(t)}\delta_{tN}\delta_{t^{\prime}1}+e^{-\mu-
iA(t^{\prime})}\delta_{t1}\delta_{t^{\prime}N}\big{]}+m\delta_{tt^{\prime}}\text{.}$
(9)

Above, $m$ is the bare mass and $g$ a coupling constant; we are implicitly
working in units where the lattice spacing is $1$, so that the number of sites
is equal to the inverse temperature $\beta$. The sign problem, created by the
chemical potential $\mu$, is portrayed in Fig. 1; the average phase decays
exponentially with the inverse temperature, and so the cost of calculations
increases exponentially with the same.

A suitable subtraction is provided by the heavy-dense limit of
$\mu\rightarrow\infty$. The Dirac matrix can be expanded via the polymer
representation Montvay and Münster (1997), and the dominant term of $\det K$
in the limit of large $\mu$ is

$\det K=e^{\beta\mu}(2^{-\beta}e^{i\sum_{t}A(t)}+O(e^{-\beta\mu}))\text{.}$
(10)

We will use the leading-order term as our subtraction:

$f_{1}(A)=e^{\frac{1}{2g^{2}}\sum_{t}\cos A(t)}\times
2^{-\beta}e^{\beta\mu+i\sum_{t}A(t)}\text{.}$ (11)

Integrating over all fields yields the leading-order partition function

$Z_{1}=e^{\beta\mu}\left[\pi
I_{1}\left(1/2g^{2}\right)\right]^{\beta}\text{.}$ (12)

(Here and throughout, $I_{\nu}(\cdot)$ denotes the modified Bessel function of
the first kind, of order $\nu$.)

For the scaling factor $f_{0}(A)/Z_{0}$ in Eq. (6) we could simply choose
$(2\pi)^{-\beta}$, but it is convenient in this case to use the bosonic part
of the Boltzmann factor:

$\frac{f_{0}(A)}{Z_{0}}=\frac{\exp\left(\frac{1}{2g^{2}}\sum_{t}(1-\cos
A(t))\right)}{\left[2\pi I_{0}(1/2g^{2})\right]^{\beta}}\text{.}$ (13)

The observable we will focus on is the number density, defined as $\langle
n\rangle=\beta^{-1}\frac{\partial}{\partial\mu}\log Z$. In order to measure
this observable with the subtraction method, we need the $\mu$-derivatives of
$f_{1}$ and $Z_{1}$ as per Eq. (7). Happily, in this case they are
particularly simple: $\frac{\partial}{\partial\mu}f_{1}=f_{1}$ and
$\frac{\partial}{\partial\mu}Z_{1}=Z_{1}$. This reflects the fact that, in the
heavy-dense limit, the density is $1$ regardless of temperature.

To summarize, before performing the subtraction, the partition function was
written $Z=\int e^{-S}$ with the action $S$ defined by Eq. (8). The modified
form of the partition function is

$Z=\int\mathcal{D}A\;\underbrace{\exp\left(\frac{1}{2g^{2}}\sum_{t}\left(1-\cos
A(t)\right)\right)}_{f_{0}}\bigg{[}\underbrace{\det
K}_{f/f_{0}}-\underbrace{2^{-\beta}e^{\beta\mu+i\sum_{t}A(t)}}_{f_{1}/f_{0}}+\underbrace{\frac{e^{\beta\mu}\left[\pi
I_{1}(1/2g^{2})\right]^{\beta}}{\left[2\pi
I_{0}(1/2g^{2})\right]^{\beta}}}_{Z_{1}/Z_{0}}\bigg{]}\text{,}$ (14)

where the scaling factor $f_{0}$ and its integral $Z_{0}$ are defined by Eq.
(13), and the subtraction is constructed from the heavy-dense term $f_{1}$ and
its integral $Z_{1}$, given in Eqs. (11) and (12).

While numerically identical, this form is hoped to have a reduced sign
problem. The density is given by the expectation value, taken in the
subtracted ensemble,

$\beta\langle n\rangle=\left<\frac{\operatorname{{Tr}}K^{-1}\frac{\partial
K}{\partial\mu}-f_{1}+f_{0}\frac{Z_{1}}{Z_{0}}}{f-f_{1}+f_{0}\frac{Z_{1}}{Z_{0}}}\right>_{\\!f-g}\text{.}$
(15)

Figure 1:  The subtraction method as applied to the $0+1$-dimensional Thirring
model. The leftmost plot shows the density as a functon of chemical potential
with $\beta=8$, $m=1$, and $g^{2}=0.2$. The exact result is from Pawlowski
_et al._ (2015). The center plot shows the average phase, again as a function
of $\mu$, for the same parameters. On the right is the average phase for
$\mu=1.8$ as a function of inverse temperature $\beta$.

The results of this procedure are shown in Fig. 1. Specially in $0+1$
dimensions, the sign problem is no longer exponential in the volume, but
rather improves slightly as $\beta$ is increased. This is not to be expected
to hold true for higher dimensional theories. In general, the exponential
difficulty of the sign problem will not be removed by the subtraction method,
but merely ameliorated. (In the case of the particular model at hand, it is
possible to construct a subtraction that entirely removes the sign problem,
but only because the entire partition function is analytically known.)

Lastly, note that all data points in Fig. 1 are constructed from $10^{3}$
samples. The data points calculated with the subtraction have much smaller
error bars (for $\mu=2.0$, the error bar width is $\sim 10^{-14}$) even than
the sign-free $\mu=0$ data point without the subtraction; this procedure has
improved the signal-to-noise ratio in addition to reducing the sign problem.
In the limit of the ideal subtraction of Eq. 2, there is no variance remaining
in the observable, and a single measurement yields the exact answer.

##  IV Field Theory

Figure 2: Simulation of the $1+1$-dimensional Thirring model on a $12\times 6$
lattice with $m=0.15$, $g^{2}=0.3$. The left plot shows the density as a
function of chemical potential, and on the right are the corresponding average
phases. Each data point is backed by $10^{4}$ samples.

We now move to the $1+1$-dimensional Thirring model with staggered fermions.
The lattice action of this model is Alexandru  _et al._ (2017)

$S=\sum_{x,\nu=0,1}\frac{2}{g^{2}}(1-\cos A_{\nu}(x))-\log\det K[A]$ (16)

with the Dirac matrix now defined by

$\displaystyle K[A]_{xy}=m\delta_{xy}+\frac{1}{2}\sum_{\nu=0,1}$
$\displaystyle\eta_{\nu}e^{iA_{\nu}(x)+\mu\delta_{\nu,0}}\delta_{x+\nu,y}$
(17) $\displaystyle-$
$\displaystyle\eta_{\nu}e^{-iA_{\nu}(y)-\mu\delta_{\nu,0}}\delta_{y+\nu,x}\text{,}$

where as before $m$ is the bare mass, $g$ the coupling, and $\mu$ the chemical
potential. The staggered fermions are defined by
$\eta_{0}=(-1)^{\delta_{0x_{0}}}$ and $\eta_{1}=(-1)^{x_{0}}$. As in the
$0+1$-dimensional model, a sign problem is created at $\mu\neq 0$.

The first subtraction procedes from the same heavy-dense limit we used for the
quantum mechanical model above. As before, we define
$f_{0}=e^{\frac{2}{g^{2}}\sum_{x,\nu}\cos A_{\nu}(x)}$. The leading-order term
in the heavy-dense expansion is

$f_{1}=e^{\frac{2}{g^{2}}\sum_{x,\nu}\cos A_{\nu}(x)}2^{-\beta L}e^{\beta
L\mu+i\sum_{x}A_{0}(x)}$ (18)

which, when integrated over all fields, yields the partial partition function

$Z_{1}=e^{\beta L\mu}2^{-\beta L}\left(2\pi
I_{0}(2/g^{2})I_{1}(2/{g^{2}})\right)^{\beta L}\text{.}$ (19)

At this order in the heavy-dense expansion, everything takes the form of $L$
copies of the quantum mechanical model above. In particular, the
$\mu$-derivatives of $f_{1}$ and $Z_{1}$ are $Lf_{1}$ and $LZ_{1}$,
respectively.

The results of simulating with the leading-order heavy-dense subtraction, on a
$12\times 6$ lattice, are shown in Fig. 2. Without the subtraction, the sign
problem falls to be indistinguishable from $0$ ($\lesssim 10^{-2}$) by
$\mu\approx 0.8$; after the subtraction, the sign problem is manageable from
$\mu=0$ through lattice saturation.

At the next order in the heavy-dense limit, the number of diagrams in the
polymer representation is exponential in $\beta$. Therefore, it is not
practical (barring another way of computing the NLO heavy-dense partition
function) to use this expansion at higher orders. Another expansion to
consider is the hopping expansion. However this expansion is also not
practical for the purpose of removing a sign problem, as the lowest-order term
in the hopping expansion that has a sign problem is at order $\kappa^{\beta}$.

At small $g$, the auxiliary field is pegged to $A\sim 0$ by the $\cos A$ term
in the action. As a result, it is possible to construct a “weak-coupling”
expansion for the lattice Thirring model described here by Taylor expanding
$\det K[A]$ in the fields $A$. The term first-order in $A$ makes a
particularly convenient subtraction: as it is odd in $A$, it integrates to
$0$, and the corresponding partial partition function $Z_{1}$ vanishes. The
subtracted integrand of the partition function is

$f-g=f_{0}\left[\det K-\det
K_{0}\operatorname{{Tr}}K_{0}^{-1}\left(\frac{\partial K}{\partial
A}\right)_{A=0}A\right]$ (20)

where $K_{0}$ is $K$ evaluated at $A=0$, and
$f_{0}=e^{\frac{2}{g^{2}}\sum_{x,\nu}\cos A_{\nu}(x)}$ as usual. Fig. 3 shows
the magnitude of the sign problem on a $6\times 6$ lattice, as a function of
the squared coupling constant, with and without this subtraction. A systematic
improvement is visible at small values of the coupling; at sufficiently large
value of $g^{2}$, the subtraction is no longer guaranteed to help.

Figure 3: The sign problem on a $6\times 6$ lattice with bare mass $m=0.15$
and chemical potential $\mu=1$, with and without the subtraction of Eq. (20).

##  V Nonperturbative Optimization

So far, we have described how a suitable subtraction can be engineered with
the aid of a systematic expansion, such as the weak coupling or heavy-dense
limit. Subtractions constructed in this manner need not be optimal, and it may
be profitable to consider other possibilities. In this section we will see
that it is possible to efficiently perform a nonperturbative optimization on a
family of ansatz subtractions to find the one with the largest average phase.
The method discussed here was used in a very similar form for optimizing
manifolds of integration Alexandru  _et al._ (2018a), and has been applied (in
one form or another) to several different field theories Alexandru  _et al._
(2018b); Kashiwa  _et al._ (2019); Ohnishi  _et al._ (2019).

Suppose we have a continuous family of actions $S_{\alpha}$ (the parameter
$\alpha$ may have many components), such that the partition function $Z=\int
e^{-S_{\alpha}}$ does not depend on $\alpha$. This is exactly the case if
$\alpha$ defines a subtraction, or as in Alexandru  _et al._ (2018a), a
manifold of integration. Although the partition function has no dependence on
$\alpha$, the quenched partition function and therefore the sign problem may.
In general, computing the sign problem for any fixed $\alpha$ is
computationally expensive. We would like to invest computational resources
efficiently, performing a simulation with the value of $\alpha$ that has the
mildest sign problem. However, finding such a value appears hard: it certainly
isn’t feasible to do a grid search, resolving the sign problem for each value
of $\alpha$, in order to find the best one.

Consider performing gradient ascent on the logarithm of the average phase.
Arbitrarily picking some initial $\alpha$, we would like to calculate
$\frac{\partial}{\partial\alpha}\log\frac{Z}{Z_{Q}(\alpha)}$, which specifies
the direction in which we should move. If we were to calculate this by finite
differencing, we would need to resolve the sign problem at both $\alpha$ and
$\alpha+\epsilon$, an expensive proposition. However, observe that

$\frac{\partial}{\partial\alpha}\log\frac{Z}{Z_{Q}(\alpha)}=-\frac{\partial}{\partial\alpha}\log
Z_{Q}(\alpha)$ (21)

has the form of a derivative of the logarithm of the _quenched_ partition
function, and the contribution of the physical $Z$ cancels entirely. The
direction which most quickly alleviates the sign problem is a quenched
expectation value, which can be computed without encountering a sign problem.

With this observation in hand, we see that it is possible to begin with a
family of subtractions $g_{\alpha}$, and perform an efficient, sign-free
gradient descent to find the optimal subtraction in that family. At this
point, a (comparatively expensive) Monte Carlo can be performed, with high
statistics to counter the remaining sign problem.

One motivation for this method stems from the “weak-coupling” subtraction of
the previous method. The subtraction $g=f_{1}-Z_{1}$ defined by Eq. (20) can
be multiplied by an arbitrary coefficient $\alpha$, so that the integrand of
the partition function is modified by

$-g_{\alpha}=-\alpha f_{0}\det
K_{0}\operatorname{{Tr}}K_{0}^{-1}\left(\frac{\partial K}{\partial
A}\right)_{A=0}A\text{.}$ (22)

In the previous section, the coefficient used was implicitly $1$; as shown in
Fig. 4, it turns out that this is not the optimal coefficient. The
optimization procedure described above can be used to optimize this
coefficient at scale. Note that for the example shown here, the full-magnitude
first-order subtraction makes the sign problem _worse_ at $g^{2}=0.3$.
However, nonperturbative optimization can reverse this, making the first-order
subtraction useful even at this relatively large coupling.

Figure 4: The magnitude of the sign problem for a $4\times 4$ lattice with
$m=0.15$, $g^{2}=0.3$, and $\mu=1$, as a function of the subtraction
coefficient $\alpha$, using the subtraction of Eq. (22).

##  VI Discussion

The method of subtractions described in this paper allows practical mitigation
of sign problems associated to finite fermion density and real-time
observables. The method is exact in the sense that it makes no additional
approximations in the partition function. Furthermore, the removal of the sign
problem, although only approximate, is systematically improvable.

This method is not unrelated to prior work. In particular, the method of field
complexification Alexandru  _et al._ (2020) may be seen as a specific strategy
for constructing a subtraction111In fact, the subtraction method was initially
inspired by an attempt to extend the method of field complexification to the
case of path integrals with discrete domains of integration.. In that method,
the original domain of the path integral — $\mathbb{R}^{N}$, say — is expanded
to a complex space of twice the (real) dimension. In this case, the expanded
space would be $\mathbb{C}^{N}$. By Cauchy’s integral theorem, the path
integral can now be performed over any $N$-real-dimensional manifold
$\mathcal{M}\subset\mathbb{C}^{N}$ obtained by a smooth deformation from
$\mathbb{R}^{N}$ (and with mild constraints at infinity, when the complex
space is unbounded). Typically the new manifold is parameterized by the real
plane via a function $\tilde{\phi}$ mapping field configurations
$\phi\in\mathbb{R}^{N}$ to field configurations on $\mathcal{M}$, so that the
deformed path integral is written

$Z=\int_{\mathbb{R}^{N}}\\!\mathcal{D}\phi\;e^{-S[\phi]}=\int_{\mathbb{R}^{N}}\\!\mathcal{D}\phi\;e^{-S[\tilde{\phi}(\phi)]}\det\frac{\partial\tilde{\phi}}{\partial\phi}\text{.}$
(23)

The difference between the two integrands is zero, and so can be viewed as a
subtraction. Of course, in this view, every modification to the path integral
that leaves the integration domain unchanged is a special case of the
subtraction method.

We can also go a step further and note that the difference between the two
integrands is a total derivative. Concretely, in one dimension, the difference
between the two Boltzmann factors is

$e^{-S[\tilde{\phi}(\phi)]}\det\frac{\partial\tilde{\phi}}{\partial\phi}-e^{-S[\phi]}=\frac{\partial}{\partial\phi}\int_{\phi}^{\tilde{\phi}(\phi)}e^{-S[\phi^{\prime}]}\;\mathrm{d}\phi^{\prime}\text{.}$
(24)

It is notable that a well-chosen subtraction can resolve a sign problem even
in cases where no manifold can. A simple example of a sign problem unremovable
by any choice of manifold is the one-dimensional integral (which is to be
considered a mock partition function)

$Z=\int_{-\pi}^{\pi}\\!\mathrm{d}\theta\;\left[\cos(\theta)+\epsilon\right]\text{.}$
(25)

The sign problem associated to this partition function becomes arbitrarily bad
as $\epsilon$ is taken towards $0$. This sign problem was shown in Lawrence
(2020) to be unremovable by any choice of integration contour. In fact, the
original integration domain $S^{1}$ has a more mild sign problem than any
other choice of domain. In this case, it’s particularly easy to see that a
subtraction of $\cos\theta$ completely removes the sign problem, where no
manifold can. Thus the method of subtractions is strictly more powerful than
that of complexification.

The manifold used in Alexandru  _et al._ (2018a, b) to improve the sign
problem of the Thirring model in $1+1$ and $2+1$ dimensions was motivated
(post-hoc) by the leading-order term in the heavy-dense expansion. In Lawrence
(2018) it was shown that a manifold of that form can entirely remove the sign
problem coming from that leading-order term. This choice of manifold is
therefore equivalent to a subtraction constructed from that term.

The complexification method has been applied to real-time observables through
the lattice Schwinger-Keldysh formalism Alexandru  _et al._ (2016c). The
determination of real-time observables on the lattice remains a largely
unexplored area. Future work should be able to apply the subtraction method to
real-time calculations through the same formalism.

The success of the method described in this paper depends on the availabilty
of a systematic expansion in which the sign problem can be seen. We have seen
that several options exist for the Thirring model. Examining and making use of
such expansions in other models is a critical next step.

We noted in Sec. III that in addition to improving the sign problem, the
signal-to-noise ratio associated with the modified observable was improved
from the one associated with the original observable. This was not explored
further in this paper, but it suggests that the same or a similar method could
be deployed explicitly for treating expensive signal-to-noise problems. It is
not entirely surprising that this should be possible, as the closely related
complexification method has recently been applied to noisy observables in
Abelian gauge theory and complex scalar field theory Detmold  _et al._ (2020).

###### Acknowledgements.

I am indebted to Andrei Alexandru, Paulo Bedaque, and Henry Lamm for many
useful conversations regarding the sign problem. I am also grateful to Henry
Lamm for comments on an earlier version of this manuscript. This work was
supported by the U.S. Department of Energy under Contract No. DE-
FG02-93ER-40762, and subsequently by the U.S. Department of Energy under
Contract No. DE-SC0017905.

## References

  * Jerrum and Sinclair (1993) M. Jerrum and A. Sinclair, SIAM Journal on computing 22, 1087 (1993).
  * Guo and Jerrum (2016) H. Guo and M. Jerrum, “Random cluster dynamics for the ising model is rapidly mixing,” (2016), arXiv:1605.00139 [cs.DS] .
  * Collevecchio  _et al._ (2016) A. Collevecchio, T. M. Garoni, T. Hyndman, and D. Tokarev, Journal of Statistical Physics 164, 1082–1102 (2016).
  * Aarts and Stamatescu (2008) G. Aarts and I.-O. Stamatescu, JHEP 09, 018 (2008), arXiv:0807.1597 [hep-lat] .
  * Langfeld and Lucini (2016) K. Langfeld and B. Lucini,  _Proceedings, International Meeting Excited QCD 2016: Costa da Caparica, Portugal, March 6-12, 2016_ , Acta Phys. Polon. Supp. 9, 503 (2016), arXiv:1606.03879 [hep-lat] .
  * Alexandru  _et al._ (2005) A. Alexandru, M. Faber, I. Horvath, and K.-F. Liu, Phys. Rev. D72, 114513 (2005), arXiv:hep-lat/0507020 [hep-lat] .
  * de Forcrand and Kratochvila (2006) P. de Forcrand and S. Kratochvila,  _Hadron physics, proceedings of the Workshop on Computational Hadron Physics, University of Cyprus, Nicosia, Cyprus, 14-17 September 2005_ , Nucl. Phys. Proc. Suppl. 153, 62 (2006), [,62(2006)], arXiv:hep-lat/0602024 [hep-lat] .
  * Fodor and Katz (2002) Z. Fodor and S. D. Katz, Phys. Lett. B534, 87 (2002), arXiv:hep-lat/0104001 [hep-lat] .
  * Allton  _et al._ (2002) C. R. Allton, S. Ejiri, S. J. Hands, O. Kaczmarek, F. Karsch, E. Laermann, C. Schmidt, and L. Scorzato, Phys. Rev. D66, 074507 (2002), arXiv:hep-lat/0204010 [hep-lat] .
  * Chandrasekharan (2013) S. Chandrasekharan, Eur. Phys. J. A49, 90 (2013), arXiv:1304.4900 [hep-lat] .
  * Alexandru  _et al._ (2020) A. Alexandru, G. Basar, P. F. Bedaque, and N. C. Warrington, (2020), arXiv:2007.05436 [hep-lat] .
  * de Forcrand and Philipsen (2007) P. de Forcrand and O. Philipsen, JHEP 01, 077 (2007), arXiv:hep-lat/0607017 [hep-lat] .
  * Thirring (1958) W. E. Thirring, Annals of Physics 3, 91 (1958).
  * Alexandru  _et al._ (2017) A. Alexandru, G. Basar, P. F. Bedaque, G. W. Ridgway, and N. C. Warrington, Phys. Rev. D 95, 014502 (2017), arXiv:1609.01730 [hep-lat] .
  * Alexandru  _et al._ (2016a) A. Alexandru, G. Basar, P. F. Bedaque, G. W. Ridgway, and N. C. Warrington, JHEP 05, 053 (2016a), arXiv:1512.08764 [hep-lat] .
  * Pawlowski and Zielinski (2013) J. M. Pawlowski and C. Zielinski, Phys. Rev. D 87, 094509 (2013), arXiv:1302.2249 [hep-lat] .
  * Alexandru  _et al._ (2016b) A. Alexandru, G. Basar, and P. Bedaque, Phys. Rev. D 93, 014504 (2016b), arXiv:1510.03258 [hep-lat] .
  * Montvay and Münster (1997) I. Montvay and G. Münster,  _Quantum fields on a lattice_ (Cambridge University Press, 1997).
  * Pawlowski  _et al._ (2015) J. M. Pawlowski, I.-O. Stamatescu, and C. Zielinski, Physical Review D 92 (2015), 10.1103/physrevd.92.014508.
  * Alexandru  _et al._ (2018a) A. Alexandru, P. F. Bedaque, H. Lamm, and S. Lawrence, Phys. Rev. D97, 094510 (2018a), arXiv:1804.00697 [hep-lat] .
  * Alexandru  _et al._ (2018b) A. Alexandru, P. F. Bedaque, H. Lamm, S. Lawrence, and N. C. Warrington, Phys. Rev. Lett. 121, 191602 (2018b), arXiv:1808.09799 [hep-lat] .
  * Kashiwa  _et al._ (2019) K. Kashiwa, Y. Mori, and A. Ohnishi, Phys. Rev. D 99, 114005 (2019), arXiv:1903.03679 [hep-lat] .
  * Ohnishi  _et al._ (2019) A. Ohnishi, Y. Mori, and K. Kashiwa, JPS Conf. Proc. 26, 024011 (2019).
  * Lawrence (2020) S. Lawrence,  _Sign Problems in Quantum Field Theory: Classical and Quantum Approaches_ , Ph.D. thesis (2020), arXiv:2006.03683 [hep-lat] .
  * Lawrence (2018) S. Lawrence,  _Proceedings, 36th International Symposium on Lattice Field Theory (Lattice 2018): East Lansing, MI, United States, July 22-28, 2018_ , PoS LATTICE2018, 149 (2018), arXiv:1810.06529 [hep-lat] .
  * Alexandru  _et al._ (2016c) A. Alexandru, G. Basar, P. F. Bedaque, S. Vartak, and N. C. Warrington, Phys. Rev. Lett. 117, 081602 (2016c), arXiv:1605.08040 [hep-lat] .
  * Detmold  _et al._ (2020) W. Detmold, G. Kanwar, M. L. Wagman, and N. C. Warrington, Phys. Rev. D 102, 014514 (2020), arXiv:2003.05914 [hep-lat] .


# A New Type of Cipher

Fabio F. G. Buono
<EMAIL_ADDRESS>
(5-1-2012)

###### Abstract

We will define a new type of cipher that doesn’t use neither an easy to
calcualate and hard to invert matematical function like RSA nor a classical
mono or polyalphabetic cipher.

Our cipher will use an intrinsic and not syntactic property of a sequence. The
core idea of this cipher is a process that is close to changing the
measurement units of the input sequence.

###### Contents

  1. 1 Introduction
  2. 2 The Idea
  3. 3 The cipher

##  1 Introduction

As known a cipher is an algorithm that takes as input some binary sequence and
gives back a ciphered sequence as output. This process is supposed to be
simple to compute but difficult to reverse unless the key is known (this is
known as a one way trapdoor mechanism).

The problem of most known ciphers (except the one-time-pad [2][3][7][8]), is
that their ciphertexts preserve some kind of structure which can be used from
some cryptanalyst to obtain the plaintext they originated from.

Many kind of cryptoanalisis use this strategy. Therefor we shall eliminate
this problem. To be uneffected by this pathology we shall mold our cipher
aroud a intrinsect non syntactic property of the information sequences, i.e.
its measurabilty as we will explain.

We are going to define a process (the measurement) that will be something like
a input sequence “weighing“, the ciphertext spawned by our cipher isn’t a
simple encoding in the classical meaning, but an allocation function of its
value, called from now $\nabla$.

I m going to explain in this article, some possible implementations of this
idea. These implementations will help on clarifying how we use $\nabla$ in our
process.

##  2 The Idea

The property we shall be using in our cipher, is a redefinition of a measure
of the input sequence. To give an idea of what we mean by a measure of
sequence we start with a simple example. The following base two sequence

$101000001$

is written base ten, giving exponents in reverse sequence, as shown in the
following example:

$2^{0}+2^{2}+2^{8}=261.$

Now we define $\nabla$ as a set of positive integer such that every element of
set will be smaller than previous and such that last element will be 1.

We call measure by nabla, a set of integer values. The first one is the result
of integer division between decimal value of input sequence and the value of
the first element of $\nabla$. Next value of the set is the result of integer
division between decimal value of the previous element of set ( first one in
this istance ) multiplied by the value of the element of $\nabla$ previously
used, and so on.

Now, we will be able to define a first cipher pseudo-code.

##  3 The cipher

To show a first example of how the cipher works, we can propose the pseudocode
below, there we take in input a binary sequence and translate it in its
decimal value. after that we take in input an array of integral value as
$\nabla$ and encode it. The output will be an array of measures by $\nabla$.

  * Function Cript: begin /* plaintext input as decimal value */