  We consider the problem of estimating an unknown parameter vector
${\boldsymbol \theta}\in{\mathbb R}^n$, given noisy observations ${\boldsymbol
Y} = {\boldsymbol \theta}{\boldsymbol \theta}^{\top}/\sqrt{n}+{\boldsymbol Z}$
of the rank-one matrix ${\boldsymbol \theta}{\boldsymbol \theta}^{\top}$, where
${\boldsymbol Z}$ has independent Gaussian entries. When information is
available about the distribution of the entries of ${\boldsymbol theta}$,
spectral methods are known to be strictly sub-optimal. Past work characterized
the asymptotics of the accuracy achieved by the optimal estimator. However, no
polynomial-time estimator is known that achieves this accuracy.
  It has been conjectured that this statistical-computation gap is fundamental,
and moreover that the optimal accuracy achievable by polynomial-time estimators
coincides with the accuracy achieved by certain approximate message passing
(AMP) algorithms. We provide evidence towards this conjecture by proving that
no estimator in the (broader) class of constant-degree polynomials can surpass
AMP.
