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.