Local basis transformations can mitigate the negative sign problem in quantum Monte Carlo (QMC) simulations of frustrated quantum magnets, but the only known theoretical justification — that minimizing a locally computable surrogate, the L1 adaptive loss, bounds the true severity of the sign problem — holds under a frustration-free assumption that excludes the very systems where the sign problem is most harmful. The open problem is to establish the rigorous relationship between locally optimized loss functions and the true sign severity in general frustrated regimes: prove guarantees (or construct explicit counterexamples) for when minimizing the local loss reduces the true negativity, control the stoquastic-decomposition error that arises from the non-distributivity of the element-wise absolute value and depends on lattice connectivity, and characterize the cell-size and connectivity dependence that limits improvements in two dimensions. Recent successor work (2026) has advanced the empirical side with full unitary rotations and two-dimensional benchmarks, but explicitly leaves the cost-function-versus-average-sign correspondence unproven.

Background

Quantum Monte Carlo (QMC) methods, such as the stochastic series expansion (SSE) which expands the partition function Z=Tr eβGZ=\mathrm{Tr}\,e^{\beta G} (with G=−HG=-H, HH the Hamiltonian, β\beta inverse temperature) as a sum over classical configurations, are among the most powerful unbiased tools for equilibrium quantum many-body physics. Their key weakness is the negative sign problem: when configuration weights W(c)W(c) can be negative, sampling must proceed by reweighting through a 'virtual' Hamiltonian GvG_v with non-negative weights, and the statistical error of any observable is amplified by the average sign ⟨S⟩v\langle S\rangle_v. The amplification grows exponentially with system size and inverse temperature, making frustrated magnets — those whose interactions cannot be simultaneously minimized — largely inaccessible. The severity is basis-dependent: a unitary change of the local representation basis reshuffles which matrix elements are negative.

Murota and Todo (2025) introduced a unified severity metric, the negativity η=⟨∣S∣2⟩v/∣⟨S⟩v∣\eta=\sqrt{\langle|S|^2\rangle_v}/|\langle S\rangle_v|, and proved that the optimal virtual Hamiltonian is the stoquastic form G+G^+ of GG, obtained by replacing every off-diagonal matrix element by its absolute value (a 'stoquastic' Hamiltonian has all non-positive off-diagonal elements in the given basis and is sign-problem-free). Since ⟨S⟩v=Z/Zv\langle S\rangle_v = Z/Z_v and Zv=Tr eβGvZ_v=\mathrm{Tr}\,e^{\beta G_v} is maximized by Gv=G+G_v=G^+, the low-temperature severity is governed by the gap negativity η′=λ+(G)−λ(G)\eta'=\lambda^+(G)-\lambda(G), the difference between the largest eigenvalue of G+G^+ and of GG, a temperature-independent quantity. Because λ(G)\lambda(G) is basis-invariant, mitigating the sign problem by basis transformation reduces to minimizing λ+(G)\lambda^+(G) over products of local transformations U=⊗iuiU=\otimes_i u_i, where the same local unitary uu is applied uniformly to every optimization cell — a small repeating unit of one or more lattice sites, the single-site cell being the smallest choice, for which each bond operator becomes (u⊗u) gb (u†⊗u†)(u\otimes u)\,g_b\,(u^\dagger\otimes u^\dagger) — and larger cells enlarge the variational freedom while suppressing the effect of sites shared by several bonds.

Directly evaluating η′\eta' is exponentially costly, so the authors introduced a locally computable surrogate, the L1 adaptive loss

LL1(G,u)=1∣B∣∑b∈Bλ+((u⊗u) gb (u†⊗u†))−λ(gb),\mathcal{L}_{\mathrm{L1}}(G,u)=\frac{1}{|\mathcal{B}|}\sum_{b\in\mathcal{B}}\lambda^+\big((u\otimes u)\,g_b\,(u^\dagger\otimes u^\dagger)\big)-\lambda(g_b),

