Average-case approximation hardness of random Ising partition functions
- Field
- Topics
Problem
Is it \(\#\mathrm{P}\)-hard to approximate \(|Z_R|^2\) to relative multiplicative error \(a+o(1)\) on a \(b\) fraction of random Ising instances? Here \(a>0\) and \(0<b\leq1\) are constant parameters independent of the number of vertices \(n\), specifying the relative error and instance fraction.
Take the complete graph on \(n\) vertices. Choose each edge weight \(w_{ij}\) and each vertex weight \(v_k\) independently and uniformly from \(\{0,\ldots,7\}\). With \(\omega=e^{i\pi/8}\), define
The target is the squared modulus of Eq. (1). An estimate \(\widetilde Q_R\) is required to satisfy
The \(b\) fraction in the question is measured over the random vertex and edge weights for which Eq. (2) holds; \(o(1)\) tends to zero as \(n\to\infty\).
Source
Conjecture 2 of Bremner, Montanaro, and Shepherd, on page 2 of arXiv v2, states this average-case hardness conjecture with \(a=1/4\) and \(b=1/24\) [BMS16]. The present formulation replaces those two numerical constants by the parameters \(a\) and \(b\), as requested by the contributor, and retains the original \(o(1)\) term, random-instance distribution, and squared-modulus target. The parameterized formulation is not a verbatim claim of the paper.
Progress
Reports do not certify correctness or automatically change the problem's status. Progress policy.
None
Comment
The remaining task is an average-case hardness result for the specified random-weight distribution and relative-error guarantee. The pair \((a,b)\) indexes a family of questions; hardness for every pair is not asserted. The source’s original parameter choice is \((a,b)=(1/4,1/24)\). The instance fraction \(b\) concerns inputs, not an algorithm’s internal success probability.