# Quantum Physics

[Submitted on 29 Feb 2024]

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

View PDFAbstract:The quantum approximate optimization algorithm (QAOA) is a general-purpose algorithm for combinatorial optimization. In this paper, we analyze the performance of the QAOA on a statistical estimation problem, namely, the spiked tensor model, which exhibits a statistical-computational 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 classical computation threshold $\Theta(n^{(q-2)/4})$ for spiked $q$-tensors.

Meanwhile, we characterize the asymptotic overlap distribution for $p$-step QAOA, finding an intriguing sine-Gaussian law verified through simulations. For some $p$ and $q$, the QAOA attains an overlap that is larger by a constant factor than the tensor power iteration overlap. Of independent interest, our proof techniques employ the Fourier transform to handle difficult combinatorial sums, a novel approach differing from prior QAOA analyses on spin-glass models without planted structure.

Current browse context:

quant-ph

### References & Citations

# Bibliographic and Citation Tools

Bibliographic Explorer

*(What is the Explorer?)*
Litmaps

*(What is Litmaps?)*
scite Smart Citations

*(What are Smart Citations?)*# Code, Data and Media Associated with this Article

CatalyzeX Code Finder for Papers

*(What is CatalyzeX?)*
DagsHub

*(What is DagsHub?)*
Gotit.pub

*(What is GotitPub?)*
Papers with Code

*(What is Papers with Code?)*
ScienceCast

*(What is ScienceCast?)*# Demos

# Recommenders and Search Tools

Influence Flower

*(What are Influence Flowers?)*
Connected Papers

*(What is Connected Papers?)*
CORE Recommender

*(What is CORE?)*# arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? **Learn more about arXivLabs**.