# Quantum Critical Points and the Sign Problem

R. Mondaini<EMAIL_ADDRESS>S. Tarat<EMAIL_ADDRESS>Beijing
Computational Science Research Center, Beijing 100193, China  R.T. Scalettar
<EMAIL_ADDRESS>Department of Physics, University of California,
Davis, CA 95616, USA

###### Abstract

The “sign problem” (SP) is the fundamental limitation to simulations of
strongly correlated materials in condensed matter physics, solving quantum
chromodynamics at finite baryon density, and computational studies of nuclear
matter. As a result, it is part of the reason fields such as ultra-cold atomic
physics are so exciting: they can provide quantum emulators of models that
could not otherwise be solved, due to the SP. For the same reason, it is also
one of the primary motivations behind quantum computation. It is often argued
that the SP is not intrinsic to the physics of particular Hamiltonians, since
the details of how it onsets, and its eventual occurrence, can be altered by
the choice of algorithm or many-particle basis. Despite that, we show that the
SP in determinant quantum Monte Carlo (DQMC) is quantitatively linked to
quantum critical behavior. We demonstrate this via simulations of a number of
fundamental models of condensed matter physics, including the spinful and
spinless Hubbard Hamiltonians on a honeycomb lattice and the ionic Hubbard
Hamiltonian, all of whose critical properties are relatively well understood.
We then propose a reinterpretation of the low average sign for the Hubbard
model on the square lattice when away from half-filling, an important open
problem in condensed matter physics, in terms of the onset of pseudogap
behavior and exotic superconductivity. Our study charts a path for exploiting
the average sign in QMC simulations to understand quantum critical behavior,
rather than solely as an obstacle that prevents quantum simulations of many-
body Hamiltonians at low temperature.

Over the last several decades, quantum Monte Carlo (QMC) simulations have
provided great insight into challenging strong correlation problems in
chemistry [1, 2], condensed matter [3, 4], nuclear [5], and high energy
physics [6]. In all these areas, however, the sign problem (SP), which occurs
when the probability for specific quantum configurations in the importance
sampling becomes negative, significantly constrains their application.
Solving, or at least mitigating, the SP is one of the central endeavors of
computational physics. The extent and importance of the effort is indicated by
the many proposed solutions, and their continued development over the last
three decades — see the Supplemental Materials (SM) for a review [7].

Despite enormous effort, the SP remains unsolved. In fact, the lack of
progress is one of the main driving forces behind a number of large-scale
efforts, including the quest for quantum emulators [8, 9, 10] as well as
quantum computing itself [11, 12]. One of the most fundamental mysteries
concerns the possible link between the sign problem and the underlying physics
of the Hamiltonian being investigated.

Here, instead of challenging this NP-hard problem [13], or proposing solutions
that can partially ameliorate its behavior [14, 15] we show that there is a
clear quantitative connection between the behavior of the average sign
$\langle{\cal S}\rangle$ in the widely used Determinant Quantum Monte Carlo
(DQMC) method and several quantum phase transitions: that of the semimetal to
antiferromagnetic Mott insulator (AFMI) of Dirac fermions in the spinful
[SU(2)] honeycomb-Hubbard Hamiltonian [16, 17], the band to correlated
insulator transition [18, 19, 20], and charge density wave transitions of
spinless [U(1)] fermions on a honeycomb lattice [21, 22]. In the first case,
simulations at half-filling, where the quantum critical point (QCP) occurs,
are SP free. We introduce a small doping $\mu$ and show, in the limit $\mu\to
0^{+}$ at temperature $T\to 0$, that $\langle{\cal S}\rangle$ evolves rapidly
as we tune through the QCP.

Our second illustration, the ionic Hubbard model, has a SP even at half-
filling. Here the average sign undergoes an abrupt drop at the band-insulator
(BI) to correlated metal (CM) transition. The third case, spinless fermions on
a honeycomb lattice, also has a semimetal to (charge) insulator transition.
Its interest relies on the existence of a SP-free approach. Studying it with a
method which contains an ‘unnecessary’ SP lends insight into the key question
of the algorithm dependence of links between the SP and the physics of model
Hamiltonians.

These three discussions establish a link between known physics of the models
and the fermion sign. Having made that connection, we then turn to the iconic
square lattice Hubbard model whose physics has not been conclusively
established. We find that the onset of the SP occurs in a dome-shaped region
of the filling-temperature phase space underneath that of the pseudogap (PG)
physics. The SP is well-enough controlled in the PG phase to obtain reliable
results for various observables, including the pairing correlations in various
channels, exhibiting dominant enhancement for $d$-wave symmetry. Because it
onsets exponentially in inverse temperature, the SP provides a rather sharp
demarcation of the regime, which mimics the superconducting dome of the
cuprates [23]. Although the SP prevents DQMC from resolving a signal of a
$d$-wave transition, the ground work established for the honeycomb lattice and
BI-CM models suggests that this sign problem dome might be linked to the onset
of a superconducting phase. In the conclusions we will make connections which
will further corroborate the generality of our results to other models and QMC
methods.

The Sign Problem; Model and Methodology

The origin of the sign problem can be understood in two related classes of
algorithms, ‘world-line’ Quantum Monte Carlo (WLQMC) [24] and Green’s function
Quantum Monte Carlo (GFQMC) [25, 26], by considering Feynman’s path integral
approach, which provides a mapping of quantum statistical mechanics in $D$
dimensions to classical statistical mechanics in $D+1$ dimensions. Paralleling
Feynman’s original exposition for the operator $e^{-{\rm i}\hat{H}t/\hbar}$,
the imaginary time evolution operator $e^{-\beta\hat{H}}$ is subdivided into
$L_{\tau}$ incremental pieces $\hat{U}_{\Delta\tau}=e^{-\Delta\tau\hat{H}}$,
where $L_{\tau}\,\Delta\tau=\beta$, the inverse temperature. Complete sets of
states $\hat{\cal I}_{\tau}=\sum_{S_{\tau}}|S_{\tau}\rangle\langle S_{\tau}|$
are introduced between each $\hat{U}_{\Delta\tau}$ so that the partition
function ${\cal Z}={\rm Tr}\,e^{-\beta\hat{H}}$ becomes a sum over the
classical degrees of freedom associated with the spatial labels of each
$\hat{\cal I}_{\tau}$, and also an additional imaginary time index denoting
the location $\tau=1,2,\ldots,L_{\tau}$ of $\hat{\cal I}_{\tau}$ in the string
of operators $\hat{U}_{\Delta\tau}$. The quantity being summed in the
calculation of ${\cal Z}$ is the product of matrix elements $\langle
S_{\tau}|\hat{U}_{\Delta\tau}|S_{\tau+1}\rangle$.

In such WLQMC/GFMC methods, the SP arises when $\prod_{\tau}\langle
S_{\tau}|\hat{U}_{\Delta\tau}|S_{\tau+1}\rangle<0$. Negative matrix elements
are unavoidable for itinerant fermionic models in $D>1$ because their sign
depends on the number of fermions intervening between two particles undergoing
exchange, and hence changes as the particle positions are updated. The basis
dependence of the sign problem is apparent by considering intermediate states
$|S_{\tau}\rangle$ chosen to be eigenstates $|\phi_{\alpha}\rangle$ of
$\hat{H}$. In that case the matrix elements are just $e^{-\Delta\tau
E_{\alpha}}$ and hence are trivially positive definite. Of course, since the
eigenstates of $\hat{H}$ are unknown, this is not a practical choice in any
non-trivial situation. Moreover, the SP can generally be avoided for bosonic
or spin models as long as the lattice is bipartite. Nonetheless, even bosonic
and spin Hamiltonians can have negative matrix elements on frustrated
geometries [27], especially for antiferromagnetic models, emphasizing the SP
is not solely a consequence of Fermi statistics.

‘Auxiliary field’ Quantum Monte Carlo (AFQMC) algorithms [28, 29, 30]
typically have a much less severe SP than WLQMC [31, 7]. They are based on the
observation that the trace of an exponential of a quadratic form of fermionic
operators can be done analytically, resulting in the determinant of a matrix
of dimension set by the cardinality of fermionic operators. The determinant is
the product $\prod_{j}\big{(}1+e^{-\beta\varepsilon_{j}}\big{)}$, where
$\varepsilon_{j}$ are the non-interacting energy levels, and is always
positive.

Figure 1: The SU(2) Hubbard model on the honeycomb lattice. (A) Cartoon
depicting a honeycomb lattice with $N=2L^{2}$ sites ($L=6$ here), accompanied
by the relevant terms in $\hat{H}$. (B) Contour plot of the average
$\langle{\cal S}\rangle$ in the $T/t$ ($\mu/t$) vs $U/t$ in the upper (lower)
panel. Here $L=9$ and $\mu/t=0.1$ ($T/t=1/20$) in the upper (lower) panel. (C)
The average sign extrapolated with the linear system size $L$, using
$T/t=1/20$ and $\mu/t=0.1$. (D) Similar extrapolation as in C, but displaying
a local quantity (the derivative of the double occupancy), which is an
indicator of the QCP. In all panels with data, the prediction for the ground-
state phase transition occurring at $U_{c}/t=3.869$ [17] is depicted by a star
marker.

If interactions are present, quartic terms in $\hat{H}$ are reduced to
quadratic ones with a Hubbard-Stratonovich (HS) transformation. The trace of
the resulting product of exponentials of quadratic forms can be performed, but
now they each depend on a different, i.e. imaginary-time dependent, auxiliary
field. The resulting determinant is no longer guaranteed to be positive; the
consequence is the SP since the HS field needs to be sampled stochastically in
order to compute operator expectation values.

In AFQMC, the trace over fermionic degrees of freedom is done for all species
(i.e. all spin and orbital indices $\alpha$). If there is no hybridization
between different $\alpha$, each trace gives an individual determinant. In
some situations, particle-hole, time-reversal, or other symmetries [32, 33,
34] impose a relation between the determinants for different $\alpha$’s, and
as a consequence the negative determinants always come in pairs. Low
temperature (ground-state) properties can be accessed in such ‘sign problem
free’ cases, and a host of interesting quantum phase transitions has been
explored [35, 36, 37, 38]. If such a partnering does not occur, a reasonable
rule of thumb is that the average sign $\langle{\cal S}\rangle$ is
sufficiently bounded away from zero with measurements that exhibit
sufficiently small error bars for $T\gtrsim W/20\,$-$\,W/40$, at intermediate
interaction strengths (of the same order as the bandwidth $W$) 111This is just
a rough guideline; the precise onset of the SP is determined by lattice
geometry, doping (chemical potential), and interaction strength. A catalog of
the SP in DQMC for the single band Hubbard model in different situations is
given in Ref. [59]..

The DQMC methodology [28, 29] we use is a specific implementation of AFQMC. We
employ the discrete HS transformation introduced by Hirsch [40] and choose the
Trotter discretization $\Delta\tau$ such that systematic errors in
$\langle{\cal S}\rangle$ and other observables are of the same order as
statistical sampling errors. (See [7] for additional details.)

We mostly consider models in which two (spin) species of itinerant electrons
hop on a lattice with an on-site repulsion, i.e., variants of the Hubbard
Hamiltonian,

$\displaystyle\hat{H}=$
$\displaystyle-\sum_{ij\,\sigma}t_{ij}\big{(}\,\hat{c}^{\dagger}_{i\sigma}\hat{c}^{\phantom{\dagger}}_{j\sigma}+\hat{c}^{\dagger}_{j\sigma}\hat{c}^{\phantom{\dagger}}_{i\sigma}\,\big{)}-\sum_{i\sigma}\mu_{i}\,\hat{n}_{i\sigma}$
$\displaystyle+U\sum_{i}\left(\hat{n}_{i\uparrow}-\frac{1}{2}\right)\,\left(\hat{n}_{i\downarrow}-\frac{1}{2}\right).$
(1)

Here $\hat{c}^{\dagger}_{j\sigma}(\hat{c}^{\phantom{\dagger}}_{j\sigma})$ are
creation (destruction) operators at site $i$ with spin $\sigma$ and
$\hat{n}_{i\sigma}=\hat{c}^{\dagger}_{i\sigma}\hat{c}^{\phantom{\dagger}}_{i\sigma}$
is the number operator. In Sec. I, $i,j$ are near-neighbor sites on a
honeycomb lattice, with $t_{ij}=t$. As a consequence of particle-hole symmetry
(PHS), $\mu_{i}=0$ corresponds to half-filling, and
$\rho=\langle\hat{n}_{i\sigma}\rangle=1/2$, for arbitrary $U$ and temperature
$T$. In Sec. II, we consider a $t_{ij}=t$ square lattice with
$\mu_{i}=+\Delta$ on one sublattice and $\mu_{i}=-\Delta$ on the other, a
situation which has a SP even at half-filling, but which is mild enough to
allow its phase diagram to be established with reasonable reliability. Sec.
III concerns a single species model with interactions between fermions on
neighboring sites, notable because a SP-free QMC formulation exists [22, 41].

All these models have QCPs which have been located to fairly high precision
and so serve as testbeds for demonstrating that the average sign can be used
as an alternate means to study the onset of quantum criticality. In our final
investigation, Sec. IV, we consider the doped, spinful, square lattice Hubbard
model, much of whose low temperature physics remains shrouded in mystery. We
correlate the behavior of the SP with some of its properties at intermediate
temperature, and then describe what might be inferred concerning one the most
elusive puzzles–the presence of a low temperature superconducting dome.

I. Semimetal to AFMI on a Honeycomb Lattice

On a honeycomb lattice (Fig. 1A), the $U=0$ Hubbard Hamiltonian has a semi-
metallic density of states which vanishes linearly at $E=0$. Its dispersion
relation $E({\bf k})$ has Dirac points in the vicinity of which the kinetic
energy varies linearly with momentum. Unlike the square lattice that displays
AF order for all $U\neq 0$, the honeycomb Hubbard model at $T\to 0$ remains a
semimetal for small nonzero $U$, turning to an AF insulator only for $U$
exceeding a critical $U_{c}$. Early DQMC and series expansion calculations
estimated $U_{c}\sim 4\,t$ [42], with subsequent studies [16, 17] yielding the
more precise value $U_{c}/t=3.869$.

