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

Summary

The paper studies the performance of the Quantum Approximate Optimization Algorithm (QAOA) for a classical average case problem from high dimensional statistic: tensor principal component analysis (tPCA), which exhibits a computational-statistical gap. The paper investigates if this algorithm can achieve a quantum advantage over its classical counterparts. The paper makes progress towards this question and suggests that the answer to expect is somewhat negative (only for QAOA). The main results are 1. After 1 step of QAOA, it archives weak recovery at the same SNR threshold (up to constants) as achieved by 1 step of clssical tensor power iteration. 2. Using heuristic calculations (but not rigorously), they further showed that even after (some constant) $p$ steps of QAOA, the estimator succeeds at weak recovery at the same SNR as the tensor power iteration. This further suggests that even after using tensor unfolding, QAOA won't be able to surpass the computational threshold for this problem. 3. Along the way, they observe a sine Gaussian law for the asymptotic distribution of the overlap between the estimator (after $p$ steps of QAOA) and the ground truth. Again, this is proven for $p=1$ steps but empirically verified for $p>1$. Background: The problem is known to have a computational statistical gap. In particular, in the parameterization (1.1) taken in this paper, (a) recovery is possible whenever the SNR $\lambda \gg 1$, (b) but the threshold for efficient algorithms is known to be $\lambda \approx n^{(q-2)/4}$. Several classical algorithms including tensor unfolding, sum-of-squares, or gradient descent with landscape smoothing are known to achieve this. For iterative algorithms, such as the tensor power iteration and vanilla GD, the threshold is further away, requiring $\lambda \approx n^{(q-2)/2}$, and thus, to achieve the computational threshold either tensor unfolding (for power iteration) or landscape smoothing (for GD) is required.

Strengths

1. The paper analyzes one of the important quantum algorithms, for an important problem in high dimensional statistics to seek to answer if there is a quantum advantage. The results in the paper are suggestive that the answer to expect is negative. 2. The paper is well-written, and for heuristic claims, provided clean numerical simulations.

Weaknesses

I do not see any major weaknesses in the paper. Only a small quibble is a place in the introduction in lines 39-40 (and also in the abstract lines 1-3), where the authors present the motivation as seeking whether QAOA has superpolynomial speedup from clssical algorithms. However, I found this motivation slightly hand-wavy. I could not find enough concrete justification for why looking at (the combination of) QAOA for tensor PCA is a promising avenue for demonstrating this. If authors can make this more concrete, that would be helpful. On the other hand, just studying the performance of QAOA for tensor PCA is an important question in its own right, as very well justified in lines 40-51. The authors do make good progress towards this.

Questions

1. Could the author elaborate on how to combine QAOA with tensor unfolding? In more detail, why do the results after $p$ steps of unfolded tensors suggest that we could not surpass the computational threshold after using QAOA on unfolded almost square matrix? 2. In a non-quantum setup, a more standard is to take the prior to be uniform over a sphere. Can authors describe why it was important to take it to be uniform over the hypercube (in slightly more detail than in footnote 1)? I am just trying to understand the difficulty in the analysis if the prior was uniform over a sphere.

Rating

7

Confidence

3

Soundness

4

Presentation

4

Contribution

3

Limitations

N/A

Summary

The paper investigates the performance of the Quantum Approximate Optimization Algorithm (QAOA) on the spiked tensor model problem. The authors demonstrate that QAOA's weak recovery threshold aligns with that of tensor power iteration and show through heuristic calculations that multi-step QAOA could potentially match but not exceed the classical computation threshold. A notable finding is the sine-Gaussian law for the asymptotic overlap distribution of p-step QAOA verified by simulations, which is distinct from classical methods and suggests a modest quantum advantage. The paper employs novel techniques, including Fourier transforms, to analyze the QAOA's performance and concludes with implications for potential quantum advantage in statistical inference problems.

Strengths

