Research ArticlePHYSICS

Easing the Monte Carlo sign problem

See allHide authors and affiliations

Science Advances  14 Aug 2020:
Vol. 6, no. 33, eabb8341
DOI: 10.1126/sciadv.abb8341
  • Fig. 1 We optimize the non-stoquasticity ν1 of translation-invariant, two-local Hamiltonians over on-site orthogonal transformations O=On using a conjugate gradient method for manifold optimization (44, 45).

    (A) Relative non-stoquasticity improvement of random two-local Hamiltonians that are known to admit an on-site stoquastic basis. For each local dimension, 100 instances are drawn and the results are displayed as a box plot according to [(63), 2.16], where whiskers are placed at 1.5 times the interquartile range and circles denote outliers. This serves as a benchmark of our algorithm, which, for almost all instances, accurately recovers a stoquastic on-site basis. (B) Optimized non-stoquasticity of the anti-ferromagnetic J0-J1-J2-J3-Heisenberg model relative to the computational basis as a function of J2/J, J3/J, where J0 = J1 = J. The algorithm is initialized in a Haar random orthogonal on-site basis. This model is known to admit a nonlocal stoquastic basis for J3J0 + J1 (11). (C) Optimized non-stoquasticity of the anti-ferromagnetic Heisenberg ladder illustrated in the inset with couplings J, J, J× relative to the computational basis as a function of J/J and J×/J. We initialized the algorithm at the identity matrix (which was randomly perturbed by a small amount). The phase diagram of the non-stoquasticity qualitatively agrees with the findings of (14), where the stochastic series expansion QMC method was studied. There, it was found that the sign problem can be completely eliminated for a completely frustrated arrangement where J× = J, while the sign problem remains present for partially frustrated couplings J×J. However, throughout the parameter regime, the stoquasticity remains nontrivial, which may be due to the fact that the optimization algorithm converges to local minima.

  • Fig. 2 Improvement of the inverse average sign 〈sign〉−1 concomitant with the improvement in non-stoquasticity of Fig. 1C for the frustrated ladder model, as measured by the ratio of its logarithm before optimization compared to that after optimization.

    We compute the average sign via exact diagonalization for a ladder of 2 × 4-sites, m = 100 Monte Carlo steps, and inverse temperature β = 1.

  • Fig. 3 Constructing a Hamiltonian whose sign problem is NP-hard to ease under orthogonal on-site transformations.

    (A) To prove NP-completeness of SignEasing, we reduced it to the MAXCUT-problem, which asks for the ground-state energy of an anti-ferromagnetic Ising Hamiltonian H on a graph G. (B) In our encoding, we map H to a Hamiltonian H′, in which all ZZ interactions are replaced by XX interactions and translate the spin configurations (s1, …, sn) ∈ {0,1}n of the anti-ferromagnetic Ising model to on-site transformations Z1s1Znsn. To achieve this restriction, we penalize all other transformations by adding an ancilla qubit ξi, j for every edge (i, j) of G and adding the interaction term C(ZiZjZiZξi,jZjZξi,j) with a suitably chosen constant C > 0. We obtain that ν1(H′) can be eased below a certain value if and only if the ground-state energy of H is below that value to begin with, thus establishing the reduction.

  • Table 1 Analogy between satisfiability problems and curing/easing the sign problem.

    The satisfiability equivalent of curing the sign problem is to decide whether a given sentence is satisfiable, while the equivalent of easing is to find the minimal number of clauses that are violated by a sentence. Similarly, results on the computational complexity of curing and easing the non-stoquasticity of a local Hamiltonian H are in one-to-one correspondence with the hardness of satisfiability problems.

    SatisfiabilityStoquasticityComplexityReferences
    3SATCuring
    2 + 1-local H
    NP-complete(19, 20)
    2SATCuring strictly
    2-local H
    In P(20, 21)
    MAX2SATEasing strictly
    2-local H
    NP-completeHere

Supplementary Materials

  • Supplementary Materials

    Easing the Monte Carlo sign problem

    Dominik Hangleiter, Ingo Roth, Daniel Nagaj, Jens Eisert

    Download Supplement

    This PDF file includes:

    • Sections S1 to S4
    • Figs. S1 to S5
    • Appendices A and B
    • References

    Files in this Data Supplement:

Stay Connected to Science Advances

Navigate This Article