The upper panel of Fig. 1B gives $\langle{\cal S}\rangle$ in the $U$-$T$
plane. By introducing a small non-zero $\mu=0.1$, we can induce a SP which
begins to develop at $T/t\sim 0.1$. As $T$ is lowered further the average sign
deviates from $\langle{\cal S}\rangle=1$ in a relatively narrow window of
$U/t$ close to the known $U_{c}$. In turn, we show the $\langle{\cal
S}\rangle$ on the $U-\mu$ plane at fixed $T/t=0.05$ in the lower panel of Fig.
1B. For large $\mu$ the sign is small for a broad swath of interaction values.
As $\mu$ decreases this region pinches down until it terminates close to
$U_{c}$; the dashed white line displays the minimum $\langle{\cal S}\rangle$
in the relevant range. In both panels, the behavior of the average sign
outlines the quantum critical fan that extends above the QCP.

Figure 1C shows a finite size extrapolation of $\langle{\cal S}\rangle$ in the
$1/L-U$ plane, where $L$ is the linear lattice size. Just as $\langle{\cal
S}\rangle$ worsens with increasing $\beta$, it is also known to deviate
increasingly from $\langle{\cal S}\rangle=1$ with growing $L$ [29]. What these
data further indicate is that the extrapolation $L\rightarrow\infty$ clearly
reveals $U_{c}$ in the presence of a small chemical potential. So far, we have
exclusively used $\langle{\cal S}\rangle$ in locating $U_{c}$. Original
investigations employed more ‘traditional’ (and more physical) correlation
functions such as the AF structure factor and conductivity. For comparison to
the evolution of $\langle{\cal S}\rangle$, Fig. 1D shows one example, the rate
of change of the double occupancy $D$, again in the $1/L-U$ plane. A peak in
$-dD/dU$ indicates where local moments $\langle m^{2}\rangle$ are growing most
rapidly. The similarity between Figs. 1C and 1D emphasizes how $\langle{\cal
S}\rangle$ is tracking the physics of the model in a way remarkably similar to
$\langle m^{2}\rangle$. The combination of the three limits, $\mu,\beta,L$,
unequivocally points out the QCP location; the SM [7] contains further
discussion, and other observables.

Figure 2: The SU(2) Ionic Hubbard model on the square lattice. (A) Cartoon
depicting a square lattice with $N=L^{2}$ sites ($L=4$ here), accompanied by
the relevant terms in $\hat{H}$. (B) Contour plot of the average $\langle{\cal
S}\rangle$ in the $U/t$ vs. $T/t$ plane, with staggered potential
$\Delta/t=0.5$. (C) The contour of $\langle{\cal S}\rangle$ as function of the
competing parameters $U/t$ and $\Delta/t$, at a temperature $T/t=1/24$. (D)
The corresponding derivative of the double occupancy on the $+\Delta$ sites at
the same parameters as in C. In all data, Trotter discretization is chosen as
$\Delta\tau=0.1$ and the lattice size is $L=12$. Figure 3: The U(1) Hubbard
model on the honeycomb lattice. (A) Schematics of the spinless fermion
Hamiltonian [Eq. (2)] with nearest-neighbor interaction on a lattice with
$L=3$. Temperature extrapolation of the average $\langle{\cal S}\rangle$ as
function of the nearest-neighbor interaction $V/t$, for a lattice with $L=9$.
(D) [(C)] Extrapolation of the average sign [derivative of the nearest-
neighbor correlation in respect to $V$] with the inverse of the linear size
$L$ along a range of interactions, at a temperature $T$ that scales with the
system size $T/t=0.0375/L\Delta\tau$. Here $\langle{\cal S}\rangle$ marginally
increases when tackling larger sizes, indicating that the dynamical critical
exponent $z$ in the scaling with $L_{\tau}/L^{z}$ is larger than one [43, 7];
we used $z=1$ above. In all data, Trotter discretization is chosen as
$\Delta\tau=0.1$. As for the SU(2) case, the star marker depicts the best
known value of the interactions that trigger the Mott insulating phase; here
with CDW order at the ground-state [41].

II. Ionic Hubbard BI to AF Transition

Among the different types of non-conducting states are ‘band insulators’ (BI),
in which the chemical potential lies in a gap in the non-interacting density
of states (DOS), and ‘Mott insulators’ (MI) in which strong repulsive
interactions prevent hopping at commensurate filling. The evolution from BI to
MI is a fascinating issue in condensed matter physics [18, 44, 45, 46, 19,
20]. In the ionic Hubbard model we investigate here, a staggered site energy
$\mu_{i}=\pm\Delta$ on the two sublattices of a square lattice (Fig. 2A) leads
to a dispersion relation $E(k)=\pm\sqrt{\varepsilon(k)^{2}+\Delta^{2}}$ with
$\varepsilon(k)=-2t\,({\rm cos}k_{x}+{\rm cos}k_{y}\,)$. The resulting DOS
vanishes in the range $-\Delta<E<+\Delta$ in which the lattice is half-filled,
resulting in a BI. The occupation of the ‘low energy’ sites $\mu_{i}=-\Delta$
is greater than that of the ‘high energy’ sites $\mu_{i}=+\Delta$, so that
there is a trivial charge density wave (CDW) order associated with an explicit
breaking of the sublattice symmetry in the Hamiltonian.

An onsite repulsion $U$ disfavors this density modulation: The potential
energy $Un_{i\uparrow}n_{i\downarrow}$ is higher than for a uniform
occupation. Thus the driving physics of the BI, the staggered site energy
$\Delta$ and that of the MI, the repulsion $U$, are in competition. Although
the simplest scenario is a direct BI to MI transition with increasing $U$, one
of the more exotic possible outcomes is the emergence of a metallic phase when
these two energy scales are in balance and neither type of insulator can
dominate the behavior. Past DQMC simulations suggest this less trivial case
occurs, and have used the temperature dependence of the dc conductivity to
bound the metallic phase [46, 47].

Here we investigate how this physics might be reflected in the average sign.
Figure 2 B shows $\langle{\cal S}\rangle$ in the $U/t-T/t$ plane at
$\Delta=0.5\,t$. As $T$ is lowered, $\langle{\cal S}\rangle$ deviates from
unity for a range of intermediate $U$ values. Figure 2 C gives the behavior in
the $U/t-\Delta/t$ plane at fixed low $T=t/24$. The central result is that
$\langle{\cal S}\rangle$ is small in a region which maps well with the
previously determined boundaries of the metallic phase [46, 47]. This is
emphasized by a comparison to Fig. 2 D, which uses one of the ‘traditional’
methods for phase boundary location, namely the behavior of the double
occupancy. The BI has a low occupancy, and hence very low double occupancy on
the $+\Delta$-sites. Increasing $U$ smooths out the density, so that the
double occupancy on the $+\Delta$-sites increases: $d\langle
n_{\uparrow\downarrow,+\Delta}\rangle/dU>0$. In contrast, in the MI region,
$U\gtrsim\Delta$, the physics is that of the usual Hubbard Hamiltonian and
double occupancy decreases as $U$ grows: $d\langle
n_{\uparrow\downarrow,+\Delta}\rangle/dU<0$.

In the CM region between BI and MI, however, obtaining a relevant signal-to-
noise ratio for the traditional observables is exponentially challenging
precisely because the average sign vanishes in this region. The ‘phase
diagram’ obtained by $\langle{\cal S}\rangle$ (Fig. 2 C) is remarkably similar
to that given by the physical observable, the rate of change of double
occupancy with $U$ (Fig. 2 D)

As in the determination of the QCP for the spinful Hubbard model on a
honeycomb lattice, $\langle{\cal S}\rangle$ emerges as more than a mere
nuisance, but as a harbinger of the physics. An in-depth similarity between
these two situations is discussed in the SM [7], where we show that the BI-
metal QCP is again uniquely identified by the $1/L$ scaling of $\langle{\cal
S}\rangle$, in precise analogy with the honeycomb case. These results suggest
the existence of a quantum critical region associated with the CM phase and
the vanishing $\langle{\cal S}\rangle$.

III. An ‘Unnecessary’ Sign Problem

We now consider spinless fermions, where the on-site Hubbard interaction $U$,
made irrelevant by the Pauli principle, is replaced by an intersite repulsion
$V$,

$\displaystyle\hat{H}=$ $\displaystyle-t\sum_{\langle
ij\rangle}\big{(}\,\hat{c}^{\dagger}_{i}\hat{c}^{\phantom{\dagger}}_{j}+\hat{c}^{\dagger}_{j}\hat{c}^{\phantom{\dagger}}_{i}\,\big{)}+V\sum_{\langle
ij\rangle}\hat{n}_{i}\hat{n}_{j}.$ (2)

Equation 2 provides an example of a model where the SP can be completely
solved by utilizing special techniques such as the fermion bag in the
Continuous Time QMC approach [35], or by going to a different basis employing
a Majorana representation of the fermions in the AFQMC method [41], as long as
the system is on a bipartite lattice and $V>0$. The standard Blankenbecler,
Scalapino, and Sugar (BSS) approach [28], on the other hand, manifestly
displays a SP in the low temperature regime. Nevertheless, in order to study
the sign and its connection with the underlying physics, we use a BSS based
algorithm to investigate the system on a honeycomb lattice (Fig. 3 A).
Consideration of this ‘unnecessary’ SP allows us to address fundamental issues
related to the algorithm dependence of links between the SP and the physics of
model Hamiltonians.

At $T=0$, the model displays a QPT between a Dirac semimetal and an insulating
staggered CDW state as the interaction is tuned through a critical value
$V_{c}$ [22]. At large $V$, the repulsive interaction favours a CDW state,
distinguished from that of the ionic Hubbard model by the fact that there is
no staggered external field here – the CDW phase is a result of spontaneous
symmetry breaking. As $V$ is reduced, increasing quantum fluctuations due to
hopping finally destroy the CDW state, resulting in a Dirac semimetal for
$V<V_{c}$. Accurate estimates based on SP free methods yield $V_{c}\sim 1.35t$
[41].

In Fig. 3 B, we show a map of the temperature extrapolation of $\langle{\cal
S}\rangle$ as a function of $V$. The sign shows a clear reduction around the
known $V_{c}$ (denoted by the star).

Figure 3 D shows the spatial lattice size dependence of the sign, and Fig. 3
C, once again, a more ‘traditional’ local variable, the derivative of the
nearest-neighbor (NN) density-density correlation, $\langle
n_{i}n_{j}\rangle_{\rm NN}$, with respect to $V$. In the CDW phase, increasing
$V$ strengthens the staggered order, reducing the NN density correlations, and
hence $-d\langle n_{i}n_{j}\rangle_{\rm NN}/dV$ is positive. Conversely, the
effect is much smaller in the semimetal state, where the derivative is close
to zero. The transition $V_{c}$ is characterized by a clear downturn in this
quantity, which becomes progressively sharper as $L$ increases, as Figure 3 C
shows. This variable, thus, serves as a physical indicator of the QPT,
allowing a comparison of Figs. 3 C,D to demonstrate the connection between the
QCP and the behavior of $\langle{\cal S}\rangle$. In this model, $\langle{\cal
S}\rangle$ is well enough behaved that a study of the finite-temperature CDW
transition with DQMC is feasible [7], without having to resort to SP-free
approaches [48].

IV. Square Lattice Hubbard Model

Figure 4: Square lattice Hubbard model. (A) Temperature dependence of the
average $\langle{\cal S}\rangle$ as function of the chemical potential
$\mu/t$, for a lattice with $L=16$, $U/t=6$ and next-near-neighbor hopping
$t^{\prime}/t=-0.2$, values chosen to be close to those in cuprate materials.
(B) The $d$-wave pair susceptibility (subtracted from the non-vertex
contribution) for the same parameters. (C) The corresponding static spin
susceptibility $\chi(\textbf{q}=0)$. The white markers describe its peak for
values at which the average sign is large enough to allow a reliable
calculation, which encompasses the pseudogap regime. (D, E and F) display the
corresponding diagrams when converting to the calculated average density. The
black markers depict the actual average density extracted from the regular
mesh of $\mu$ used in the upper panels, and where an interpolation of the data
is performed. In all data, Trotter discretization is chosen as
$\Delta\tau=0.0625$.

The essential physics of the cuprate superconductors consists of
antiferromagnetic order at and near one hole per CuO2 cell, a superconducting
dome upon doping, which typically extends to densities
$0.6\lesssim\rho\lesssim 0.9$ and a ‘pseudogap’/‘strange metal’ phase above
the dome [49, 23]. There are many quantitative, experimentally-based, phase
diagrams of different materials which determine the regions occupied by these
phases [50]. Likewise, there are computational studies of individual
$(\rho,T,U)$ points establishing magnetic/charge order [51], linear
resistivity [52], a reduction in the spectral weight for spin excitations [53,
54], and $d$-wave pairing [55, 56].

Here we reveal a ‘sign problem phase diagram’ which bears significant
resemblance to that of experiments. As is well known, the severity of the sign
problem itself precludes determination of $d$-wave order in DQMC via
‘traditional’ observables such as the associated correlation functions.
However, Figure 4, based on the behavior of the sign itself, is suggestive. We
report the average sign (Fig. 4 A), the enhancement of the $d$-wave pairing
susceptibility over its value in the absence of the pairing vertex [57] (Fig.
4 B), and the uniform, static spin susceptibility $\chi(\textbf{q}=0)$ in both
the $T/t-\mu/t$ (A–C) and $T/t-\rho$ (D–F) planes – see SM [7].