- The paper prove that the weak recovery threshold of 1-step QAOA matches that of 1-step tensor power iteration, which is a new theoretical result for analyzing QAOA. - The paper uses heuristic calculations to characterize the asymptotic overlap distribution of p-step QAOA, showing that the ability is similar to the multi-step tensor power iterations. - Their proof techniques includes Fourier transform to handle exponential sums, which may be novel in the analysis of QAOA algorithms.

Weaknesses

- The results indicate that constant-step QAOA does not improve the recovery threshold beyond what is achievable by classical tensor power iteration by more than a constant factor, suggesting that the quantum advantage is modest. - The paper does not address the performance of QAOA with more circuit depths, which is an open question and could be crucial for demonstrating a strong quantum advantage.

Questions

- Could the authors explain more about the generality of their proof techniques, i.e., could their proof techniques be used in analysis for QAOA algorithms in other problem settings?

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

- The analysis for p-step QAOA (where p > 1) relies on heuristic arguments from physics, which may not be as rigorous as desired.

Summary

The quantum approximate optimization algorithm is analyzed for the spiked tensor model. Weak recovery of 1-step QAOA is rigorously shown to matche that of 1-step tensor power iteration. Heuristic calculations for p-step QAOA matche that of p-step tensor power iteration.

Strengths

There have been many works on tensor revorery fro such statistical models within classical inference. A very small number of works have attacked the quantum algorithmic aspect. This paper is therefore very welcome. The results are interesting and clearly expalined. Weak recovery of 1-step QAOA is rigorously shown to matche that of 1-step tensor power iteration. Heuristic calculations for p-step QAOA matche that of p-step tensor power iteration. the paper argues that that multi-step QAOA with tensor unfolding could achieve, the asymptotic classical computation threshold of spiked q-tensors. The asymptotic overlap distribution for p-step QAOA is characterized and some sort of sine-Gaussian law is observed (through simulations).

Weaknesses

For p-step QAOA the analysis is not rigorous. The observation of the intriguing sine-Gaussian law is numerical. Further analysis will be needed.

Questions

Maybe authors could discuss the limitations of implementing such algorithms on NISQ devices ? Any realistic prospects ?

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

Maybe authors could discuss the limitations of implementing such algorithms on NISQ devices ? Any realistic prospects ?

Summary

This submission proposed to use quantum approximate optimization algorithm (QAOA) to compute the maximum likelihood estimator in the statistical estimation problem of the spiked tensor model. Using the overlap between the estimated vector and the original vector, the author(s) obtained rigorous analysis for the so-called weak recovery threshold for 1-step QAOA. Namely, above such a threshold, the overlap will be non-zero with non-trivial probability; otherwise, the overlap will vanish with high probability. The author(s) also showed that the established weak recovery threshold matches the 1-step tensor power iteration classical algorithm. For the p-step QAOA, the author(s) also obtained the weak recovery threshold based on some heuristic argument, which also matches that of the p-step tensor power iteration algorithm. Numerical experiments show that the QAOA method could achieve the state of the art threshold by combining with tensor unfolding (a technique used in the state of the art algorithm). As far as I know, the submission proposed a new technical analysis for QAOA (by showing that the overlap exhibits an asymptotic sine-Gaussian distribution), providing a rigorous study of the polynomial-time QAOA. As such, I believe the work is worth sharing to the community. Hence, I recommend accept. (I did not have enough time to check all the derivations provided in appendices in details, but the overall proof ideal seems logical to me.)

Strengths

1. Rigorous analysis for the 1-step QAOA, rigorous analysis for the p-step tensor power iteration, and detailed comparison between the two algorithms. 2. Discovering an intriguing sine-Gaussian law also verified through numerical simulations. 3. The manuscript is well written and explained.

Weaknesses

1. The asymptotic analysis requires the number of qubits n approaching infinity, which is practically demanding. 2. The analysis of the p-step QAOA is based on an heuristic calculation. 3. It is not known if QAOA could achieve the same threshold as in the state of the art classical algorithm. Numerical experiments do provide some potentials of matching the result. Whether there is a quantum advantage remains unclear.

