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

We thank the reviewer for their positive comments on the importance of the algorithm and the problem under study. To make the motivation more concrete: We believe that tensor PCA is a promising avenue for demonstrating quantum advantage because the computational-statistical gap in the spiked tensor problem is huge compared to other problems. The gap here is a polynomial factor separating the required $\Omega(n^{(q-2)/4})$ SNR for the best known algorithm vs. the information-theoretically sufficient $O(1)$ SNR; compare this to a constant factor gap in many other cases such as spin-glass optimization [45]. Hence, it is reasonable to conjecture that a better (quantum) algorithm exists for this problem. Our choice of focus on the QAOA is because it is a novel quantum algorithmic primitive that is both realistic for near-term implementations and guaranteed to succeed when the algorithmic depth p grows unboundedly with problem size. We concur with the reviewer that the question of studying QAOA on tensor PCA is an important question on its own, and we will augment the justifications in the main text with the above discussion.

To answer the reviewer’s questions:

1. The idea about combining QAOA with tensor unfolding is explained in Remark 3.11, but we will elaborate further here. Essentially, upon an input spiked tensor, we partition the tensor indices into two groups to obtain a 2-tensor which is a spiked matrix that we call the unfolded tensor. We can apply the QAOA to the resultant spiked matrix, with a rescaled SNR $\bar{\lambda}_n = \lambda_n/n^{(q-2)/4}$. Additionally, our Claim 3.7 implies that as $p\to\infty$ (after taking $n\to\infty$), the QAOA can solve the spiked matrix problem with $\bar{\lambda}_n \approx 1$. This implies that the QAOA with tensor unfolding can solve the original spiked tensor problem with $\lambda_n = \Theta(n^{(q-2)/4})$ which achieves but does not surpass the classical computational threshold. Our result does not rule out the possibility that the QAOA can surpass the computational threshold when p grows unboundedly with n, or potentially in combination with a more clever trick.

2. The issue here is that the QAOA can only output bit-strings, which live on the hypercube. In practice, when the hidden prior is on the sphere, we can still run the QAOA to get an estimator on the hypercube, but this may not be very natural. Our theoretical framework can be certainly used to analyze the overlap between the hypercube estimator and the spherical prior, and we believe the result will be similar. Another potential solution for a spherical prior is to develop a variant of the QAOA for continuous variables, but this is outside the scope of our work.

We thank the reviewer for the positive comments on the novelty of our results. Regarding the weaknesses mentioned, we acknowledge that the quantum advantage is modest. Before our work, the extent of quantum advantage that the QAOA could provide on the spiked tensor problem was unknown, especially since previous hardness results did not apply in this setting. Therefore, understanding the power and limitations of the QAOA for this problem is an important step forward. While our analysis is limited to depths p that do not grow with n, this regime is also the most realistic for near-term quantum computers. Nevertheless, we agree that analyzing this algorithm at super-constant depths is an important open question worthy of future work.

In terms of generalizing our techniques to more problems, we believe our methods can be also applied to study the performance of the QAOA on other problems such as planted clique, sparse PCA, stochastic block model and Bayesian linear models, to name a few. Furthermore, by setting $\lambda=0$, our formula recovers previous results on the QAOA applied to spin-glass models (which can be seen in the derivations in Appendix D.4). This demonstrates the broader applicability of our methods beyond the specific problem studied in this paper.

To address the limitation regarding heuristics arguments, we refer the reviewer to our global rebuttal where we discuss the potential of making our derivation more rigorous. There, we also discuss additional evidence for the correctness of the heuristics (that is, the use of Dirac delta functions and interchanging order of limits), which are further corroborated by our numerical experiments.

We thank the reviewer for the positive comments on the importance of understanding the power of quantum algorithms for statistical inference problems. Regarding the weakness mentioned, we remark that our analysis and derivation of the sine-Gaussian law is completely rigorous at p=1. Additionally, for the general-p analysis, we have strong evidence supporting the correctness of our approach, not only from numerical simulation but also from the fact that our framework reproduces known rigorous results in different limits. We explain this in more detail in our global rebuttal.