The most salient features of this ‘sign phase diagram’ are (i) the ‘dome’ of
vanishing $\langle{\cal S}\rangle$ which occurs in a range of densities
$0.4\lesssim\rho\lesssim 1$ as $T$ is lowered (Fig. 4 D); (ii) the enhancement
of $d$-wave pairing (Fig. 4 E) surrounding the sign dome; and (iii), that the
magnetic properties are also linked to the $\langle{\cal S}\rangle$-dome: the
trajectory tracing the peak value of $\chi(q=0)$ as $T$ is decreased
terminates precisely at the top of the dome (Fig. 4 F). In isolation, the
comparisons of the behavior of the sign and the pairing and magnetic responses
in the square lattice Hubbard model appear likely to be merely coincidental.
Indeed, the fact that the sign is worst precisely for optimal dopings has been
previously remarked, but thought to be just ‘bad luck’ [57, 32, 58, 59].
However, that the known QCP of the three models discussed in Secs. I-III can
be quantitatively linked to the behavior of $\langle{\cal S}\rangle$ suggest
that the sign dome might actually be indicative of the presence of $d$-wave
superconductivity.

Discussion and Outlook

Early in the history of the study of the sign problem, a simple connection was
noted between the fermionic physics and negative weights in auxiliary field
QMC: If one artificially constructs two Hubbard-Stratonovich field
configurations, one associated with two particle exchanging as they propagate
in imaginary time and another with no exchange, one finds that the associated
fermion determinants are negative in the former case, and positive in the
latter [60]. This interesting observation, however, pertains to low density,
that is, to the propagation of just two electrons. Another key observation is
that the SP can be viewed as being proportional to the exponential of the
difference of free energy densities of the original fermionic problem, and the
one used with the weights in the Monte Carlo sampling taken to be positive,
akin to a bosonic formulation of the problem [32, 13]. It highlights how
intrinsic the SP is in QMC methods. A last important remark is that ordered
phases are often associated with a reduction in the importance of
configurations which scramble the sign. This is graphically illustrated in the
snapshots of [24]. Although less crisp, similar effects are seen in auxiliary
field QMC, for example in considering the evolution from the attractive
Hubbard model to the Holstein model with decreasing phonon frequency
$\omega_{0}$. Reducing $\omega_{0}$ acts to increase the effect of the phonon
potential energy term $\hat{P}^{2}$ in $\hat{H}$, thereby straightening the
auxiliary field in imaginary time.

Here we have shown that the behavior of the average sign $\langle{\cal
S}\rangle$ in DQMC simulations holds information concerning finite density
thermodynamic phases and transitions between them: the quantum critical points
in the semimetal to antiferromagnetic Mott insulator transition of Dirac
fermions, the band insulator to metal to correlated insulator evolution of the
ionic Hubbard Hamiltonian, and the QCP of spinless fermions (even though a
sign-problem free formulation exists). Specifically, a rapid evolution of
$\langle{\cal S}\rangle$ marks the positions of quantum critical points. We
have chosen these models as representative examples of QCP physics of
itinerant electrons which have been extensively studied in the condensed
matter physics community, but believe the result to be general. In fact, in a
model for frustrated spins in a ladder, using a completely different QMC
method (stochastic series expansion), similar conclusions can be inferred
[61], further corroborating this generality.

Likewise, in the square lattice version of the $U(1)$ Hubbard model that we
studied here, with an added $\pi$-flux, it can be shown that in the sign-
problem free formulation, the QMC weights, when expressed in terms of the
square of Pfaffians (Pf), holds similar information, namely, that $\langle{\rm
sgn(Pf)}\rangle$ departs from 1 close to the QCP for this model [62]. These
results provide further evidence that the average sign of the QMC weights is
inherently connected to the physics of the model in many unrelated models and
methods, but an even broader study may be necessary to establish this
conclusively.

Having established this connection in Hamiltonians with known physics, we have
also presented a careful study of the sign problem for the Hubbard model on a
2D square lattice, which is of central interest to cuprate $d$-wave
superconductivity. The intriguing ‘coincidence’ that the sign problem is worst
at a density $\rho\sim 0.87$, which corresponds to the highest values of the
superconducting transition temperature, has previously been noted [57, 32, 58,
59]. It is worth emphasizing that we have not here presented any solution to
the sign problem. However, our work does establish the surprising fact that
$\langle{\cal S}\rangle$ can be used as an ‘observable’ which can quite
accurately locate quantum critical points in models like the spinful and
spinless Hubbard Hamiltonians on a honeycomb lattice, and the ionic Hubbard
model, and also provides a clearer connection between the evolution of the
fermion sign and the strange metal/pseudogap and superconducting phases of the
iconic square lattice Hubbard model.

### Acknowledgments

We acknowledge insightful discussions with S.-J. Hu and H.-Q. Lin. Funding:
R.T.S. was supported by the grant DE‐SC0014671 funded by the U.S. Department
of Energy, Office of Science. R.M. acknowledges support from the National
Natural Science Foundation of China (NSFC) Grants No. NSAF-U1930402, No.
11974039 and No. 12050410263. Computations were performed on the Tianhe-2JK at
the Beijing Computational Science Research Center. Author contributions: R.T.S
proposed the original idea for the honeycomb lattice; R.M. suggested its
extension to the ionic and spinless fermion cases. All authors considered the
square lattice Hubbard model, performed numerical simulations, analyzed data,
and co-wrote the manuscript. Competing interests: Authors declare no competing
interests. Data and materials availability: All data needed to evaluate the
conclusions in the paper are presented in the main text or the supplementary
materials. Further raw data is available at [63].

