Basis Dependence, Computational Complexity, and No Universal Cure

The sign of a Monte Carlo weight belongs to a representation, not to a Hamiltonian or path integral in isolation. A local basis rotation, Hubbard–Stratonovich channel, duality, contour deformation, or regrouping of configurations can remove destructive signs in one description while creating nonlocal interactions, a hard observable map, a complex Jacobian, or an exponentially expensive transformation. Complexity results rule out certain generic polynomial-time cures under stated hypotheses; they do not prove that every finite-density model or every useful parameter region is hard.

Required background. Anatomy and severity of a sign problem supplies phase, overlap, and cost diagnostics.

Helpful background. Symmetry, gauge redundancy, and duality supplies exact changes of variables and invariant content.

Stoquasticity is basis relative

Convention and regulator card. Consider a finite-dimensional regulated Hilbert space with a named product basis $\{|x\rangle\}$. A real Hamiltonian is stoquastic in this basis if $H_{xy}\le0$ for every $x\ne y$. Then for sufficiently small $\Delta\tau$, the off-diagonal transfer-matrix elements of $e^{-\Delta\tau H}$ are nonnegative to leading order. The definition says nothing until the basis, allowed transformations, locality notion, and cost of evaluating transformed observables are specified.

Take

$$H=t\begin{pmatrix}0&1\\1&0\end{pmatrix}, \qquad t>0.$$

In the displayed basis it is nonstoquastic. With the local phase change $U=\operatorname{diag}(1,-1)$,

$$UHU^\dagger=t\begin{pmatrix}0&-1\\-1&0\end{pmatrix},$$

which is stoquastic. The spectrum and partition function are unchanged. An observable $O$ must also become $UOU^\dagger$; forgetting this can turn a correct sign-free simulation into a wrong measurement.

Diagonal sign changes $|x\rangle\mapsto s_x|x\rangle$, $s_x=\pm1$, cannot repair every sign pattern. On a graph of nonzero off-diagonal matrix elements, the product of edge signs around a closed cycle is invariant because every $s_x$ occurs twice. For a triangle with all $H_{xy}=+t$, the edge-sign product is positive, whereas three nonpositive off-diagonal elements would have negative product. No diagonal $\pm1$ gauge makes that triangle stoquastic. A more general unitary might, but it can destroy the tensor-product locality that made sampling efficient.

The full cost of a representation change

Let $y=F(x)$ be an exact transformation. Equality of partition functions requires

$$Z=\int_X dx\,w(x) =\int_Ydy\,w(F^{-1}y)\,J_{F^{-1}}(y).$$

A “solution” must account for all of the following:

• computing $F$, $F^{-1}$, and the Jacobian to the required precision;
• evaluating or sampling the transformed action with controlled scaling;
• translating the target observable and its normalization;
• representing global constraints, winding sectors, and boundary conditions;
• maintaining overlap and ergodic movement among relevant sectors.

If $w'(y)ge0$ but $O'(y)$ is an exponentially oscillatory sum, the sign problem has moved into measurement. If $w'$ is local only after introducing a constraint whose update mixes exponentially slowly, it has moved into dynamics. If determining $U$ itself requires solving an exponentially large optimization, existence does not give an algorithm.

The two-state benchmark above makes the observable issue explicit. For

$$O=\begin{pmatrix}0&1\\1&0\end{pmatrix},$$

the basis change gives $UOU^\dagger=-O$. Since $H=tO$,

$$\langle O\rangle_\beta =-\tanh(\beta t), \qquad \langle UOU^\dagger\rangle_{UHU^\dagger} =-\tanh(\beta t).$$

Measuring the untransformed matrix $O$ in the transformed ensemble instead yields $+\tanh(\beta t)$: a stable, sign-free, exactly wrong answer.

What the NP-hardness result says

Troyer and Wiese construct a family of quantum Monte Carlo instances in which efficiently removing the sign problem would solve an NP-complete Ising spin-glass problem. Their conclusion is a worst-case statement about a specified input family, desired accuracy, and polynomial resource scaling Troyer and Wiese 2005.

A defensible complexity claim must name:

1. Input class: which Hamiltonians, couplings, lattice sizes, and encodings vary with input size.
2. Permitted transformation: local basis rotations, arbitrary unitaries, auxiliary fields, dualities, regrouping, or contour changes.
3. Output and precision: a partition function, sign, energy, or observable; additive or relative error; success probability.
4. Resource measure: classical time, memory, oracle calls, preprocessing, and precision in the transformed weights.
5. Quantifier: worst case over a family, average case under a distribution, or a particular physical sequence.

NP-hardness of a generic cure does not imply that every instance is hard, that all bases are equally severe, that QCD at every $(T,\mu)$ realizes the reduction, or that exponential average-phase suppression proves NP-hardness. Conversely, finding a sign-free island does not contradict a worst-case theorem.

Sufficient symmetry criteria can guarantee nonnegative determinants for meaningful families; for example, antiunitary pairing can organize eigenvalues into complex-conjugate pairs Wu and Zhang 2005. Such structure is precisely why the no-universal-cure statement must coexist with model-specific solutions.