Addressing the question on implementation, we remark that the QAOA is quite NISQ-friendly and has already been implemented in practice for various problems, as demonstrated for example in Refs. [16-18]. However, some limitations of noisy implementations of QAOA are known, particularly when the problem topology does not match the hardware connectivity (see e.g., [arXiv:2009.05532]). These limitations can be mitigated to some extent with simple forms of error-correction. Nevertheless, our paper is focused on the theoretical analysis of the performance and limitations of the noiseless QAOA. A detailed discussion about potential implementations on near-term quantum devices is beyond the scope of this work.

We thank the reviewer for a positive assessment of our paper. We refer the reviewer to the global rebuttal for our response regarding the weakness of using heuristic calculation. Moreover, our asymptotic results in the $n\to\infty$ limit also show good agreement with numerical experiments at finite $n$. In particular, the average squared overlap with the signal at finite $n$ appears to converge to our infinite-n prediction with order $1/n$ deviations as shown in Figure 2 and 4.

We now address the reviewer’s questions one-by-one:

1. We stress that the constant factor advantage is in fact rigorous for $p=1$ and $q\ge3$, as seen in the first row of Table 1. However, we acknowledge that the constant factor advantage seen for $p>1$ is currently not fully rigorous, and will revise our manuscript to say “conjectured advantage” in those cases.

2. We recognize that our results currently do not rigorously show an advantage for the QAOA against the state-of-the-art classical threshold. Although it is rigorously known that the QAOA can compute the MLE and (weakly) recover the signal when the depth p grows unboundedly with n, we do not rigorously know if it can do so in polynomial depths even with SNR at the classical threshold. One possible way to address this is extending previous computational universality results in Ref. [19] to show the QAOA can reproduce classical algorithms for spiked tensors within polynomial depths. Nevertheless, the scope of our present work is focused on analyzing the constant depth regime of QAOA in hopes of obtaining good performance with as little quantum resource as possible.

3. We acknowledge that the phrasing of “modest quantum advantage” may be misleading. We will revise our manuscript to more clearly indicate that this advantage is only over constant-step power iteration, which is not the best classical algorithm.

We thank the reviewer for the positive assessment of our paper and agree on the importance of studying quantum algorithms applied to the spiked tensor.

Regarding the mentioned weakness, we would like to point out that the various celebrated classical hardness results for the spiked tensor problem fall into two categories: (i) hardness for all polynomial-time classical algorithms under certain complexity-theoretical assumptions, as in Ref. [13]; or (ii) unconditional hardness results for specific families of classical algorithms, such as tensor power iteration, gradient descent, Langevin dynamics, spectral methods, and message passing algorithms (see Ref. [2-12]). Our work extends the second type of hardness results to the quantum realm by showing an unconditional limitation of a popular family of quantum algorithms on this problem.

To address the reviewer’s questions:

1. We recognize that our hardness result applies only to a specific family of quantum algorithms, but it does not rely on any assumptions. Although there is a conditional hardness result [13] that rules out all efficient classical algorithms by assuming a generalized version of the planted clique conjecture, it is unclear if this conjecture can be considered as a standard complexity assumption, especially in the quantum setting. While our result is suggestive that weak recovery for $\lambda=o(n^{(q-2)/4})$ is likely difficult for broader classes of quantum algorithms, such as low-depth quantum circuits, we do not have sufficient evidence to rule out all BQP algorithms.

2. We believe our techniques can be also applied to study the performance of the QAOA on other problems such as planted clique, sparse PCA, stochastic block models, and Bayesian linear models, among others. Furthermore, by setting $\lambda=0$, we recover previous results on the QAOA applied to spin-glass models (which is implicitly discussed in Appendix D.4). Therefore, we believe that our techniques have broader applicability beyond this paper, allowing one to study the QAOA on other problems, as well as other QAOA-like variational quantum algorithms.