## References

  * Hammond  _et al._ [1994] B. Hammond, W. Lester, and P. Reynolds,  _Monte Carlo Methods in Ab Initio Quantum Chemistry_ , Lecture and Course Notes in Chemistry: Volume 1 (World Scientific, 1994).
  * Needs  _et al._ [2020] R. Needs, M. Towler, N. Drummond, P. López Ríos, and J. Trail, Variational and diffusion quantum Monte Carlo calculations with the CASINO code, J. Chem. Phys. 152, 154106 (2020).
  * Ceperley [1995] D. Ceperley, Path integrals in the theory of condensed Helium, Rev. Mod. Phys. 67, 279 (1995).
  * Foulkes  _et al._ [2001] W. Foulkes, L. Mitas, R. Needs, and G. Rajagopal, Quantum Monte Carlo simulations of solids, Rev. Mod. Phys. 73, 33 (2001).
  * Carlson  _et al._ [2015] J. Carlson, S. Gandolfi, F. Pederiva, S. C. Pieper, R. Schiavilla, K. Schmidt, and R. Wiringa, Quantum Monte Carlo methods for nuclear physics, Rev. Mod. Phys. 87, 1067 (2015).
  * Degrand and DeTar [2006] T. Degrand and C. DeTar,  _Lattice Methods for Quantum Chromodynamics_ (World Scientific, 2006).
  * [7] See Supplemental Material, and references therein, for a review of the sign problem, more details of different observables, and further analysis of the average sign.
  * Esslinger [2010] T. Esslinger, Fermi-Hubbard physics with atoms in an optical lattice, Annu. Rev. Condens. Matter Phys. 1, 129 (2010).
  * Bloch  _et al._ [2012] I. Bloch, J. Dalibard, and S. Nascimbène, Quantum simulations with ultracold quantum gases, Nat. Phys. 8, 267 (2012).
  * Schäfer  _et al._ [2020] F. Schäfer, T. Fukuhara, S. Sugawa, Y. Takasu, and Y. Takahashi, Tools for quantum simulation with ultracold atoms in optical lattices, Nat. Rev. Phys. 2, 411 (2020).
  * Preskill [2018] J. Preskill, Quantum computing in the NISQ era and beyond, Quantum 2, 79 (2018).
  * Clemente  _et al._ [2020] G. Clemente, M. Cardinali, C. Bonati, E. Calore, L. Cosmai, M. D’Elia, A. Gabbana, D. Rossini, F. S. Schifano, R. Tripiccione, and D. Vadacchino (QuBiPF Collaboration), Quantum computation of thermal averages in the presence of a sign problem, Phys. Rev. D 101, 074510 (2020).
  * Troyer and Wiese [2005] M. Troyer and U.-J. Wiese, Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations, Phys. Rev. Lett. 94, 170201 (2005).
  * Hangleiter  _et al._ [2020] D. Hangleiter, I. Roth, D. Nagaj, and J. Eisert, Easing the monte carlo sign problem, Science Advances 6, 10.1126/sciadv.abb8341 (2020).
  * Wan  _et al._ [2020] Z.-Q. Wan, S.-X. Zhang, and H. Yao, Mitigating sign problem by automatic differentiation (2020), arXiv:2010.01141 [cond-mat.str-el] .
  * Meng  _et al._ [2010] Z. Meng, S. Wessel, A. Muramatsu, T. Lang, and F. Assaad, Quantum spin liquid emerging in two-dimensional correlated Dirac fermions, Nature 464, 847 (2010).
  * Sorella  _et al._ [2012] S. Sorella, Y. Otsuka, and S. Yunoki, Absence of a spin liquid phase in the Hubbard model on the honeycomb lattice, Sci. Rep. 2, 992 (2012).
  * Fabrizio  _et al._ [1999] M. Fabrizio, A. O. Gogolin, and A. A. Nersesyan, From band insulator to Mott insulator in one dimension, Phys. Rev. Lett. 83, 2014 (1999).
  * Craco  _et al._ [2008] L. Craco, P. Lombardo, R. Hayn, G. Japaridze, and E. Müller-Hartmann, Electronic phase transitions in the half-filled ionic Hubbard model, Phys. Rev. B 78, 075121 (2008).
  * Garg  _et al._ [2014] A. Garg, H. Krishnamurthy, and M. Randeria, Doping a correlated band insulator: A new route to half-metallic behavior, Phys. Rev. Lett. 112, 106406 (2014).
  * Huffman and Chandrasekharan [2014] E. F. Huffman and S. Chandrasekharan, Solution to sign problems in half-filled spin-polarized electronic systems, Phys. Rev. B 89, 111101 (2014).
  * Wang  _et al._ [2014] L. Wang, P. Corboz, and M. Troyer, Fermionic quantum critical point of spinless fermions on a honeycomb lattice, New J. Phys. 16, 103008 (2014).
  * Keimer  _et al._ [2015] B. Keimer, S. A. Kivelson, M. R. Norman, S. Uchida, and J. Zaanen, From quantum matter to high-temperature superconductivity in copper oxides, Nature 518, 179 (2015).
  * Hirsch  _et al._ [1982] J. Hirsch, R. Sugar, D. Scalapino, and R. Blankenbecler, Monte Carlo simulations of one-dimensional fermion systems, Phys. Rev. B 26, 5033 (1982).
  * Ceperley and Alder [1984] D. Ceperley and B. Alder, Quantum Monte Carlo for molecules: Green’s function and nodal release, J. Chem. Phys. 81, 5833 (1984).
  * Lee and Schmidt [1992] M. A. Lee and K. E. Schmidt, Green’s function Monte Carlo, Comput. Phys. 6, 192 (1992).
  * Henelius and Sandvik [2000] P. Henelius and A. W. Sandvik, Sign problem in Monte Carlo simulations of frustrated quantum spin systems, Phys. Rev. B 62, 1102 (2000).
  * Blankenbecler  _et al._ [1981] R. Blankenbecler, D. Scalapino, and R. Sugar, Monte Carlo calculations of coupled boson-fermion systems. I, Phys. Rev. D 24, 2278 (1981).
  * White  _et al._ [1989a] S. White, D. Scalapino, R. Sugar, E. Loh, J. Gubernatis, and R. Scalettar, Numerical study of the two-dimensional Hubbard model, Phys. Rev. B 40, 506 (1989a).
  * Zhang  _et al._ [1997] S. Zhang, J. Carlson, and J. E. Gubernatis, Constrained path Monte Carlo method for fermion ground states, Phys. Rev. B 55, 7464 (1997).
  * Iazzi  _et al._ [2016] M. Iazzi, A. A. Soluyanov, and M. Troyer, Topological origin of the fermion sign problem, Phys. Rev. B 93, 115102 (2016).
  * Loh  _et al._ [1990] E. Loh, J. Gubernatis, R. Scalettar, S. White, D. Scalapino, and R. Sugar, Sign problem in the numerical simulation of many-electron systems, Phys. Rev. B 41, 9301 (1990).
  * Wu and Zhang [2005] C. Wu and S.-C. Zhang, Sufficient condition for absence of the sign problem in the fermionic quantum Monte Carlo algorithm, Phys. Rev. B 71, 155115 (2005).
  * Li  _et al._ [2016] Z.-X. Li, Y.-F. Jiang, and H. Yao, Majorana-time-reversal symmetries: A fundamental principle for sign-problem-free quantum Monte Carlo simulations, Phys. Rev. Lett. 117, 267002 (2016).
  * Chandrasekharan [2010] S. Chandrasekharan, Fermion bag approach to lattice field theories, Phys. Rev. D 82, 025007 (2010).
  * Berg  _et al._ [2012] E. Berg, M. A. Metlitski, and S. Sachdev, Sign-problem–free quantum Monte Carlo of the onset of antiferromagnetism in metals, Science 338, 1606 (2012).
  * Wang  _et al._ [2015] L. Wang, Y.-H. Liu, M. Iazzi, M. Troyer, and G. Harcos, Split orthogonal group: A guiding principle for sign-problem-free fermionic simulations, Phys. Rev. Lett. 115, 250601 (2015).
  * Li and Yao [2019] Z.-X. Li and H. Yao, Sign-problem-free fermionic quantum Monte Carlo: Developments and applications, Annu. Rev. Condens. Matter Phys. 10, 337 (2019).
  * Note [1] This is just a rough guideline; the precise onset of the SP is determined by lattice geometry, doping (chemical potential), and interaction strength. A catalog of the SP in DQMC for the single band Hubbard model in different situations is given in Ref. [59].
  * Hirsch [1983] J. Hirsch, Discrete Hubbard-Stratonovich transformation for fermion lattice models, Phys. Rev. B 28, 4059 (1983).
  * Li  _et al._ [2015] Z.-X. Li, Y.-F. Jiang, and H. Yao, Solving the fermion sign problem in quantum Monte Carlo simulations by Majorana representation, Phys. Rev. B 91, 241117 (2015).
  * Paiva  _et al._ [2005] T. Paiva, R. Scalettar, W. Zheng, R. Singh, and J. Oitmaa, Ground-state and finite-temperature signatures of quantum phase transitions in the half-filled Hubbard model on a honeycomb lattice, Phys. Rev. B 72, 085123 (2005).
  * Rieger and Young [1994] H. Rieger and A. P. Young, Zero-temperature quantum phase transition of a two-dimensional Ising spin glass, Phys. Rev. Lett. 72, 4141 (1994).
  * Kampf  _et al._ [2003] A. Kampf, M. Sekania, G. Japaridze, and P. Brune, Nature of the insulating phases in the half-filled ionic Hubbard model, Journal of Physics: Condensed Matter 15, 5895 (2003).
  * Garg  _et al._ [2006] A. Garg, H. Krishnamurthy, and M. Randeria, Can correlations drive a band insulator metallic?, Phys. Rev. Lett. 97, 046403 (2006).
  * Paris  _et al._ [2007] N. Paris, K. Bouadim, F. Hebert, G. Batrouni, and R. Scalettar, Quantum Monte Carlo study of an interaction-driven band-insulator–to–metal transition, Phys. Rev. Lett. 98, 046403 (2007).
  * Chattopadhyay  _et al._ [2019] A. Chattopadhyay, S. Bag, H. R. Krishnamurthy, and A. Garg, Phase diagram of the half-filled ionic Hubbard model in the limit of strong correlations, Phys. Rev. B 99, 155127 (2019).
  * Hesselmann and Wessel [2016] S. Hesselmann and S. Wessel, Thermal Ising transitions in the vicinity of two-dimensional quantum critical points, Phys. Rev. B 93, 155157 (2016).
  * Damascelli  _et al._ [2003] A. Damascelli, Z. Hussain, and Z.-X. Shen, Angle-resolved photoemission studies of the cuprate superconductors, Rev. Mod. Phys. 75, 473 (2003).
  * Lee  _et al._ [2006] P. A. Lee, N. Nagaosa, and X.-G. Wen, Doping a Mott insulator: Physics of high-temperature superconductivity, Rev. Mod. Phys. 78, 17 (2006).
  * Jiang and Devereaux [2019] H.-C. Jiang and T. P. Devereaux, Superconductivity in the doped Hubbard model and its interplay with next-nearest hopping t’, Science 365, 1424 (2019).
  * Huang  _et al._ [2019] E. W. Huang, R. Sheppard, B. Moritz, and T. P. Devereaux, Strange metallicity in the doped Hubbard model, Science 366, 987 (2019).
  * Randeria  _et al._ [1992] M. Randeria, N. Trivedi, A. Moreo, and R. T. Scalettar, Pairing and spin gap in the normal state of short coherence length superconductors, Phys. Rev. Lett. 69, 2001 (1992).
  * Tremblay  _et al._ [2006] A.-M. S. Tremblay, B. Kyung, and D. Sénéchal, Pseudogap and high-temperature superconductivity from weak to strong coupling. towards a quantitative theory (review article), Low Temperature Physics 32, 424 (2006).
  * Maier  _et al._ [2005a] T. A. Maier, M. Jarrell, T. C. Schulthess, P. R. C. Kent, and J. B. White, Systematic study of $d$-wave superconductivity in the 2d repulsive Hubbard model, Phys. Rev. Lett. 95, 237001 (2005a).
  * Maier  _et al._ [2016] T. A. Maier, P. Staar, V. Mishra, U. Chatterjee, J. C. Campuzano, and D. J. Scalapino, Pairing in a dry Fermi sea, Nat. Comm. 7, 11875 (2016).
  * White  _et al._ [1989b] S. R. White, D. J. Scalapino, R. L. Sugar, N. E. Bickers, and R. T. Scalettar, Attractive and repulsive pairing interaction vertices for the two-dimensional Hubbard model, Phys. Rev. B 39, 839 (1989b).
  * Scalapino [1994] D. Scalapino, Does the Hubbard model have the right stuff?, in  _Proceedings of the International School of Physics_ , edited by R. Broglia and J. Schrieffer (North-Holland, 1994).
  * Iglovikov  _et al._ [2015] V. Iglovikov, E. Khatami, and R. Scalettar, Geometry dependence of the sign problem in quantum Monte Carlo simulations, Phys. Rev. B 92, 045110 (2015).
  * [60] J. Hirsch, unpublished.
  * Wessel  _et al._ [2017] S. Wessel, B. Normand, F. Mila, and A. Honecker, Efficient Quantum Monte Carlo simulations of highly frustrated magnets: the frustrated spin-1/2 ladder, SciPost Phys. 3, 005 (2017).
  * Goetz  _et al._ [2021] A. Goetz, S. Beyl, M. Hohenadler, and F. F. Assaad, Langevin dynamics simulations of the two-dimensional Su-Schrieffer-Heeger model (2021), arXiv:2102.08899 [cond-mat.str-el] .
  * Mondaini  _et al._ [2021] R. Mondaini, S. Tarat, and R. T. Scalettar, Datasets to produce figures of the manuscript “Quantum Critical Points and the Sign Problem” (2021).
  * Bethe and Salpeter [1957] H. A. Bethe and E. E. Salpeter,  _Quantum Mechanics of One- and Two-Electron Atoms_ (Springer-Verlag, 1957).
  * Anderson [1975] J. B. Anderson, A random‐walk simulation of the Schrödinger equation: H+3, J. Chem. Phys. 63, 1499 (1975).
  * Ceperley and Alder [1980] D. Ceperley and B. Alder, Ground state of the electron gas by a stochastic method, Phys. Rev. Lett. 45, 566 (1980).
  * Negele [1986] J. W. Negele, Monte carlo studies of nuclear many-particle systems, J. Stat. Phys. 43, 991 (1986).
  * Lynn  _et al._ [2019] J. Lynn, I. Tews, S. Gandolfi, and A. Lovato, Quantum Monte Carlo methods in nuclear physics: Recent advances, Annu. Rev. Nucl. Part. Sci. 69, 279 (2019).
  * Kogut [1979] J. B. Kogut, An introduction to lattice gauge theory and spin systems, Rev. Mod. Phys. 51, 659 (1979).
  * Kogut [1983] J. B. Kogut, The lattice gauge theory approach to quantum chromodynamics, Rev. Mod. Phys. 55, 775 (1983).
  * Sugiyama and Koonin [1986] G. Sugiyama and S. E. Koonin, Auxiliary field Monte-Carlo for quantum many-body ground states, Ann. Phys. 168, 1 (1986).
  * Batrouni  _et al._ [1985] G. G. Batrouni, G. R. Katz, A. S. Kronfeld, G. P. Lepage, B. Svetitsky, and K. G. Wilson, Langevin simulations of lattice field theories, Phys. Rev. D 32, 2736 (1985).
  * Duane and Kogut [1985] S. Duane and J. B. Kogut, Hybrid stochastic differential equations applied to quantum chromodynamics, Phys. Rev. Lett. 55, 2774 (1985).
  * Gottlieb  _et al._ [1987] S. Gottlieb, W. Liu, D. Toussaint, R. L. Renken, and R. L. Sugar, Hybrid-molecular-dynamics algorithms for the numerical simulation of quantum chromodynamics, Phys. Rev. D 35, 2531 (1987).
  * Scalettar  _et al._ [1986] R. T. Scalettar, D. J. Scalapino, and R. L. Sugar, New algorithm for the numerical simulation of fermions, Phys. Rev. B 34, 7911 (1986).
  * Scalettar  _et al._ [1987] R. T. Scalettar, D. J. Scalapino, R. L. Sugar, and D. Toussaint, Hybrid molecular-dynamics algorithm for the numerical simulation of many-electron systems, Phys. Rev. B 36, 8632 (1987).
  * Davies  _et al._ [1988] C. T. H. Davies, G. G. Batrouni, G. R. Katz, A. S. Kronfeld, G. P. Lepage, K. G. Wilson, P. Rossi, and B. Svetitsky, Fourier acceleration in lattice gauge theories. I. Landau gauge fixing, Phys. Rev. D 37, 1581 (1988).
  * Buendia [1986] G. M. Buendia, Comparative study of the discrete and the continuous Hubbard-Stratonovich transformation for a one-dimensional spinless fermion model, Phys. Rev. B 33, 3519 (1986).
  * Chen and Tremblay [1992] L. Chen and A.-M. Tremblay, Determinant Monte Carlo for the Hubbard model with arbitrarily gauged auxiliary fields, Int. J. Mod. Phys. B 06, 547 (1992).
  * Assaad [2002] F. F. Assaad, Quantum Monte Carlo methods on lattices: The determinantal approach, in  _Quantum Simulations of Complex Many-Body Systems: From Theory to Algorithms, Lecture Notes NIC Series_ , Vol. 10 (2002) pp. 99–156.
  * Gubernatis  _et al._ [2016] J. Gubernatis, N. Kawashima, and P. Werner,  _Quantum Monte Carlo Methods: Algorithms for Lattice Models_ (Cambridge University Press, 2016).
  * Alhassid [2017] Y. Alhassid, Auxiliary-feld quantum Monte Carlo methods in nuclei, in  _Emergent Phenomena in Atomic Nuclei from Large-Scale Modeling: a Symmetry-Guided Perspective_ , edited by K. D. Launey (World Scientific, 2017).
  * Hao  _et al._ [2019] H. Hao, B. M. Rubenstein, and H. Shi, Auxiliary field quantum Monte Carlo for multiband Hubbard models: Controlling the sign and phase problems to capture Hund’s physics, Phys. Rev. B 99, 235142 (2019).
  * He  _et al._ [2019] Y.-Y. He, M. Qin, H. Shi, Z.-Y. Lu, and S. Zhang, Finite-temperature auxiliary-field quantum Monte Carlo: Self-consistent constraint and systematic approach to low temperatures, Phys. Rev. B 99, 045108 (2019).
  * Hirsch [1985] J. E. Hirsch, Two-dimensional Hubbard model: Numerical simulation study, Phys. Rev. B 31, 4403 (1985).
  * Alford  _et al._ [1999] M. Alford, A. Kapustin, and F. Wilczek, Imaginary chemical potential and finite fermion density on the lattice, Phys. Rev. D 59, 054502 (1999).
  * Toulouse  _et al._ [2016] J. Toulouse, R. Assaraf, and C. J. Umrigar, Introduction to the variational and diffusion Monte Carlo methods, in  _Electron Correlation in Molecules – ab initio Beyond Gaussian Quantum Chemistry_, Advances in Quantum Chemistry, Vol. 73, edited by P. E. Hoggan and T. Ozdogan (Academic Press, 2016) pp. 285 – 314\.
  * de Forcrand and Philipsen [2002] P. de Forcrand and O. Philipsen, The QCD phase diagram for small densities from imaginary chemical potential, Nucl. Phys. B. 642, 290 (2002).
  * Gavai and Gupta [2003] R. V. Gavai and S. Gupta, Pressure and nonlinear susceptibilities in QCD at finite chemical potentials, Phys. Rev. D 68, 034506 (2003).
  * Allton  _et al._ [2002] C. Allton, S. Ejiri, S. Hands, O. Kaczmarek, F. Karsch, E. Laermann, C. Schmidt, and L. Scorzato, QCD thermal phase transition in the presence of a small chemical potential, Phys. Rev. D 66, 074507 (2002).
  * Adami and Koonin [2001] C. Adami and S. E. Koonin, Complex Langevin equation and the many-fermion problem, Phys. Rev. C 63, 034319 (2001).
  * Berger  _et al._ [2019] C. E. Berger, L. Rammelmüller, A. C. Loheac, F. Ehmann, J. Braun, and J. E. Drut, Complex Langevin and other approaches to the sign problem in quantum many-body physics (2019), arXiv:1907.10183 [cond-mat.quant-gas] .
  * Witten [2010] E. Witten, A new look at the path integral of quantum mechanics (2010), arXiv:1009.6032 [hep-th] .
  * Cristoforetti  _et al._ [2012] M. Cristoforetti, F. Di Renzo, and L. Scorzato (AuroraScience Collaboration), New approach to the sign problem in quantum field theories: High density QCD on a Lefschetz thimble, Phys. Rev. D 86, 074506 (2012).
  * Bañuls and Cichy [2019] M. C. Bañuls and K. Cichy, Review on novel methods for lattice gauge theories (2019), arXiv:1910.00257 [hep-lat] .
  * Ortiz  _et al._ [1993] G. Ortiz, D. Ceperley, and R. Martin, New stochastic method for systems with broken time-reversal symmetry: 2D fermions in a magnetic field, Phys. Rev. Lett. 71, 2777 (1993).
  * Chandrasekharan and Wiese [1999] S. Chandrasekharan and U.-J. Wiese, Meron-cluster solution of fermion sign problems, Phys. Rev. Lett. 83, 3116 (1999).
  * Bergkvist  _et al._ [2003] S. Bergkvist, P. Henelius, and A. Rosengren, Reduction of the sign problem using the meron-cluster approach, Phys. Rev. E 68, 016122 (2003).
  * Nyfeler  _et al._ [2008] M. Nyfeler, F.-J. Jiang, F. Kämpfer, and U.-J. Wiese, Nested cluster algorithm for frustrated quantum antiferromagnets, Phys. Rev. Lett. 100, 247206 (2008).
  * Nomura  _et al._ [2014] Y. Nomura, S. Sakai, and R. Arita, Multiorbital cluster dynamical mean-field theory with an improved continuous-time quantum Monte Carlo algorithm, Phys. Rev. B 89, 195146 (2014).
  * Mukherjee and Cristoforetti [2014] A. Mukherjee and M. Cristoforetti, Lefschetz thimble Monte Carlo for many-body theories: A Hubbard model study, Phys. Rev. B 90, 035134 (2014).
  * Shinaoka  _et al._ [2015] H. Shinaoka, Y. Nomura, S. Biermann, M. Troyer, and P. Werner, Negative sign problem in continuous-time quantum Monte Carlo: Optimal choice of single-particle basis for impurity problems, Phys. Rev. B 92, 195126 (2015).
  * Kaul [2015] R. K. Kaul, Marshall-positive $\mathrm{SU}(N)$ quantum spin systems and classical loop models: A practical strategy to design sign-problem-free spin hamiltonians, Phys. Rev. B 91, 054413 (2015).
  * Fukuma  _et al._ [2019] M. Fukuma, N. Matsumoto, and N. Umeda, Applying the tempered Lefschetz thimble method to the Hubbard model away from half filling, Phys. Rev. D 100, 114510 (2019).
  * Ulybyshev  _et al._ [2020] M. Ulybyshev, C. Winterowd, and S. Zafeiropoulos, Lefschetz thimbles decomposition for the Hubbard model on the hexagonal lattice, Phys. Rev. D 101, 014508 (2020).
  * Kim  _et al._ [2020] A. J. Kim, P. Werner, and R. Valentí, Alleviating the sign problem in quantum Monte Carlo simulations of spin-orbit-coupled multiorbital Hubbard models, Phys. Rev. B 101, 045108 (2020).
  * Wiringa  _et al._ [2000] R. Wiringa, S. C. Pieper, J. Carlson, and V. Pandharipande, Quantum Monte Carlo calculations of $A=8$ nuclei, Phys. Rev. C 62, 014001 (2000).
  * Gandolfi  _et al._ [2020] S. Gandolfi, D. Lonardoni, A. Lovato, and M. Piarulli, Atomic nuclei from quantum Monte Carlo calculations with chiral EFT interactions, Frontiers in Physics 8, 117 (2020).
  * Umrigar  _et al._ [2007] C. Umrigar, J. Toulouse, C. Filippi, S. Sorella, and R. Hennig, Alleviation of the fermion-sign problem by optimization of many-body wave functions, Phys. Rev. Lett. 98, 110201 (2007).
  * Shi  _et al._ [2014] H. Shi, C. A. Jiménez-Hoyos, R. Rodríguez-Guzmán, G. E. Scuseria, and S. Zhang, Symmetry-projected wave functions in quantum Monte Carlo calculations, Phys. Rev. B 89, 125129 (2014).
  * Roggero and Pederiva [2018] A. Roggero and F. Pederiva, Extension of the configuration interaction Monte Carlo method to atoms and molecules, in  _Novel Electronic Structure Theory: General Innovations and Strongly Correlated Systems_, edited by P. Hoggan (Elsevier, 2018) Chap. 13, pp. 241–253.
  * Rothstein  _et al._ [2019] S. Rothstein, E. Ospadov, and C. Bruzzese, Introduction to fixed-node quantum Monte Carlo, in  _Mathematical Physics in Theoretical Chemistry_, edited by S. Blinder and J. House (Elsevier, 2019) Chap. 6, pp. 189–217.
  * Bloch [2005] I. Bloch, Ultracold quantum gases in optical lattices, Nat. Phys. 1, 23 (2005).
  * Tarruell and Sanchez-Palencia [2018] L. Tarruell and L. Sanchez-Palencia, Quantum simulation of the hubbard model with ultracold fermions in optical lattices, Comptes Rendus Physique 19, 365 (2018), quantum simulation / Simulation quantique.
  * Ortiz  _et al._ [2001] G. Ortiz, J. Gubernatis, E. Knill, and R. Laflamme, Quantum algorithms for fermionic simulations, Phys. Rev. A 64, 022319 (2001).
  * Brown  _et al._ [2010] K. Brown, W. Munro, and V. Kendon, Using quantum computers for quantum simulation, Entropy 12, 2268 (2010).
  * Steudtner and Wehner [2018] M. Steudtner and S. Wehner, Fermion-to-qubit mappings with varying resource requirements for quantum simulation, New J. Phys. 20, 063010 (2018).
  * Google AI Quantum and collaborators [2020] Google AI Quantum and collaborators, Observation of separated dynamics of charge and spin in the Fermi-Hubbard model (2020), arXiv:2010.07965 [quant-ph] .
  * Kawashima and Harada [2004] N. Kawashima and K. Harada, Recent developments of world-line Monte Carlo methods, J. Phys. Soc. Jpn. 73, 1379 (2004).
  * Reynolds  _et al._ [1990] P. J. Reynolds, J. Tobochnik, and H. Gould, Diffusion quantum Monte Carlo, Comput. Phys. 4, 662 (1990).
  * Georges  _et al._ [1996] A. Georges, G. Kotliar, W. Krauth, and M. J. Rozenberg, Dynamical mean-field theory of strongly correlated fermion systems and the limit of infinite dimensions, Rev. Mod. Phys. 68, 13 (1996).
  * Beard and Wiese [1996] B. Beard and U.-J. Wiese, Simulations of discrete quantum systems in continuous Euclidean time, Phys. Rev. Lett. 77, 5130 (1996).
  * Hettler  _et al._ [2000] M. Hettler, M. Mukherjee, M. Jarrell, and H. Krishnamurthy, Dynamical cluster approximation: Nonlocal dynamics of correlated electron systems, Phys. Rev. B 61, 12739 (2000).
  * Kotliar  _et al._ [2001] G. Kotliar, S. Y. Savrasov, G. Pálsson, and G. Biroli, Cellular dynamical mean field approach to strongly correlated systems, Phys. Rev. Lett. 87, 186401 (2001).
  * Rubtsov  _et al._ [2005] A. Rubtsov, V. Savkin, and A. Lichtenstein, Continuous-time quantum Monte Carlo method for fermions, Phys. Rev. B 72, 035122 (2005).
  * Maier  _et al._ [2005b] T. Maier, M. Jarrell, T. Pruschke, and M. H. Hettler, Quantum cluster theories, Rev. Mod. Phys. 77, 1027 (2005b).
  * Kyung  _et al._ [2006] B. Kyung, G. Kotliar, and A.-M. S. Tremblay, Quantum Monte Carlo study of strongly correlated electrons: Cellular dynamical mean-field theory, Phys. Rev. B 73, 205106 (2006).
  * Gull  _et al._ [2008] E. Gull, P. Werner, O. Parcollet, and M. Troyer, Continuous-time auxiliary-field Monte Carlo for quantum impurity models, EPL (Europhysics Letters) 82, 57003 (2008).
  * Gull  _et al._ [2011] E. Gull, A. J. Millis, A. I. Lichtenstein, A. N. Rubtsov, M. Troyer, and P. Werner, Continuous-time Monte Carlo methods for quantum impurity models, Rev. Mod. Phys. 83, 349 (2011).
  * Prokofév  _et al._ [1996] N. Prokofév, B. Svistunov, and I. Tupitsyn, Exact quantum Monte Carlo process for the statistics of discrete systems, JETP Lett. 64, 911 (1996)).
  * Houcke  _et al._ [2010] K. V. Houcke, E. Kozika, N. Prokofév, and B. Svistunov, Diagrammatic Monte Carlo, Physics Procedia 6, 95 (2010).
  * Rossi [2017] R. Rossi, Determinant diagrammatic Monte Carlo algorithm in the thermodynamic limit, Phys. Rev. Lett. 119, 045701 (2017).
  * Rohringer  _et al._ [2018] G. Rohringer, H. Hafermann, A. Toschi, A. Katanin, A. Antipov, M. Katsnelson, A. Lichtenstein, A. Rubtsov, and K. Held, Diagrammatic routes to nonlocal correlations beyond dynamical mean field theory, Rev. Mod. Phys. 90, 025003 (2018).
  * Hirsch [1986] J. E. Hirsch, Connection between world-line and determinantal functional-integral formulations of the Hubbard model, Phys. Rev. B 34, 3216 (1986).
  * Batrouni and Scalettar [1990] G. G. Batrouni and R. T. Scalettar, Anomalous decouplings and the fermion sign problem, Phys. Rev. B 42, 2282 (1990).
  * Georges and Kotliar [1992] A. Georges and G. Kotliar, Hubbard model in infinite dimensions, Phys. Rev. B 45, 6479 (1992).
  * Jarrell [1992] M. Jarrell, Hubbard model in infinite dimensions: A quantum Monte Carlo study, Phys. Rev. Lett. 69, 168 (1992).
  * Jarrell  _et al._ [2001] M. Jarrell, T. Maier, C. Huscroft, and S. Moukouri, Quantum Monte Carlo algorithm for nonlocal corrections to the dynamical mean-field approximation, Phys. Rev. B 64, 195130 (2001).
  * Hohenadler  _et al._ [2012] M. Hohenadler, Z. Y. Meng, T. C. Lang, S. Wessel, A. Muramatsu, and F. F. Assaad, Quantum phase transitions in the Kane-Mele-Hubbard model, Phys. Rev. B 85, 115132 (2012).
  * Bercx  _et al._ [2014] M. Bercx, M. Hohenadler, and F. F. Assaad, Kane-Mele-Hubbard model on the $\pi$-flux honeycomb lattice, Phys. Rev. B 90, 075140 (2014).
  * Parisen Toldin  _et al._ [2015] F. Parisen Toldin, M. Hohenadler, F. F. Assaad, and I. F. Herbut, Fermionic quantum criticality in honeycomb and $\pi$-flux Hubbard models: Finite-size scaling of renormalization-group-invariant observables from quantum Monte Carlo, Phys. Rev. B 91, 165108 (2015).
  * Imriška  _et al._ [2016] J. Imriška, L. Wang, and M. Troyer, First-order topological phase transition of the Haldane-Hubbard model, Phys. Rev. B 94, 035109 (2016).
  * Vanhala  _et al._ [2016] T. I. Vanhala, T. Siro, L. Liang, M. Troyer, A. Harju, and P. Törmä, Topological phase transitions in the repulsively interacting Haldane-Hubbard model, Phys. Rev. Lett. 116, 225305 (2016).
  * Shao  _et al._ [2021] C. Shao, E. V. Castro, S. Hu, and R. Mondaini, Interplay of local order and topology in the extended Haldane-Hubbard model, Phys. Rev. B 103, 035125 (2021).
  * Huscroft and Scalettar [1997] C. Huscroft and R. Scalettar, Effect of disorder on charge-density wave and superconducting order in the half-filled attractive Hubbard model, Phys. Rev. B 55, 1185 (1997).
  * Denteneer  _et al._ [2001] P. J. H. Denteneer, R. T. Scalettar, and N. Trivedi, Particle-hole symmetry and the effect of disorder on the Mott-Hubbard insulator, Phys. Rev. Lett. 87, 146401 (2001).
  * Denteneer  _et al._ [1999] P. J. H. Denteneer, R. T. Scalettar, and N. Trivedi, Conducting phase in the two-dimensional disordered Hubbard model, Phys. Rev. Lett. 83, 4610 (1999).
  * Denteneer and Scalettar [2003] P. J. H. Denteneer and R. T. Scalettar, Interacting electrons in a two-dimensional disordered environment: Effect of a Zeeman magnetic field, Phys. Rev. Lett. 90, 246401 (2003).
  * Sorella and Tosatti [1992] S. Sorella and E. Tosatti, Semi-metal-insulator transition of the Hubbard model in the honeycomb lattice, Europhys. Lett. 19, 699 (1992).
  * Herbut [2006] I. F. Herbut, Interactions and phase transitions on graphene’s honeycomb lattice, Phys. Rev. Lett. 97, 146401 (2006).
  * Giuliani and Mastropietro [2009] A. Giuliani and V. Mastropietro, The two-dimensional Hubbard model on the honeycomb lattice, Commun. Math. Phys. 293, 301 (2009).
  * Ma  _et al._ [2011] T. Ma, F. Hu, Z. Huang, and H.-Q. Lin, Magnetic correlation in the Hubbard model on a honeycomb lattice, Comput. Phys. Commun. 182, 52 (2011), computer Physics Communications Special Edition for Conference on Computational Physics Kaohsiung, Taiwan, Dec 15-19, 2009\.
  * Clark  _et al._ [2011] B. Clark, D. Abanin, and S. Sondhi, Nature of the spin liquid state of the Hubbard model on a honeycomb lattice, Phys. Rev. Lett. 107, 087204 (2011).
  * Raczkowski  _et al._ [2020] M. Raczkowski, R. Peters, T. T. Phùng, N. Takemori, F. F. Assaad, A. Honecker, and J. Vahedi, Hubbard model on the honeycomb lattice: From static and dynamical mean-field theories to lattice quantum Monte Carlo simulations, Phys. Rev. B 101, 125103 (2020).
  * Assaad and Herbut [2013] F. F. Assaad and I. F. Herbut, Pinning the order: The nature of quantum criticality in the Hubbard model on honeycomb lattice, Phys. Rev. X 3, 031010 (2013).
  * Bouadim  _et al._ [2007] K. Bouadim, N. Paris, F. Hébert, G. Batrouni, and R. Scalettar, Metallic phase in the two-dimensional ionic Hubbard model, Phys. Rev. B 76, 085112 (2007).
  * Manmana  _et al._ [2004] S. Manmana, V. Meden, R. Noack, and K. Schönhammer, Quantum critical behavior of the one-dimensional ionic Hubbard model, Phys. Rev. B 70, 155115 (2004).
  * Bag  _et al._ [2015] S. Bag, A. Garg, and H. Krishnamurthy, Phase diagram of the half-filled ionic Hubbard model, Phys. Rev. B 91, 235108 (2015).
  * Fye [1986] R. Fye, New results on Trotter-like approximations, Phys. Rev. B 33, 6271 (1986).
  * Hirayama  _et al._ [2018] M. Hirayama, Y. Yamaji, T. Misawa, and M. Imada, Ab initio effective Hamiltonians for cuprate superconductors, Phys. Rev. B 98, 134501 (2018).
  * Hirayama  _et al._ [2019] M. Hirayama, T. Misawa, T. Ohgoe, Y. Yamaji, and M. Imada, Effective Hamiltonian for cuprate superconductors derived from multiscale ab initio scheme with level renormalization, Phys. Rev. B 99, 245155 (2019).
  * Jarrell and Gubernatis [1996] M. Jarrell and J. Gubernatis, Bayesian inference and the analytic continuation of imaginary-time quantum Monte Carlo data, Phys. Rep. 269, 133 (1996).
  * Trivedi and Randeria [1995] N. Trivedi and M. Randeria, Deviations from Fermi-liquid behavior above ${T}_{c}$ in 2d short coherence length superconductors, Phys. Rev. Lett. 75, 312 (1995).
  * Wu  _et al._ [2018] W. Wu, M. S. Scheurer, S. Chatterjee, S. Sachdev, A. Georges, and M. Ferrero, Pseudogap and Fermi-surface topology in the two-dimensional Hubbard model, Phys. Rev. X 8, 021048 (2018).
  * Chen  _et al._ [2012] K.-S. Chen, Z. Y. Meng, T. Pruschke, J. Moreno, and M. Jarrell, Lifshitz transition in the two-dimensional Hubbard model, Phys. Rev. B 86, 165136 (2012).
  * Dalla Piazza  _et al._ [2012] B. Dalla Piazza, M. Mourigal, M. Guarise, H. Berger, T. Schmitt, K. J. Zhou, M. Grioni, and H. M. Rønnow, Unified one-band Hubbard model for magnetic and electronic spectra of the parent compounds of cuprate superconductors, Phys. Rev. B 85, 100508 (2012).

