Research map / Learning theory and algorithms / Matrix and tensor methods
Statistical Estimation in the Spiked Tensor Model via the Quantum Approximate Optimization Algorithm
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Analyzes QAOA for weak recovery in the spiked tensor model, proving 1-step QAOA matches 1-step tensor power iteration's threshold, deriving a sine-Gaussian overlap law, and giving heuristic results for p-step QAOA.
Problem
Whether the Quantum Approximate Optimization Algorithm can weakly recover the signal in the spiked tensor model at SNR thresholds below the best classical polynomial-time threshold, given the computational-statistical gap.
Approach
Analyzes p-step QAOA on the MLE cost of the spiked tensor model, computing the expected moment-generating function of the overlap and using a discrete Fourier transform to linearize exponents in combinatorial multinomial sums; this yields a sine-Gaussian overlap law and shows QAOA matches tensor power iteration's threshold.
Key results
- 1-step QAOA weak recovery threshold is Theta(n^{(q-1)/2}), matching 1-step tensor power iteration, with overlap converging to sin(2beta)e^{-2q gamma^2} sin(2q Lambda gamma G^{q-1}) in distribution.
- Quantum enhancement factor over power iteration of up to q/e for 1-step QAOA (optimal at gamma=1/(2 sqrt q), beta=pi/4), so QAOA beats power iteration for q>e.
- Heuristic p-step QAOA threshold is n^{(q-2+eps_p)/2} with eps_p=(q-2)/((q-1)^p-1), matching p-step power iteration; QAOA with tensor unfolding heuristically reaches n^{(q-2)/4}.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use 1-step QAOA instead of 1-step tensor power iteration | Spiked q-tensor weak recovery · Spiked q-tensor | SNR threshold: Θ(n^{(q-1)/2}) vs Θ(n^{(q-1)/2}) | No clear effect |
| Use p-step QAOA instead of p-step tensor power iteration | Spiked q-tensor weak recovery · Spiked q-tensor, fixed p | SNR threshold: Θ( n^{(q-2 + ε_p)/2}) vs Θ(n^{(q-2 + ε_p)/2}) | No clear effect |
| Use 1-step QAOA rather than tensor power iteration | Spiked q-tensor, small Λ · Spiked q-tensor with q > e | Squared overlap: q / e | Helped |
| Use 1-step QAOA rather than tensor power iteration | Spiked q-tensor, small Λ · Spiked q-tensor with q=2 | Quantum enhancement factor: 0.8578 | Hurt |
| Use 1-step QAOA rather than tensor power iteration | Spiked q-tensor, small Λ · Spiked q-tensor with q=3 | Quantum enhancement factor: 1.0505 | Helped |
| Use 1-step QAOA rather than tensor power iteration | Spiked q-tensor, small Λ · Spiked q-tensor with q=4 | Quantum enhancement factor: 1.2131 | Helped |
| Add a fraction k/n of signal-biased qubits to the initial state | 1-step QAOA · Spiked q-tensor weak recovery with side information | SNR threshold: Θ(n^{(q-1)/2}) -> Θ(n^{(1-c)(q-1)}) | Helped |
| Add a signal-biased initialization with k = Θ(n^{3/4}) | 1-step QAOA · Spiked q-tensor weak recovery with side information | SNR threshold: Θ(n^{(q-1)/2}) -> Θ(n^{(q-1)/4}) | Helped |
| Apply tensor unfolding before QAOA | QAOA weak recovery · Spiked q-tensor, even q | SNR threshold: Θ(n^{(q-2 + ε'_p)/4}) | Helped |
| Increase p-step QAOA depth | QAOA with tensor unfolding · Spiked q-tensor, even q | SNR threshold: Θ(n^{(q-2 + ε'_p)/4}) -> Θ(n^{(q-2)/4}) | Helped |
| Classically simulate p-step QAOA at depth p≥3 rather than p≤2 | p-step QAOA simulation · Spiked tensors with q=2,3 | Overlap distribution agreement with theory | Hurt |
Surprising findings
- The QAOA overlap distribution does not concentrate over quantum measurements, in contrast to prior spin-glass QAOA results, suggesting negative hardness results may not transfer.
- Rounding the power iteration estimator to signs does not improve the threshold exponent and reduces overlap.
Limitations
- Results for p>1 rely on non-rigorous physics heuristics (Dirac delta and Fourier linearization).
- Numerical simulations limited to n<=26 qubits due to O(2^n) classical simulation cost.
Experimental setup
Metrics: weak recovery threshold expected squared overlap overlap distribution
Baselines: tensor power iteration matrix power iteration with tensor unfolding
Builds on: QAOA tensor power iteration
Closest papers by meaning
- Sublinear Time Quantum Sensitivity Sampling (NeurIPS 2026 · similarity 0.87)
- TensorRL-QAS: Reinforcement learning with tensor networks for improved quantum architecture search (NeurIPS 2025 · similarity 0.87)
- Optimal algorithmic complexity of inference in quantum kernel methods (NeurIPS 2026 · similarity 0.86)
- Score-based Variational Inference via Quantum Maximally Mixed States (NeurIPS 2026 · similarity 0.86)
- A Sub-Problem Quantum Alternating Operator Ansatz for Correlation Clustering (ICML 2025 · similarity 0.86)
- Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functions (ICML 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.