On the Computational Complexity of Curing the Sign Problem

Throughout this work we reserve the term ‘efficient’ to mean that the algorithm requires at most a polynomial run-time in the problem size (the number of variables). For example, an algorithm equilibrates efficiently if it can correctly samples from the Gibbs distribution of the Hamiltonian in question with at most a polynomial run-time in the problem size and the given statistical error [see part (iii) of the definition of the sign problem given in Ref. [ 7 ] for a precise statement.]

Cited in the paper.

The thermal average is ⟨ A ⟩ ≡ 1 Z ​ Tr ​ ( e − β ​ H ​ A ) \langle A\rangle\equiv\frac{1}{Z}\mathrm{Tr}(e^{-\beta H}A) where β \beta is the inverse temperature, and our claim is that ⟨ A ⟩ = ⟨ A ′ ⟩ \langle A\rangle=\langle A^{\prime}\rangle where A ′ = U ​ A ​ U † A^{\prime}=UAU^{\dagger} for unitary U U . Here is the proof. First, Z = Tr ⁡ ( e − β ​ H ) = Tr ⁡ ( U ​ e − β ​ H ​ U † ) = Tr ⁡ ( e − β ​ H ′ ) = Z ′ Z=\mathrm{Tr}(e^{-\beta H})=\mathrm{Tr}(Ue^{-\beta H}U^{\dagger})=\mathrm{Tr}(e^{-\beta H^{\prime}})=Z^{\prime} where H ′ = U ​ H ​ U † H^{\prime}=UHU^{\dagger} . Thus ⟨ A ⟩ = 1 Z ​ Tr ​ ( U ​ e − β ​ H ​ U † ​ U ​ A ​ U † ) = 1 Z ′ ​ Tr ​ ( e − β ​ H ′ ​ A ′ ) = ⟨ A ′ ⟩ \langle A\rangle=\frac{1}{Z}\mathrm{Tr}(Ue^{-\beta H}U^{\dagger}UAU^{\dagger})=\frac{1}{Z^{\prime}}\mathrm{Tr}(e^{-\beta H^{\prime}}A^{\prime})=\langle A^{\prime}\rangle

Cited in the paper.

A related approach was discussed by Barbara Terhal at the AQC17 conference http://www.smapip.is.tohoku.ac.jp/~aqc2017/program.html

Cited in the paper.

In general, M M can grow polynomially (usually linearly for hard instances) with n n , but \mathaccentV ​ t ​ i ​ l ​ d ​ e ​ 07 ​ E ​ H 3 ​ S ​ A ​ T \mathaccentV{tilde}07E{H}_{\mathrm{3SAT}} remain k k -local since the operator norm of each of its terms is poly ​ ( n ) \textrm{poly}(n) , as required by the definition of a k k -local Hamiltonian (see, e.g., Definition 1 of Ref. [ 8 ] )

Cited in the paper.

For example in Ref. [ 7 ] a solution to sign problem is defined as: “an algorithm of polynomial complexity to evaluate the thermal average ⟨ A ⟩ \langle A\rangle ”… “[f]or a quantum system that suffers from a sign problem for an observable A A , and for which there exists a polynomial complexity algorithm for the related bosonic system”

Cited in the paper.

Consider the following example. (i) H X = ∑ i ​ j J i ​ j ​ X i ​ X j H_{X}=\sum_{ij}{J}_{ij}X_{i}X_{j} , with J i ​ j {J}_{ij} randomly chosen from the set { 0 , ± J } \{0,\pm J\} on a three-dimensional lattice, has a sign problem. (ii) Deciding whether its ground state energy is below a given bound is NP-complete [ 10 ] . (iii) Deciding the same for its bosonic and sign-problem-free version H | X | = ∑ i ​ j | J i ​ j | ​ X i ​ X j H_{|X|}=\sum_{ij}|J_{ij}|X_{i}X_{j} is in BPP (classical polynomial time with bounded error) since this Hamiltonian is that of a simple ferromagnet. The conclusion drawn in Ref. [ 7 ] was that since the bosonic version is easy to simulate, the sign problem is the origin of the NP-hardness of a QMC simulation of this model ( H X H_{X} ). However, note that computing thermal averages via a QMC simulation of H X H_{X} is the same as for H Z = W ⊗ n ​ H X ​ W ⊗ n = ∑ i ​ j J i ​ j ​ Z i ​ Z j H_{Z}=W^{\otimes n}H_{X}W^{\otimes n}=\sum_{ij}{J}_{ij}Z_{i}Z_{j} , which is stoquastic and has no sign problem. Thus, the sign problem of H X H_{X} is efficiently curable, after which (when it is presented as H Z H_{Z} ) deciding its ground state energy remains NP-hard

Cited in the paper.