Supplementary Materials:
Quantum Critical Points and the Sign Problem

In these Supplementary Materials we provide some additional context and
history of the sign problem. We also show the behavior of other observables
across the transitions described in the main body of the paper, as well as
exploring more carefully finite spatial size and Trotter effects in the
evolution of $\langle{\cal S}\rangle$.

###### Contents

  1. I The Role of Quantum Simulations
  2. II Determinant Quantum Monte Carlo
  3. III Physical Observables
  4. IV Sign Problem: General Importance
  5. V The sign problem in other QMC algorithms
  6. VI The sign problem in other Hamiltonians
  7. VII More details on the Spinful Hubbard Model on a Honeycomb Lattice (main text, Sec. I)
  8. VIII More details on the Ionic Hubbard Hamiltonian (main text, Sec. II)
  9. IX More details on Spinless Honeycomb Hubbard (main text, Sec. III)
  10. X More details for the homogeneous Hubbard model on the square lattice (main text, Sec. IV)

##  I The Role of Quantum Simulations

The motivation for numerical solutions to the quantum many body problem is the
intractability of analytic solutions except in limited circumstances. Indeed,
the extension of the analytic solution of the single electron Hydrogen atom to
two electrons is already problematic, as emphasized in the classic text of
Bethe and Salpeter [64]. As a consequence, quantum simulations approaches
appeared in chemistry [65, 25], condensed matter [66, 24], nuclear [67, 68],
and high energy physics [69, 28, 70] almost as soon as computers became
reasonably available for scientific work.