where B\mathcal{B} is the set of bonds and λ+(⋅)\lambda^+(\cdot) the largest eigenvalue. A Hamiltonian is frustration-free when its ground state simultaneously minimizes every local term; under this assumption they proved LL1(G,u)≥λ+(G)−λ(G)\mathcal{L}_{\mathrm{L1}}(G,u)\ge\lambda^+(G)-\lambda(G) (their Theorem 1), so minimizing the loss provably drives down an upper bound on the sign severity. The crux is that stoquasticization is not distributive over the bond decomposition: G+≠∑bgb+G^+\neq\sum_b g_b^+, because taking element-wise absolute values and summing do not commute, and the discrepancy is generated at sites shared by several bonds — hence it depends on lattice connectivity, through the area-to-volume ratio of optimization cells, and is expected to grow in the very regimes (two-dimensional, frustrated) where the method empirically gains less. Optimizing the loss by Riemannian gradient descent (gradient descent adapted to the curved manifold of orthogonal or unitary matrices) with the Adam optimizer (a standard adaptive stochastic-gradient method), the authors reproduced almost all previously known analytical basis transformations in frustration-free and related spin models, found weaker improvement rates in two dimensions, and showed that restricting to orthogonal (real) transformations can break Hamiltonian symmetries (e.g. the Jx↔JyJ_x\leftrightarrow J_y exchange symmetry of the kagome Heisenberg model, the antiferromagnet on the kagome lattice of corner-sharing triangles) which unitary transformations restore.

Hatano and Suzuki (1992) first emphasized the basis dependence of the sign problem; Nakamura (1998) found sign-free bases in frustrated 1D chains; Levy and Clark (2021) optimized orthogonal basis rotations directly against the average sign; Hangleiter, Roth, Nagaj, and Eisert (2020) proposed minimizing measures of non-stoquasticity (the total magnitude of negative off-diagonal elements) over the orthogonal group and proved that even this 'easing' is NP-complete for nearest-neighbour Hamiltonians with simple basis choices. Complexity-theoretic results frame the ceiling: curing non-stoquasticity is NP-hard in general (Marvian, Lidar, Hen 2019), and the two-local qubit case has been classified (Klassen et al. 2020). The open question is therefore not whether the sign problem can be cured in general (it cannot, barring complexity-theoretic collapse), but whether the local-surrogate optimization strategy carries any guarantee outside frustration-free regimes, and how its unavoidable approximation errors are controlled by lattice and cell geometry.

Problem Statement

Establish the rigorous foundations — and the controlled limits — of local basis-transformation mitigation of the quantum Monte Carlo sign problem, as posed by Murota and Todo (2025). The objective is to determine the exact relationship between locally computable optimization losses and the true severity of the sign problem, jointly along three linked fronts:

  1. Guarantees beyond frustration-free regimes. Determine under what conditions on the Hamiltonian and the local transformation family minimizing the L1 adaptive loss LL1\mathcal{L}_{\mathrm{L1}} (or a comparable local surrogate) provably reduces the true negativity of the transformed Hamiltonian — extending, tightening, or delimiting the frustration-free upper bound LL1(G,u)≥λ+(G)−λ(G)\mathcal{L}_{\mathrm{L1}}(G,u)\ge\lambda^+(G)-\lambda(G) — and/or construct explicit counterexamples (Hamiltonians and transformation families where loss minimization fails to reduce, or worsens, the true negativity) outside those conditions.

  2. Control of the stoquastic-decomposition mismatch. Characterize quantitatively how the non-distributivity error G+≠∑b∈Bgb+G^+\neq\sum_{b\in\mathcal{B}}g_b^+ — generated at sites shared by multiple bonds and hence governed by lattice connectivity and the area-to-volume ratio of optimization cells — separates the local loss from the true gap negativity, and establish how this error can be bounded, corrected, or suppressed by cell design or modified local terms.

  3. Lattice-connectivity and scaling dependence. Explain and characterize the observed weaker improvement in two-dimensional versus one-dimensional systems, addressing all of the following: (a) the roles of cell choice, cell size, boundary effects, and overlap structure of local terms; (b) the feasibility and convergence behavior of the Riemannian-gradient optimization over larger cells, larger local Hilbert spaces, and the full unitary (rather than orthogonal) group; and (c) the trade-offs (cost, parametrization, optimization landscape) of unitary optimization.

