Average-case additive hardness of squared complex Gaussian hafnians
- Field
- Topics
Problem
Is additive estimation of squared complex Gaussian hafnians \(\#\mathrm P\)-hard under randomized polynomial-time oracle reductions? For \(n\geq1\), let \(X=X^T\in\mathbb C^{2n\times2n}\) have zero diagonal. Its entries above the diagonal are independent with density \(\pi^{-1}e^{-|z|^2}\). Let \(\mathcal M_{2n}\) be the perfect matchings of \(\{1,\ldots,2n\}\) and define
Given \(0<\varepsilon,\delta<1\), an estimator must output \(\widehat p\in\mathbb R\) with
Probability in Eq. (2) includes both \(X\) and the estimator’s randomness. The binary input is a truncated, rounded copy \(\widetilde X\). Use \(\operatorname{poly}(n,\log(1/\varepsilon),\log(1/\delta))\) bits per entry. Choose the precision so that the squared hafnians of \(X\) and \(\widetilde X\) differ by at most \(\varepsilon h_n/2\), except with probability \(\delta/2\). Reduction cost is polynomial in the binary input length, \(1/\varepsilon\), and \(1/\delta\). Here \(\#\mathrm P\) is the class of functions counting accepting paths of nondeterministic polynomial-time machines. The target normalization \(h_n\) is defined in Eq. (1).
Source
This explicit ensemble and additive normalization refine the hafnian-of-Gaussians discussion following Eq. (11) of Hamilton et al. [HKS+17]. The formulation distinguishes additive squared-hafnian estimation from multiplicative hafnian estimation; the paper does not state this precise normalized problem as a numbered conjecture.
Progress
Hamilton et al., Eq. (7), use the identity
\begin{equation} \operatorname{Haf}\begin{pmatrix}0&G\\G^T&0\end{pmatrix} =\operatorname{Per}G. \tag{3} \end{equation}Here \(G\) is any square matrix and \(\operatorname{Per}G\) is its permanent. Equation (3) transfers worst-case permanent evaluation hardness to hafnians. The block matrices in this reduction are not typical independent symmetric Gaussian samples [HKS+17].
Independence and the matching expansion give \(\mathbb E|\operatorname{Haf}X|^2=h_n\). Distinct matchings have vanishing cross terms. This elementary normalization calculation does not provide an average-case reduction at error \(\varepsilon h_n\).
Comment
The unresolved claim is average-case additive approximation hardness for independent complex entries above the diagonal. Worst-case hardness, exact average-case evaluation, and Gaussian-product ensembles \(YY^T\) do not by themselves imply it. The hafnian lower-tail question is a separate auxiliary problem, not an equivalent hardness claim.