There is considerable methodological linkage in quantum simulation between
these fields. For example, in the case of the DQMC method used in this work,
the problem of treating the accumulation of round off errors at low
temperatures was first developed in the nuclear physics community [71] before
being adapted to condensed matter. Likewise, the linear scaling methods of
lattice gauge theory (LGT) [72, 73, 74] were soon adapted to condensed matter
physics [75, 76], albeit with only limited success owing to the extreme
anisotropic (non-relativistic) nature of the condensed matter space-imaginary
time lattices. Many of the algorithms, like Fourier Acceleration, which are
crucial to LGT, were first implemented and tested for classical spin models
[77].

##  II Determinant Quantum Monte Carlo

The DQMC method is a specific type of AFQMC [28, 78, 29, 79, 80, 81, 82, 83,
84]. In DQMC, the partition function ${\cal Z}$ is expressed as a path
integral and the Trotter approximation is used to isolate the quartic terms,

$\displaystyle{\cal Z}={\rm Tr}\,e^{-\beta\hat{H}}={\rm
Tr}\,[e^{-\Delta\tau\hat{H}}]^{L_{\tau}}\sim{\rm
Tr}\,[e^{-\Delta\tau\hat{H}_{t}}e^{-\Delta\tau\hat{H}_{U}}]^{L_{\tau}}\,,$
(S1)

where $\hat{H}_{t}$ includes the hopping and chemical potential (together with
all other bilinear terms in the fermionic operators), and $\hat{H}_{U}$ the
on-site interactions, in the Hubbard Hamiltonian of Eq. (1). The latter are
then decomposed via,

$\displaystyle e^{-\Delta\tau
U(n_{i\uparrow}-\frac{1}{2})(n_{i\downarrow}-\frac{1}{2})}=\frac{1}{2}e^{-U\Delta\tau/4}\sum_{s_{i}=\pm
1}e^{\lambda s_{i}(n_{i\uparrow}-n_{i\downarrow})}\,,$ (S2)

where ${\rm cosh}\,\lambda=e^{U\Delta\tau/2}$. A Hubbard-Stratonovich variable
(bosonic field) $s_{i}$ must be introduced at each spatial site $i$ and for
each imaginary time slice $U_{\Delta\tau}$. The prefactor
$\frac{1}{2}e^{-U\Delta\tau/4}$ is an irrelevant constant which may be
dropped.

The key observation is that the right hand side of Eq. (S2) is now quadratic
in the fermions, so that the partition function ${\cal Z}$ is a trace over a
product of quadratic forms of fermionic operators:

$\displaystyle{\cal Z}=\sum_{\\{s_{i\tau}\\}}{\rm
Tr_{\uparrow}}\,[e^{\vec{c}^{\,\dagger}_{\uparrow}K\vec{c}^{\phantom{\dagger}}_{\uparrow}}e^{\vec{c}^{\,\dagger}_{\uparrow}P^{1}\vec{c}^{\phantom{\dagger}}_{\uparrow}}\cdots
e^{\vec{c}^{\,\dagger}_{\uparrow}K\vec{c}^{\phantom{\dagger}}_{\uparrow}}e^{\vec{c}^{\,\dagger}_{\uparrow}P^{L}_{\tau}\vec{c}^{\phantom{\dagger}}_{\uparrow}}\,]\,\,\,{\rm
Tr_{\downarrow}}\,[e^{\vec{c}^{\,\dagger}_{\downarrow}K\vec{c}^{\phantom{\dagger}}_{\downarrow}}e^{-\vec{c}^{\,\dagger}_{\downarrow}P^{1}\vec{c}^{\phantom{\dagger}}_{\downarrow}}\cdots
e^{\vec{c}^{\,\dagger}_{\downarrow}K\vec{c}^{\phantom{\dagger}}_{\downarrow}}e^{-\vec{c}^{\,\dagger}_{\downarrow}P^{L}_{\tau}\vec{c}^{\phantom{\dagger}}_{\downarrow}}\,]\,,$
(S3)

with $\vec{c}^{\,\dagger}_{\sigma}=(\,c^{\,\dagger}_{\sigma
1}\,c^{\,\dagger}_{\sigma 2}\cdots\,c^{\,\dagger}_{\sigma N}\,)^{T}$. The
matrix $K$ is the same for all time slices and contains $\mu\Delta\tau$ along
its diagonal and $t\Delta\tau$ for sites connected by the hopping. (In the
case of the ionic Hubbard model, the staggered site energy term also appears
along the diagonal.) The matrices $P^{\tau}$ are diagonal, with
$P^{\tau}_{ii}=\lambda\sigma s_{i\tau}$ ($\sigma=\pm 1$ for $\uparrow$ and
$\downarrow$). All matrices have dimension equal to the number of spatial
lattice sites $N$.

The trace of a quadratic form such as Eq. (S3) can be done analytically [28,
29, 79, 80, 81, 82, 83, 84], resulting in

$\displaystyle{\cal Z}=\sum_{\\{s_{i\tau}\\}}{\rm det}[I+e^{K}e^{P^{1}}\cdots
e^{K}e^{P^{L_{\tau}}}]\,\,{\rm det}[I+e^{K}e^{-P^{1}}\cdots
e^{K}e^{-P^{L_{\tau}}}]\,.$ (S4)

The expression for ${\cal Z}$ of Eq. (S4) contains no quantum operators, just
the matrices $K,\\{P^{\tau}\\}$ of the quadratic forms. Its calculation is
thereby reduced to a classical Monte Carlo problem in which the sum over
$\\{s_{i\tau}\\}$ must be done stochastically with a weight equal to the
product of the two determinants. That these might become negative is the
origin of the SP in DQMC.

Besides this spinful case, we have also investigated interacting spinless
fermions. The problem formulation in QMC simulations is almost identical to
that of the spinful case, but now the decoupling of the interactions $V$ on
each nearest-neighbor bond $\langle i,j\rangle$ reads

$\displaystyle e^{-\Delta\tau
V(n_{i}-\frac{1}{2})(n_{j}-\frac{1}{2})}=\frac{1}{2}e^{-V\Delta\tau/4}\sum_{s_{ij}=\pm
1}e^{\lambda s_{ij}(n_{i}-n_{j})}\,,$ (S5)

where ${\rm cosh}\,\lambda=e^{V\Delta\tau/2}$. The Hubbard-Stratonovich
variable $s$ now lives on the bonds, and its total number for the rhombus-
shaped space-time lattices used here is $3L^{2}L_{\tau}$. After a similar
procedure for tracing out the fermions, one ends up with

$\displaystyle{\cal Z}=\sum_{\\{s_{ij,\tau}\\}}{\rm
det}[I+e^{K}e^{P^{1}}\cdots e^{K}e^{P^{L_{\tau}}}],$ (S6)

where the elements of the diagonal matrix $P^{\tau}$ are
$P_{ii}^{\tau}=(-1)^{i}\lambda\sum_{j}s_{ij,\tau}$. A major difference from
the spinful case is that the protection that the sign of the determinants of
the matrices for up and down spin channels display in bipartite lattices by
getting locked together [85, 31] is no longer present. This can generically
give rise to an even more detrimental SP, yet it allows us to systematically
locate the QCP of Eq. (2) with a large accuracy.

##  III Physical Observables

The central object in the QMC simulations is the Green’s function $\textbf{\rm
G}^{\sigma}$ whose matrix elements are
$G_{ij}^{\sigma}(\tau^{\prime},\tau)=\langle
c_{i\sigma}^{\phantom{\dagger}}(\tau^{\prime})c_{j\sigma}^{\dagger}(\tau)\rangle$.
By using Wick contractions and the fermionic anti-commutation relations one
can define all quantities used in the main text. These are the double
occupancy,

$\langle n_{\uparrow\downarrow}\rangle=\langle
n_{\uparrow}n_{\downarrow}\rangle,$ (S7)

the static susceptibility

$\chi(\textbf{q})=\frac{\beta}{N}\sum_{i,j}e^{{\rm
i}\textbf{q}\cdot(\textbf{R}_{i}-\textbf{R}_{j})}\langle(n_{i,\uparrow}-n_{i,\downarrow})(n_{j,\uparrow}-n_{j,\downarrow})\rangle,$
(S8)

and the pair-susceptibility

$P_{\alpha}=\int_{0}^{\beta}d\tau\langle\Delta_{\alpha}^{\phantom{\dagger}}(\tau)\Delta_{\alpha}^{\dagger}(0)\rangle,$
(S9)

with the momentum-dependent pair operator given by

$\Delta_{\alpha}^{\dagger}=\frac{1}{N}\sum_{\textbf{k}}f_{\alpha}(\textbf{k})\,c_{\textbf{k}\uparrow}^{\dagger}c_{-\textbf{k}\downarrow}^{\dagger}.$
(S10)

The form factors $f_{\alpha}(\textbf{k})$ describe the various symmetry
channels investigated:

$f_{d}(\textbf{k})=\cos k_{x}-\cos k_{y};\ \ f_{s^{*}}(\textbf{k})=\cos
k_{x}+\cos k_{y};\ \ f_{s}(\textbf{k})=1,$ (S11)

for $d$-wave, extended $s$-wave, and $s$-wave pairings, respectively. In all
data presented, we subtract the uncorrelated (non-vertex) contribution,
$P_{\alpha}^{\rm nv}$, in which pairs of fermionic operators are first
averaged before taking the product, i.e., terms in Eq. (S9) such as $\langle
c_{i\downarrow}^{\dagger}(\tau)c_{j\downarrow}^{\phantom{\dagger}}(0)c_{l\downarrow}^{\dagger}(\tau)c_{m\downarrow}^{\phantom{\dagger}}(0)\rangle$
get replaced by their decoupled contributions $\langle
c_{i\downarrow}^{\dagger}(\tau)c_{j\downarrow}^{\phantom{\dagger}}(0)\rangle\,\langle
c_{l\downarrow}^{\dagger}(\tau)c_{m\downarrow}^{\phantom{\dagger}}(0)\rangle$.

Other quantities used exclusively in this supplemental material are introduced
in the corresponding sections.

##  IV Sign Problem: General Importance

In lattice gauge theory, the SP is triggered by a non-zero chemical potential
$\mu$. Attempts to solve, or reduce, the SP include analytic continuation from
complex to real chemical potentials $\mu$ [86, 87], Taylor expansion about
zero $\mu$ [88, 89], re-weighting approaches [90], complex Langevin methods
[91, 92], and Lefshetz thimble techniques [93, 94]. For a review of the SP in
LGT, see Ref. [95]. A similar litany of papers, ideas, and new methods
characterizing, ameliorating, or solving the SP can be found in the condensed
matter [32, 96, 30, 97, 27, 98, 13, 99, 100, 101, 102, 103, 59, 84, 104, 105,
106], nuclear physics [107, 82, 68, 108], and quantum chemistry [109, 110,
111, 112] communities. These approaches differ in detail, depending on whether
they are addressing the SP in real space versus lattice models, quantum spin
versus itinerant fermion, etc.

One of the dominant themes in atomic and molecular (AMO) physics over the last
decade has been the possibility that ultracold atoms in an optical lattice
might serve as emulators of fundamental models of condensed matter physics
[113, 8, 9, 114, 10]. The initial motivation was the possibility that
simplified model Hamiltonians could be more precisely realized in the AMO
context than in the solid state, where materials ‘complications’ are
unavoidable and often significant, if not dominant. However, it was quickly
understood that an equally important advantage was that, because of the SP,
the solution of these simplified models was possible only at temperatures
which were well above those needed to access phenomena like $d$-wave
superconductivity. Thus it is fair to say that the SP has been a significant
driver of the enormous efforts and progress in this domain of AMO physics.