Questions

1. In Remark 3.10, the author(s) claimed that for certain parameter p, the QAOA has a constant factor advantage over the classical power iteration algorithm in the overlap achieved. The overlap via the p-step tensor is proved in Proposition 3.9. However, the overlap via QAOA given in (3.12) is based on heuristic calculations. Hence, I'm not sure such an advantage is rigorous. If I did not misunderstand anything, the wording of claiming the constant factor advantage needs to be modified. 2. In Discussion, the author(s) asserted that "This implies that achieving a strong quantum advantage via the QAOA requires using a number of steps p that grows with n." I understand that multiple (possibly infinite many) steps is needed to achieve a better performance for QAOA. However, it is still not analytically evident if QAOA can match the state of the art threshold, because a heuristic calculation is required in the analysis. Hence, whether there is a rigorous advantage for QAOA still remains unclear to me, even p approaching infinity. 3. As above, even if author(s) can rigorously show that p-step QAOA outperforms the p-step tensor power iteration, it probably not accurate to call it a "modest quantum advantage", since the p-step tensor power iteration is not the state of the art algorithm. I highly recommend the author(s) to be more careful about the phrasing of quantum advantage throughout the paper.

Rating

8

Confidence

3

Soundness

3

Presentation

4

Contribution

3

Limitations

The limitations are addressed in the manuscript. I also summarized them in Weaknesses. Yet, since this submission is a theory work, I think the practical limitation is not a big concern.

Summary

This paper studies the performance of 1-step and multi-step quantum approximate optimization algorithm (QAOA) for spiked tensor problem. In this problem one observes a q-dimentional tensor which is a properly normalized linear combination of q-th tensor power of unknown vector $u \in \{+1, -1\}^n$ and Gaussian noise $W$: $\lambda u^{\otimes q} / n^{q/2} + 1/sqrt(n)\cdot W$. The goal is to recover the unknown vector $u$ from the observed tensor. This problem is known to be statistically solvable for $\lambda > T$, for some absolute constant T; however, it is known that under common complexity assumption, the problem has polynomial time classical algorithm only for $\lambda = \Omega(n^{(q-2)/4})$, providing a complexity gap. This paper studies whether a specific family of quantum algorithms, called QAOA, can achieve a quantum advantage compared to classical algorithm. The paper proved negative result showing that constant-step QAOA applied to weak recovery problem in the spiked tensor model only achieves non-trivial overlap with the signal u when $\lambda = \Omega(n^{(q-1)/2})$ which nearly matches the threshold for the tensor power classical algorithm.

Strengths

The spiked tensor problem is a well-studied problem with important application, hence, understanding the performance of quantum algorithms applied to this problem is an interesting problem. To the best of my knowledge, this is the first paper that studies the performance of QAOA applied to this problem, showing that this family of quantum algorithms does not achieve an advantage over classical algorithms. The proofs are quite technically involved and combine techniques such as the discrete Fourier transforms and the central limit theorem to handle combinatorial summations. I have not checked the proofs carefully, but skimming through them they look sound. The authors provide a good overview of the prior work and clearly compare the current paper to prior results.

Weaknesses

I think that the contribution of this paper is somewhat limited in the sense that negative result is obtained only for a very particular family of quantum algorithms, which does not rule out that even small modifications can achieve quantum advantage for this problem. This is in contrast to classical results where gap is established for any classical algorithm under some standard complexity assumptions.

Questions

1) Do authors expect that under some standard assumptions, any BQP algorithm is not able to recover $u$ for $\lambda =o(n^{(q-2)/4})$? 2) Do you see other candidate problems where techniques developed in this paper can potentially be used to study the performance of QAOA?

Rating

7

Confidence

3

Soundness

3

Presentation

4

Contribution

3

Limitations

na