Statistical Estimation in the Spiked Tensor Model via the Quantum Approximate Optimization Algorithm

The quantum approximate optimization algorithm (QAOA) is a general-purpose algorithm for combinatorial optimization that has been a promising avenue for near-term quantum advantage. In this paper, we analyze the performance of the QAOA on the spiked tensor model, a statistical estimation problem that exhibits a large computational-statistical gap classically. We prove that the weak recovery threshold of 1 -step QAOA matches that of 1 -step tensor power iteration. Additional heuristic calculations suggest that the weak recovery threshold of p -step QAOA matches that of p -step tensor power iteration when p is a fixed constant. This further implies that multi-step QAOA with tensor unfolding could achieve, but not surpass, the asymptotic classical computation threshold \Theta(n {(q-2)/4}) for spiked q -tensors.