A similar theme is present in quantum computing [115, 116, 11, 12], which
promises the general possibility of solving problems much more rapidly
(‘quantum supremacy’) than with a classical computer. The exponential scaling
time of solutions of model Hamiltonians in the presence of the SP offers one
of the most significant targets for such endeavors [117, 118].

##  V The sign problem in other QMC algorithms

In exploring the linkage between the SP and critical properties, we have
focused exclusively on DQMC. As noted in the previous discussion, the SP
occurs also in a plethora of QMC methods: world-line quantum Monte Carlo
(WLQMC) [119], Greens Function (Diffusion) Monte Carlo (GFMC) [120], in
dynamical mean field theory (DMFT) and its cluster extensions (including
continuous time approaches) [121, 122, 123, 124, 125, 126, 127, 128, 129], and
in diagrammatic QMC [130, 131, 132, 133]. It would be interesting to explore
these situations as well, checking the direct correlation between the SP and
regimes of quantum critical behavior. Regarding WLQMC, it is known that the
onset of the sign problem is at much higher temperature than in DQMC, and
occurs due to particle exchange in the world-lines. Indeed, this provides one
of the earliest examples of the dependence of the sign problem on the
algorithm used. It seems probable that the restriction of WLQMC to only very
high temperatures ($T/W\gtrsim 1/5$ is quite typical) might preclude the
possibility of an association of the sign problem with interesting low
temperature correlations and transitions. It is worth noticing that an attempt
to reconcile WLQMC and DQMC was put forward by introducing more generic
Hubbard-Stratonovich transformations [134]; it has been further argued that
the SP in WLQMC has two origins: one from the fact that Slater determinants
are anti-symmetric sums of world-line configurations and another intrinsic,
akin to the one in DQMC, that has been claimed having topological origin [31].
In the same way, alternative choices of Hubbard-Stratonovich transformations
in DQMC [135, 79] significantly worsen the sign problem. DMFT [136, 137, 121],
on the other hand, is at the opposite end of the spectrum, with a sign problem
which is greatly reduced relative to that of DQMC. Unfortunately, its cluster
extensions, using QMC as the cluster solver, exhibit an increasingly serious
SP at low enough temperatures as the number of points in the momentum grid
increases [138, 126, 127].

Figure S1: Local observables in the vicinity of the quantum critical point on
the SU(2) honeycomb Hubbard model. The derivative of the double occupancy (A)
and the kinetic energy (B) at $T/t=1/20$ when approaching the quantum critical
point at $\mu\to 0$ and $U_{c}\simeq 3.85t$. As in the main text for other
models, the noisy data at large chemical potentials denotes the regime of
small $\langle{\cal S}\rangle$ with a vanishing signal-to-noise ratio. (C) and
(D) display the same quantities when approaching $T/t\to 0$, with a small
chemical potential $\mu/t=0.1$. As in the $T=0$ results of Ref. [16], the
derivative of the kinetic energy displays a peak within the AFMI phase. Our
data show this persists to finite temperatures. The lattice size used is
$L=9$, and all data are averaged among 20 independent runs.

We finish by noting that while we have argued that when a QCP is present, the
SP provides quantitative information about its location, the converse is not
necessarily true: a SP can exist even in the absence of a QCP. In particular,
in WLQMC, free fermions have a SP in $D>1$ without possessing any sort of
phase transition. As noted above, DQMC is SP free when the interactions
vanish, so this simple counter-example is not present in that algorithm.

##  VI The sign problem in other Hamiltonians

In our work, the spinless fermion Hamiltonian on a honeycomb lattice offered a
particularly concrete case where a sign problem free approach allows a
detailed study of quantum critical behavior. We exploited this as a way to
make a very quantitative test of the connection of the SP to the location of
the QCP. In addition to exploring other algorithms, a promising further line
of inquiry is to turn on a chemical potential in other ‘sign problem free’
models [35, 36, 37, 34, 38]. The Kane-Mele-Hubbard model would be especially
interesting since it presents a framework to understand the transition from
topological phases (quantum spin Hall insulator) towards a (topologically
trivial) Mott insulator with antiferromagnetic order [139, 140, 141]. The
Hubbard-Stratonovich transformation is slightly more complicated, and in fact
a ‘phase problem’ appears instead. In exploring this competition between
ordered and topological phases, the study of the Haldane-Hubbard model
presents as a challenging case, since due to the absence of time-reversal
symmetry, it gives rise to a severe SP in the simulations [142]. Whether
similar analysis as conducted here can help in locating the QCP associated to
a topological transition in system sizes exceeding the ones amenable to ED
[143, 144] is yet an open question left for future studies.

A further possibility for future work includes situations where disorder
drives a quantum phase transition [145]. This is of particular interest
because different types of disorder can either possess particle-hole symmetry
or not [146], and this dichotomy is known to be linked both to the presence of
the sign problem as well as to the occurrence of metal to insulator
transitions [147, 148]. Thus disordered systems might provide an especially
rich arena to explore the connection between the SP and the underlying physics
of the Hamiltonian.

##  VII More details on the Spinful Hubbard Model on a Honeycomb Lattice (main
text, Sec. I)

### Energy and Double Occupation.—

The quantum critical point separating the paramagnetic semimetal and the
antiferromagnetic insulator (AFMI) phases of the honeycomb Hubbard hamiltonian
has been characterized using observables ranging from the magnetic structure
factor to the conductivity. In the main text, we focused on using the average
sign as a signal of the QCP. Here we provide context by showing some of the
traditional measurements. More detailed results are contained in the
literature [149, 42, 150, 16, 151, 152, 153, 17, 154].

Figure S1 shows the derivatives of the average kinetic energy $\langle
K\rangle=\frac{-t}{2L^{2}}\sum_{\langle
i,j\rangle,\sigma}(c_{i\sigma}^{\dagger}c_{j\sigma}^{\phantom{}}+c_{j\sigma}^{\dagger}c_{i\sigma}^{\phantom{}})$
and double occupation $\langle n_{\uparrow\downarrow}\rangle$ with respect to
$U$ across the honeycomb lattice transition from semimetal to AFMI. Both show
clear signals in the vicinity of $U_{c}$. The accurate indication of
antiferromagnetic long range order requires a careful finite size scaling
analysis of the antiferromagnetic structure factor, which can be found in
Refs. [42, 16, 17].

Figure S2: Spin resolved sign for the SU(2) Hubbard model on the honeycomb
lattice. The scaling with the inverse of the linear system size $L$ of the
average sign of individual determinants in the case there is no sign problem:
$\mu/t=0$. The star marker depicts the best known estimation of the critical
value $U_{c}/t=3.869$ [17] at the ground state for the onset of the Mott
insulating phase with AFM order. All data are extracted at $T/t=1/20$, with
$\Delta\tau=0.1$.

### Individual spin channel average sign in the Spinful Hubbard Model on a
Honeycomb Lattice.—

In the main text, we have demonstrated how the average sign can be used as a
‘tracker’ of quantum critical behavior. In the case of models within regimes
where a sign problem is absent, e.g., for an SU(2) Hubbard model on a
bipartite lattice, this ability is no longer available if the chemical
potential $\mu=0$, since the determinants of the two spin species always have
the same sign so that their product is positive. This can be proven by
considering a staggered particle-hole transformation (PHT)
$c^{\dagger}_{i\downarrow}\rightarrow(-1)^{i}c^{\phantom{\dagger}}_{i\downarrow}$
on the down spin species. Here $(-1)^{i}=+1(-1)$ on sublattice A(B). Under the
PHT, the kinetic energy matrix $K$ of Eqs. (S3),(S4) remains invariant, but
the matrices $P^{\tau}$ in the down spin trace change sign, making the down
spin determinant the same as the up spin determinant, up to a positive factor
$e^{\lambda\sum_{i\tau}s_{i\tau}}$ [85].

While the product of the determinants is always positive in this situation,
the QCP remains imprinted in the average sign of the determinants for
individual spin components $\langle{\cal S}_{\sigma}\rangle$. To illustrate
this, we consider the first model used in the main text, the repulsive spinful
Hubbard model on the (bipartite) honeycomb lattice. Figure S2 plots
$\langle{\cal S}_{\sigma}\rangle$ ($\sigma=\uparrow,\downarrow$) at fixed
$T/t=1/20$. The individual signs are largely positive in the metallic phase,
but rather abruptly change to equally positive and negative ($\langle{\cal
S}\rangle\sim 0$) in the AFMI phase $U>U_{c}$. The match of the transition in
the sign and the position of the QCP becomes increasingly precise in the
thermodynamic limit $1/L\rightarrow 0$. The sharpness of the drop in
$\langle{\cal S}_{\sigma}\rangle$ with increasing system sizes is suggestive
of a possible scaling form for this quantity. Preliminary data, to be
presented elsewhere, indicates a scaling with critical exponents compatible
with the ones obtained from physical observables [155].

##  VIII More details on the Ionic Hubbard Hamiltonian (main text, Sec. II)

### Finite-size effects.—

The ionic Hubbard model presents a unique situation in our study: instead of
displaying a quantum critical point at half-filling, it exhibits a quantum
critical regime, associated with a correlated metal (CM) phase [46, 156, 18,
44, 157, 45, 46, 156, 19, 20, 158]. We argued in the main text that this
phase, sandwiched between the band-insulator (BI) at large $\Delta$, and the
Mott insulator (MI) at large $U$, can be indicated by a vanishing average sign
in the DQMC simulations. We now explore the influence of finite-size effects
on those phase boundaries, for a specific value of the staggered potential
$\Delta/t=0.5$.

Figure S3: Finite-size analysis: Ionic Hubbard model. (A, B, C) The average
sign $\langle{\cal S}\rangle$ for decreasing temperatures (growing
$\beta=1/T$) as a function of the Hubbard interaction $U/t$ in a lattice with
$L=8,12$ and 16 with a staggered potential $\Delta/t=0.5$. (D,E,F) The
corresponding magnitude of the derivative of $\langle{\cal S}\rangle$ in
respect to $U$ at each lattice size. (G) Peak position of the derivative of
the average sign with different inverse temperatures $\beta$; the inset
presents an extrapolation to the thermodynamic limit of the estimated
transition from the BI to the CM phase, as inferred by the first peak of
$|d\langle{\cal S}\rangle/dU|$. The gray dashed lines in all panels display
the corresponding transition value obtained in Ref. [156]. All data are
averaged over 24 independent runs, with $\Delta\tau=0.1$.

Figure S3 indicates that the first transition which occurs upon increasing
$U/t$ from zero, that from BI to CM, is well marked by a fast drop of
$\langle{\cal S}\rangle$ at lower temperatures. A quantitative estimation of
the transition point can be extracted by differentiating the average sign with
respect to the interaction strength, $d\langle{\cal S}\rangle/dU$ (lower
panels in Fig. S3). As the temperature is lowered, the peak position quickly
approaches the best known values of the transition for this set of parameters
[156], see Fig. S3(G). The system size dependence is reasonably small. The
second transition, from CM to AFI, on the other hand, displays characteristics
reminiscent of a crossover for the system sizes and temperatures investigated.
The estimate given by the peak of the average sign also displays a stronger
dependence on $L$, and, overall, is larger than the value of the position of
the metal-AF transition at this $\Delta$ obtained in Ref. [156]. It is worth
mentioning that these values in the existing literature were extracted at
smaller lattice sizes than the largest $L$ used here. A finite size
extrapolation of the ‘traditional’ correlations used to obtain $U_{c}$ for the
metal-AF transition, similar to the one we perform here, would be useful to
undertake.

### QMC vs. ED.—

A valuable test of the conjecture that $\langle{\cal S}\rangle$ tracks a
quantum phase transition (or regime) can be made by comparing QMC results with
exact ones, obtained at smaller lattice sizes. For this purpose, we contrast
in Fig. S4 the average sign in a lattice with $L=4$ with numerical results
obtained from exact diagonalization (ED). At this small lattice size, the
quantum critical region shrinks, and at the lowest temperatures studied
($T/t=1/24$) $\langle{\cal S}\rangle$ displays a sharp dip at around
$V/t\simeq 2$. Turning to the ED results, we probe the transition via the
analysis of the low lying spectrum $E_{\alpha}$ ($E_{0}$ is the ground-state),
the many-body excitation gaps $\Delta_{\rm ex}^{(\alpha)}=E_{\alpha}-E_{0}$,
the spin and charge staggered structure factors, $S_{\rm
sdw}=(1/N)\sum_{i,j}(-1)^{\eta}\langle(n_{i\uparrow}-n_{i\downarrow})(n_{j\uparrow}-n_{j\downarrow})\rangle$
and $S_{\rm
cdw}=(1/N)\sum_{i,j}(-1)^{\eta}\langle(n_{i\uparrow}+n_{i\downarrow})(n_{j\uparrow}+n_{j\downarrow})\rangle$
[$\eta=+1\ (-1)$ when $i,j$ belong to the same (different) sublattices], and,
the fidelity metric $g_{\tiny
U}=\frac{2}{N}\frac{1-|\langle\Psi_{0}(U)|\Psi_{0}(U+dU)\rangle|}{dU^{2}}$.
This last quantity displays a peak whenever one crosses a quantum phase
transition for the parameters $U$ and $U+dU$. These results describe a single
transition in the range of parameters investigated, displaying a first-order
character, given the level crossings shown in Fig. S4(B) or a vanishing
excitation gap $\Delta_{\rm ex}^{(1)}=E_{1}-E_{0}$ at $U/t\simeq 1.99$ [Fig.
S4(C)]. In turn, the fidelity metric displays a sharp peak at this interaction
value [Fig. S4(E)], and the structure factors computed at the ground-state
swap its characteristics, from a charge- to a spin-ordered one [Fig. S4(D)].
It is an open question of whether one is able to capture the intermediate
correlated metal phase in exact methods such as ED.