Local versus global transformations

For a many-body lattice, a product unitary $U=\bigotimes_iU_i$ preserves a strong form of locality and can be searched or applied with polynomial description length. A generic unitary on $n$ sites has exponentially many parameters. Between these extremes lie finite-depth circuits, tensor-network changes of basis, and exact dualities with nonlocal boundary maps.

A useful transformation report therefore gives two scalings:

$$C_{\rm total}(n,\epsilon) =C_{\rm find}+C_{\rm sample}+C_{\rm measure}+C_{\rm validate},$$

and

$$\ell_{O'}(n)=\text{support or bond complexity of }O'=UOU^\dagger.$$

Polynomial sampling with exponential $C_{\rm find}$ is not an efficient cure. A low-depth $U$ that makes $H$ nearly stoquastic but leaves a residual average sign $e^{-cn}$ must still report the residual exponent. “Milder” is meaningful only relative to a fixed observable, error tolerance, and scaling window.

Adversarial failure cases

Instance-to-family inflation. A basis rotation removes signs for one coupling point, and the result is advertised as a solution for the model. Test the same construction along a size-growing family and include the cost of finding the rotation.

Hidden nonlocal measurement. The transformed partition function is positive, but a two-point correlator becomes a sum of exponentially many strings. Validate both $Z$ and the intended observable; positivity of $Z$ alone is insufficient.

Worst-case theorem used as empirical diagnosis. An observed exponential average phase is described as NP-hardness. It demonstrates poor scaling for that estimator over the measured range, not a complexity-class reduction.

Approximate positivity without a bias bound. Small positive matrix elements are clipped to make a Hamiltonian stoquastic. Unless the induced change in each target observable is bounded and extrapolated to zero, the simulation targets a different theory.

The severity map below keeps basis dependence and complexity in their proper logical positions. Inspect the separate branches: changing variables can move a phase problem into nonlocal interactions or difficult observables, while a worst-case theorem requires an explicitly quantified input family.

The sign problem has distinct diagnostics. The average phase fixes direct phase-estimator signal-to-noise and may scale as $e^{-\beta_TV_s\Delta f}$; overlap depends on the target observable and proposal measure; a variable change can trade phase for nonlocality or hard observables; and worst-case complexity requires a separately specified problem family. The map is schematic, not a quantitative performance comparison.

Observable-level validation checklist

• Name the original and transformed bases, transformation class, locality, boundary sectors, and Jacobian.
• Measure the cost of finding and applying the transformation, not only the cost after it is known.
• Transform at least one noncommuting observable explicitly and compare with exact diagonalization on small systems.
• Report residual phase/sign severity and sector-mixing time as functions of system size.
• State every complexity claim with input family, precision, resource, and worst-case or typical-case quantifier.
• Include a frustrated sign pattern or other negative control that the proposed restricted transformation cannot repair.

Exercises

1. Cycle obstruction

Prove that diagonal sign changes preserve the product of off-diagonal signs around a closed cycle.

Solution

An edge transforms as $H_{xy}\mapsto s_xs_yH_{xy}$. On a cycle $(x_1x_2),(x_2x_3),\ldots,(x_kx_1)$, the extra factor is

$$(s_{x_1}s_{x_2})(s_{x_2}s_{x_3})\cdots(s_{x_k}s_{x_1}) =\prod_{j=1}^ks_{x_j}^2=1.$$

Hence the sign product is invariant. A target all-negative cycle has product $(-1)^k$, providing an immediate obstruction when the original product differs.

2. Claim translation

Rewrite “the fermion sign problem is NP-hard” as a testable statement that does not overclaim.

Solution

One acceptable form is: “For the size-indexed family and accuracy criterion used in the reduction of Troyer and Wiese, a generic polynomial-time algorithm that removes the Monte Carlo sign problem and computes the specified thermodynamic quantity would yield a polynomial-time algorithm for an NP-complete Ising spin-glass problem.” The statement is worst case and does not classify every fermion model or representation.

Learning outcomes

After working this page, you should be able to:

• Construct a basis change that alters stoquasticity, transform an observable with it, and account for locality and computational cost.
• Rewrite any sign-problem complexity claim with explicit input class, permitted transformations, precision, resources, and quantifier, rejecting conclusions not licensed by those hypotheses.

Handoff

Dual, worldline, and tensor reformulations provide concrete exact transformations whose constraints and observable maps can be checked. Cross-method validation turns “milder” into a measured, bounded claim.

References

• Troyer, Matthias, and Uwe-Jens Wiese. “Computational Complexity and Fundamental Limitations to Fermionic Quantum Monte Carlo Simulations.” Physical Review Letters 94 (2005): 170201. doi:10.1103/PhysRevLett.94.170201.
• Wu, Congjun, and Shou-Cheng Zhang. “Sufficient Condition for Absence of the Sign Problem in the Fermionic Quantum Monte Carlo Algorithm.” Physical Review B 71 (2005): 155115. doi:10.1103/PhysRevB.71.155115.