Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices

In this work, we revisit algorithms for Tensor PCA: given an order-\(r\) tensor of the form \(T = G + \lambda \cdot v^{\otimes r}\) where \(G\) is a random symmetric Gaussian tensor with unit variance entries and \(v\) is an unknown boolean vector in \(\{\pm 1\}^n\), what's the minimum \(\lambda\) at which one can distinguish \(T\) from a random Gaussian tensor and more generally, recover \(v\)? As a result of a long line of work, we know that for any \(\ell \in \mathbb{N}\), there is a \(n^{O(\ell)}\) time algorithm that succeeds when the signal strength \(\lambda \gtrsim \sqrt{\log n} \cdot n^{-r/4} \cdot \ell^{1/2 - r/4}\). The question of whether the logarithmic factor is necessary turns out to be crucial to understanding whether larger polynomial time allows recovering the signal at a lower signal strength. Such a smooth trade-off is necessary for tensor PCA being a candidate problem for quantum speedups. It was first conjectured and then, more recently, with an eye on smooth trade-offs, reiterated in a blogpost of Bandeira.