Stepping back from the technical details, the central message of Fig. S4 is
extending the evidence presented in the main text that the sign problem metric
for the QCP of panel A lines up well with those of the ‘traditional
observables’ in panels B-E.

Figure S4: QMC vs. ED on a 4x4 lattice. (A) The average sign extracted from
the DQMC calculations $\langle{\cal S}\rangle$ for increasing inverse
temperatures $\beta=1/T$ as a function of the Hubbard interaction $U/t$ in a
lattice with $L=4$ and a staggered potential $\Delta/t=0.5$. (B–E) Data
extracted with the ED, including: (B) The low-lying eigenspectrum $E_{\alpha}$
at the zero-momentum sector $\mathbf{k}=(0,0)$; (C) The excitation gaps
$\Delta_{\rm ex}^{(\alpha)}$; (D) the spin and charge structure factors and
(E) the fidelity metric under variations of the interaction magnitudes $U$,
using $dU=10^{-3}t$. In (A), data are averaged over 24 independent runs, with
$\Delta\tau=0.1$.

##  IX More details on Spinless Honeycomb Hubbard (main text, Sec. III)

### The finite-temperature transition.—

As we have argued in the main text, the interacting spinless fermion
Hamiltonian has a special property in AFQMC simulations: with an appropriate
choice of the basis one uses to write the fermionic matrix, it has been proven
that the sign problem can be eliminated [41, 34, 38]. Nonetheless, using a
standard single-particle basis, where the sign problem is manifest, we
demonstrated in Fig. 3 that $\langle{\cal S}\rangle$ can be used as a way to
track the quantum phase transition. Concomitantly, we have shown that a local
observable (the derivative of the nearest neighbor density correlations with
respect to the interactions $V$) exhibits a steep downturn once the quantum
(i.e. zero temperature) phase transition is approached.

As a by-product of this analysis, we use our original approach based on the
standard BSS algorithm in the standard fermionic basis to show that one can
also obtain an estimation of the finite-temperature transition (pertaining to
universality class of the 2D Ising model) with a relatively large accuracy, if
the system is not too close to the quantum critical point, see Fig. S5. We
compute both the derivative of the nearest-neighbor density correlations as
well as the CDW structure factor, i.e., a summation of all density-density
correlations with a $+1$ $(-1)$ for sites belonging to the same (different)
sublattice, on the largest lattice size we have investigated, $L=18$. These
finite-size results for $T_{c}$ are in good agreement with recent results
obtained after system size scaling of data extracted with continuous-time QMC
methods [22, 48], where the sign problem is absent.

Figure S5: Finite-temperature transition for the spinless fermion on the
honeycomb lattice. As a by-product of the analysis of the temperature
dependence for average sign, we notice that other than in regimes very close
to the QCP, $\langle{\cal S}\rangle$ is very close to 1. (A) The derivative of
the nearest-neighbor density correlations in the $T/t$ vs. $V/t$ plane and (B)
the CDW structure factor for a lattice with $L=18$. In both plots, the markers
are the continuous-time QMC results extracted after finite-size scaling in
Ref. [48]. Imaginary-time discretization is fixed at $\Delta\tau=0.1$, and all
data is obtained as an average of 20 independent runs. Figure S6: The U(1)
model on the honeycomb lattice: Average sign dependence on the imaginary time-
discretization. The dependence of $\langle{\cal S}\rangle$ on the imaginary-
time discretization $\Delta\tau$ with growing interactions $V/t$, in a lattice
with $L=9$. Data is extracted as an average of 24 independent runs, for a
temperature $T/t=1/24$. The best known value for the Mott insulating
transition [41] ($V_{c}/t=1.355$) is signalled by the star marker.

An important outcome of these results is that they imply that the mark that a
phase transition leaves on the average sign is restricted to quantum phase
transitions, rather than thermal ones, as we show above.

### Imaginary-time discretization.—

Here we consider the effect of the imaginary-time discretization $\Delta\tau$
on the average sign, for a fixed inverse temperature and show that ‘Trotter
errors’ [159] do not affect our conclusions. Figure S6 shows the average sign
for a fixed lattice size $L=9$ and $\Delta\tau$ ranging from 0.025 to 0.2 with
a fixed temperature $T/t=1/24$. The drop in $\langle{\cal S}\rangle$ when
approaching $V_{c}$ is indicative of the QCP, but using a more dense
imaginary-time discretization does not render substantial changes in the
average sign; similar behavior was observed in other models studied.

##  X More details for the homogeneous Hubbard model on the square lattice
(main text, Sec. IV)

### Finite-size effects.—

An important aspect that deserves further attention concerns finite-size
effects on the data presented in the main text. The average sign, for example,
when not protected by some underlying symmetry of the Hamiltonian, is known to
decrease for larger system sizes [29]. Figure S7 compares the original
quantities displayed in the main text [Fig. 4] at different lattice sizes. The
“growth” of the $\langle{\cal S}\rangle\to 0$ dome is relatively small when
taking into account lattices differing by an order of magnitude in the number
of sites. The $d$-wave pair-susceptibility also qualitatively preserves its
overall features, with a tendency of local pair formation at higher electronic
densities, encapsulating the $\langle{\cal S}\rangle\to 0$ dome. Similarly,
the static spin-susceptibility and its accompanying ‘pseudogap’ line are
largely unaltered when the linear lattice size varies from $L=8$ to 16. These
results for different $L$ indicate that our analysis of the link between the
SP and quantum criticality is not a finite size effect.

Figure S7: Finite size effects for the SU(2) Hubbard model on the square
lattice. An analysis of the main quantities and their size dependence for the
model with potential connection with the physics of the cuprates. As in the
main text, we choose $U/t=6$ and $t^{\prime}/t=-0.2$. The top, middle, and
bottom rows of plots refer to $L=8,12$ and 16, respectively. In turn, the
columns from left to right depict the average sign, the correlated $d$-wave
pair susceptibility, and the long-wavelength static spin susceptibility.
Imaginary-time discretization is fixed at $\Delta\tau=0.0625$, and all data
are extracted as an average of 24 independent runs.

### Pair-symmetry channels.—

Another important check on the suitability of the chosen parameters to
describe the physics of pairs with the same experimentally inferred symmetry
as in the cuprates, is to directly compare the correlated susceptibility map
with different symmetry channels. This has been done in early studies of QMC
[57], and here, as a side-aspect of the analysis of the average sign, we bring
in a systematic investigation. Figure S8 displays the correlated pair
susceptibility $\langle P_{\alpha}-P_{\alpha}^{\rm nv}\rangle$ dependence on
the temperature and electronic filling, with $\alpha=d,s^{*}$ or $s$-wave.
Clearly, the symmetric local pairing channel ($s$-wave), which directly
confronts the on-site $U$, is not favored in the whole range of $T$ and $\rho$
investigated. The correlated pair susceptibility is always negative for finite
values of $\langle{\cal S}\rangle$, indicating the vertex is repulsive. In
contrast, both the extended $s$-wave and $d$-wave pairings exhibit positive
correlated pairing susceptibilities in the vicinity of the $\langle{\cal
S}\rangle\to 0$ dome, but are more pronounced in the latter. This emphasizes
the dominance of $d$-wave pairing in the Hubbard model, in direct analogy to a
wide class of materials displaying high-temperature superconductivity.

Figure S8: Comparison of the pairing channels for the SU(2) Hubbard model on
the square lattice. Taking as a starting point for the physics of the cuprates
the parameters $U/t=6$ and $t^{\prime}/t=-0.2$ [160, 161], we display the
comparison of the correlated pair susceptibilities considering different
symmetry channels in the left ($d$-wave), center (extended s-wave, $s^{*}$)
and right ($s$-wave) columns, both in $\mu/t$ vs. $T/t$ (upper row) and $\rho$
vs. $T/t$ (lower row) parametric space. Imaginary-time discretization is fixed
at $\Delta\tau=0.0625$, and all data are extracted as an average of 24
independent runs in a lattice with $L=16$.

### Spectral weight at the anti-nodal point.—

In describing the physics of cuprates, a common focus is the anisotropy of the
single-particle gap as extracted from ARPES techniques [49], which contrasts
with the standard isotropic behavior seen in conventional BCS-type
superconductors. At the root of the discussion is the shape of the Fermi
surface when doping the parent spin-ordered Mott insulator. In particular, to
classify the onset of the pseudogap phase at low enough temperatures $T$,
i.e., the regime where single-particle, low-energy excitations are suppressed,
one tracks the peak of the anti-nodal spectral weight at the Fermi energy,
$A_{(\pi,0)}(\omega=0)\equiv-\frac{1}{\pi}{\rm Im}G_{(\pi,0)}(\omega=0)$ as
$T$ is varied.

In QMC simulations, this quantity can in principle be extracted by means of an
analytical continuation of the data, in which the imaginary-time dependence of
the Green’s function $G$ is converted to real frequency. To avoid the well
known difficulty of such a calculation [162], a proxy valid at low enough
temperatures, $A_{(\pi,0)}^{\rm proxy}=\beta G_{(\pi,0)}(\tau=\beta/2)$ is
often used [163, 164]. Figure S9 shows the results for the anti-nodal spectral
function. The pseudogap line extracted from the proxy is qualitatively close
to the one obtained from the peak of the static long-wavelength spin
susceptibility (Figs. 4 and S7) and, like it, terminates on the $\langle{\cal
S}\rangle\to 0$ dome.

Figure S9: Comparison of the single-particle spectral weight at the anti-nodal
point. Temperature extrapolation of the extracted $A_{(\pi,0)}$ at the Fermi
energy vs the chemical potential $\mu/t$ (A) and the electronic density $\rho$
(B), on a lattice with $L=16$; other parameters are $U/t=6$ and
$t^{\prime}/t=-0.2$. The maximum values at each temperature are denoted by the
white markers. Imaginary-time discretization is fixed at $\Delta\tau=0.0625$,
and all data is extracted as an average of 24 independent runs.

### Spectral function and the Lifshitz transition.—

The extensive dataset and associated analysis we have undertaken in this
investigation of the sign problem enables us to check other important physical
aspects of the Hubbard model on the square lattice, and their relation to
cuprate phenomenology. We include them here, in order to further link their
behavior to that of the sign. One of them refers to the change of the topology
of the Fermi surface when increasing the hole-doping (decreasing the electron
density) from half-filling: at some critical $\langle n\rangle$, the Fermi
surface changes its shape from hole-like to a closed, electron-like one. This
transition, referred to as the Lifshitz transition, has been investigated in
the context of strongly interacting electrons, and was inferred to occur
concomitantly with the presence of a van Hove singularity at the Fermi level
[165].

Figure S10: Lifshitz transition. The evolution of the spectral function in one
quadrant of the Brillouin zone with increasing densities, after an
interpolation of the results for a $24\times 24$ lattice at temperature
$T/t=1/3.25$, with $U/t=6$ and $t^{\prime}/t=-0.2$. The different panels
depict results with various chemical potentials as marked, and the average
density is 0.25 in (A), 0.65 in (B), 0.95 in (C), and 1.00 in (D). Imaginary-
time discretization is fixed at $\Delta\tau=0.0625$, and all data is extracted
as an average of 20 independent runs.

Due to the presence of the SP, however, we can only investigate the Lifshitz
transition at finite-temperatures, and thus the Fermi ‘surface’ is thermally
broadened. Nonetheless, Fig. S10 displays the spectral function (obtained via
the ‘proxy’ scheme as previously explained) at the Fermi energy on lattices
with linear size $L=24$, at a temperature right above the $\langle{\cal
S}\rangle\to 0$ dome, and investigating dopings above and below the pseudogap
line in Figs. 4 and S10. As one increases the density, the change of topology
precisely confirms the Lifshitz-scenario, with a further formation of hole-
pocket regions along the anti-nodal direction, in direct analogy to the
phenomenology of high-Tc superconductors [49].

### Comparison to the near-neighbor hopping only Hubbard model.—

While it is remarkable how much of the physics of simplest Hubbard Hamiltonian
captures that of the cuprates [58], refinements of the model are known to
provide more accurate comparisons to the experiments [166, 160, 161]. One
such, the inclusion of next-nearest neighbor hopping $t^{\prime}$ was employed
in the analysis in the main text. It is significant in the context of the sign
problem because it breaks the particle-hole symmetry and, for example, induces
a SP even at half-filling. In this section we address the extent to which
including $t^{\prime}$ affects our conclusions. To this end, we contrast the
results of Fig. 4 with the ones arising from the Hubbard model with
$t^{\prime}=0$ (Fig. S11). The key qualitative aspects are similar, including
the presence of a $\langle{\cal S}\rangle\to 0$ dome, the tendency of $d$-wave
pair formation (due to the enhanced pair susceptibility with this symmetry
around such dome) and a peak of the spin susceptibility ending at the dome.
The differences are: (i) while approaching half-filling, the average sign
displays a sudden jump towards 1 (as one would expect for this bipartite
case), (ii) the extension of the dome, within the temperatures investigated
($T/t\geq 1/6$), is more constrained in density compared to the
$t^{\prime}/t=-0.2$ case, and, more importantly, (iii) the pseudogap region,
signified by the temperatures below the $\chi(\textbf{q}=0)$ peak, is
significantly reduced. Our data thus provide another argument in support of an
added next-nearest neighbor hopping in order to possibly explain the phase
diagram of high $T_{c}$ materials, which display a robust pseudogap region.
However, the main point for the purpose of this manuscript is that whether
$t^{\prime}$ is included or not, the behavior of the sign is correlated with
the physics of pairing and magnetism.

Figure S11: The ‘phase diagram’ of the bipartite Hubbard model on the square
lattice. The same as Fig. 4 in the main text, but instead removing the non-
bipartite contribution $t^{\prime}$, i.e., here the ‘vanilla’ Hubbard model
results are presented. Other parameters are the same, as $L=16$,
$\Delta\tau=0.0625$ and $U/t=6$.