A complete answer consists of a determination of the conditions requested in front 1 — through proven statements with explicit assumptions and tightness analysis, through explicit counterexamples delimiting where loss minimization fails to control the true negativity, or through both — quantitative bounds or correction schemes for front 2, and a systematic — theoretical or reproducibly numerical — account of all three components (a)–(c) of front 3, jointly determining when locally optimized basis transformations can be trusted to mitigate the sign problem in frustrated, including two-dimensional, quantum spin systems.

References

  1. Keisuke Murota and Synge Todo, 'Local Basis Transformation to Mitigate Negative Sign Problems' (2025), arXiv:2501.18069, DOI 10.48550/arxiv.2501.18069, https://arxiv.org/abs/2501.18069
  2. Julius S. Herz, Robin Schäfer, Matías G. Gonzalez, David J. Luitz, 'Sign-optimized Quantum Monte Carlo' (2026), arXiv:2607.24679, https://arxiv.org/abs/2607.24679
  3. Dominik Hangleiter, Ingo Roth, Daniel Nagaj, Jens Eisert, 'Easing the Monte Carlo sign problem', Science Advances 6, eabb8341 (2020), DOI 10.1126/sciadv.abb8341, arXiv:1906.02309, https://arxiv.org/abs/1906.02309
  4. Ryan Levy and Bryan K. Clark, 'Mitigating the Sign Problem through Basis Rotations', Physical Review Letters 126, 216401 (2021), DOI 10.1103/PhysRevLett.126.216401, arXiv:1907.02076, https://arxiv.org/abs/1907.02076
  5. Naomichi Hatano and Masuo Suzuki, 'Representation basis in quantum Monte Carlo calculations and the negative-sign problem', Physics Letters A 163, 246–249 (1992), DOI 10.1016/0375-9601(92)91006-D, https://doi.org/10.1016/0375-9601(92)91006-D
  6. Tota Nakamura, 'Vanishing of the negative-sign problem of quantum Monte Carlo simulations in one-dimensional frustrated spin systems', Physical Review B 57, R3197–R3200 (1998), DOI 10.1103/PhysRevB.57.R3197, https://doi.org/10.1103/PhysRevB.57.R3197
  7. Milad Marvian, Daniel A. Lidar, Itay Hen, 'On the computational complexity of curing non-stoquastic Hamiltonians', Nature Communications 10, 1571 (2019), DOI 10.1038/s41467-019-09501-6, https://doi.org/10.1038/s41467-019-09501-6
  8. Joel Klassen, Milad Marvian, Stephen Piddock, Marios Ioannou, Itay Hen, Barbara M. Terhal, 'Hardness and ease of curing the sign problem for two-local qubit Hamiltonians', SIAM Journal on Computing 49, 1332–1362 (2020), DOI 10.1137/19m1287511, https://doi.org/10.1137/19m1287511
  9. Kwai-Kong Ng and Min-Fong Yang, 'Mitigating the sign problem by quantum computing', Physical Review A 113, 032611 (2026), DOI 10.1103/s4nb-6fdq, arXiv:2509.13017, https://arxiv.org/abs/2509.13017
  10. Synge Todo, 'Markov Chain Monte Carlo in Tensor Network Representation' (2024, revised 2026), arXiv:2412.02974, https://arxiv.org/abs/2412.02974
  11. Arman Babakhani and Armen Karakashian, 'Stoquasticity is not enough: towards a sharper diagnostic for Quantum Monte Carlo simulability' (2025), arXiv:2508.14382, https://arxiv.org/abs/2508.14382