Statistical Estimation in the Spiked Tensor Model via the Quantum Approximate Optimization Algorithm
Authors: Leo Zhou
Joao Basso
Song Mei
Venue: NeurIPS 2024 spotlight (2024)
Keywords: quantum algorithm
statistical estimation
computational complexity
computational-statistical gap
optimization
variational quantum algorithm
quantum machine learning
statistical physics
average-case complexity
Primary area: learning_theory
TL;DR: This paper analyzes the QAOA for the spiked tensor model, showing that while it matches classical performance at constant depths, it exhibits qualitative differences and a limited quantum advantage, indicating potential for future quantum speedups.

Abstract: 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. This further implies that multi-step QAOA with tensor unfolding could achieve, but not surpass, the asymptotic classical computation threshold $\Theta(n^{(q-2)/4})$ for spiked $q$-tensors. 
Meanwhile, we characterize the asymptotic overlap distribution for $p$-step QAOA, discovering an intriguing sine-Gaussian law verified through simulations. For some $p$ and $q$, the QAOA has an effective recovery threshold that is a constant factor better than tensor power iteration.
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.

Statistical Estimation in the Spiked Tensor Model via the Quantum Approximate Optimization Algorithm
Leo Zhou
Walter Burke Institute for Theoretical Physics and the IQIM California Institute of Technology. Pasadena, CA 91 125 Electrical and Computer Engineering Department University of California, Los Angeles, CA 90095 leoxzhouducla. edu
Joao Basso
Department of Mathematics University of California, Berkeley, CA 94720 Quantum Artificial Intelligence Lab (QuAIL)
NASA Ames Research Center, Moffett Field, CA 94035
Research Institute for Advanced Computer Science (RIACS)
USRA, Mountain View, CA 94043
joao basso@berkeley. edu
Song Mei
Department Statistics and Department of EECS University of California, Berkeley, CA 94720 songmei@berkeley. edu
Abstract
The quantum approximate optimization algorithm (QAOA) a general-purposs algorithm for combinatorial optimization that has been promising avenue for near-term quantum advantage. In this paper, we analyze the performance of the QAOA the spiked tensor model, statistical estimation problem that exhibits large computationallstatie atatttiiio 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 fixed constant. This further implies that multi-step QAOA with tensor unfolding could achieve, but not surpass, the asymptotic classical computation threshold (9n(4-2))4) 2)/4) for spiked q-tensors. Meanwhile, we characterize the asymptotic overlap distribution for p-step QAOA, discovering an intriguing sine-Gaussian law verified through simulations. For some p and q. the QAOA has effective recovery threshold that is constant factor better than tensor power iteration. Of independent interest, our proof techniques employ the Fourier transform handle difficult combinatorial sums, novel approach differing from prior QAOA analyses on spin-glass models without planted structure.
1 Introduction
We study statistical estimation in the spiked tensor model, where we observe a g-tensor E R= in n² dimensions given by
Y (2n/n3/2) u (1/vm) W E T
(1.1)
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Here u ~ Unif((+1,-11" is some hidden signal and and W E (R") noise noise tensor whose entries
are i.i.d, standard Gaussian (O 1). The parameter X, > 0 is the signal-to-noise ratio (SNR). The goal is to estimate u given only access to Y. That is, we seek an estimator u: (IR*) + - -n (vn)
achieving nontrivial overlap with the signal:
Inm ionin ((()) /n² 0.
(1.2)
This task is known as weak recovery in the spiked tensor model.
The spiked tensor model is famous problem because it exhibits huge computational-statistt gap, referring to regimes of SNR where the statistical estimation problem is information-theorrooiialll solvable, but no efficient algorithm has been found. For example, it is known that the Bayes optimal estimator achieves non-trivial overlap with the signal u when A, > Arr for some constant threshold -thoorttiilttrrrrilllllll impossible when An S Arr M.
ArT = (1), whereas the problem is Furthermore, the maximum likelihood estimator also achieves non mon-trivial overlap with the signal when A, AMLE for some AMLE- (1). However, the best-known polynomial-time classical algorithms for computing non-trivial estimator require much higher SNR of X, These include tensor power iteration, gradient descent, approximate message passing, and spectral methods with tensor unfolding 12 Indeed, assuming the secret leakage planted clique conjecture, Ref. [13] proves an ((n lower bound the SNR needed by any polynomial-time classical algorithm. See Fig. I for an illustration of the different SNR thresholds and Section 2.1 background.
for more
On the other hand, quantum algorithms are widely believed have computational advantages over classical algorithms for many problem classes. In particular, we focus on the Quantum Approximate Optimization Algorithm (QAOA) 14. general- purposs quantum optimization algorithm that can be applied to optimize any objective function on bit-strings. The QAOA has received an enormous amount of attention in the quantum computing community for several reasons. First, the QAOA is simple and allows efficient implementation on near-term quantum hardware with many applications [1519]. Additionally, the QAOA is computationally universal [20). and its generalization can realize other powerful algorithms such as the quantum singular value transform [21]. Under common complexity-theoret assumptions, no classical device can efficiently simulate the output distribution of the QAOA even at shallow depth [22 23 Furthermore, the QAOA is guaranteed to find optimal solutions when its number of steps (or depth) diverges [4]. Nevertheless, analyzing the asymptotic performance of QAOA remains challenging: classical simulation of the algorithm is limited to small
problem dimension n. and analytical computations are often highly non-trie non-trivial 24 28
Given the
enormous (4 21/4) computational-stann staatsssiia gap in the spiked tensor model (compared to e.g., the constant factor gap in spin-glass optimization [29]) ), it is interesting open question whether the QAOA, as a realistic quantum algorithm with asymptotic convergence guarantees, can provide any computational advantages.
In this work, we investigate the performance of QAOA for the spiked tensor model. In particular, we choose the log-likelihood objective of spiked tensor C(z) the maximum likelihood estimator, achieves non-trivial overlap with the signal whenever An > AMLE (L). While the infinite-step QAOA could compute the maximizer, we are interested in the performance of QAOA when the depth is polynomial in the problem size, and hope that it can surpass the (--1/4) classical threshold. Although some limitations of the QAOA are known for certain random optimization problems in the low-depth regime 26 32 these negative results do not apply to the spiked tensor model since they rely on either sparse connectivity or concentration, both of which are absent the current setting. Here, as a first attempt to bridge the gap understanding how well popular quantum algorithm may perform on classically hard statistical estimation problem, we study the asymptotic behavior of the QAOA on the spiked tensor model in the constant-depth regime, where we are able to obtain rigorous and analytical results.
2/229//n11-22) Its maximizer,
Our contribution. In this paper, we analyze the signal-to-noise ratio threshold of p-step QAOA for weak recovery in the spiked tensor model, in the regime of fixed p and n approaching infinity. For p= = 1, we prove the weak recovery threshold is X, = ()n(2-))/2 matching that of 1-step tensor power iteration. For p > 1, heuristic calculations suggest the threshold is An = ((n(9 2(tm)/)))))
Another commonly studied prior is the uniform distribution over the n-sphere, Unif(5 In this work, choose the Rademacher prior for the convenience of the QAOA analysis.

---

(q 2)/4
(q - 2)/2
(q - 1)/2
log 2, /log n
informution-thooeee threshold
Classical computational threshold. Threshold spectral algorithm and multi-step QAOA with tensor unfolding
Multi-step tensor power iteration and multi-step QAOA
1-step tensor power iteration and 1-step QAOA
Figure 1:
Different thresholds for the spiked tensor model.
where Ep (q 2)/((q 1)p 1]. again matching p-step tensor power iteration. Additionally, given an initialization vector with n² /n correlation to the signal for 1/2 < c < 1, we prove the weak recovery threshold for 1 1-step QAOA A, = ((n(1=o((-1)), identical to 1-step tensor power iteration. These results indicate that constant-step QAOA has the same asymptotic recovery threshold as tensor power iteration in the spiked tensor model. Meanwhile, further heuristic analysis suggests that QAOA with tensor unfolding could achieve the classical computation threshold (1-244))
Furthermore, we derive the asymptotic distribution of the overlap for p-step QAOA, revealing an intriguing Sine-Gaussian law distinct from p-step tensor power iteration. Analyzing the second moment, we see that, for certain (p. 9) pairs, the QAOA effectively has recovery threshold that is constant factor better than tensor power iteration. Since there are classical algorithms that achieve better recovery thresholds than power iteration, it remains interesting open question whether quantum advantage over the state-of-the-ar classical algorithms may be obtained at larger QAOA depths that grow with system size. To our current knowledge, our work is the first to obtain analytical results using the QAOA for statistical inference problem.
The proof of the sine- Gaussiaa distribution adopted novel techniques, including using discrete Fourier transforms and the central limit theorem handle combinatorial summations. The Fourier transform technique also allows us to replace nonlinear polynomials in the exponents with dual variables, leaving linear exponents that become easy combinatorial sums. These techniques are of independent interest and could be useful for analyzing the QAOA in other models.
2
Background and related work
2.1 Spiked tensor model and prior algorithms
The spiked tensor model was first introduced as statistical model for tensor principal component analysis [2], where it was studied with spherical prior u E S"~1(vVi The information -ithoriin--thorettic threshold for weak recovery under this model with the spherical prior prior u E [=1]" are both An = O11)
and the Rademacher
Tensor power iteration. A well-studied classical algorithm for the spiked tensor model is tensor power iteration [2] [T] [3]. Starting from a uniform random initialization úo ~ Unif(S"-1), the k-th iteration is given by üg where
1(0-1) i n ( k-1
| 111 A 2 1, io Unif(S"-1).
(2.1)
Here, Y 11 ((--1) E R.T denotes contracting the order-q tensor Y E R= with the order-(q - 1) tensor á (gg-1) 1) R .- It is shown that with (log n) iterations, weak recovery is possible if the SNR satisfies X, 1( (1-)21-2)/2 22/22 ppolylognn) [10 33]. However, tensor power iteration does not match the best- classical algorithms. Furthermore, we remark that rounding the tensor power iteration to sign( ( E {+1}" does not give better threshold.
Other classical algorithms and related results.
2 showed that the tensor power iteration and approximate message passing algorithms with random initialization recover the signal provided Xn (nn(9-1)/2) This SNR threshold was later improved to Xn ( by 3 10 K3]
for these same methods. The same threshold An ()n(9-2)22) could also be achieved by gradient

---

descent and Langevin dynamics as proved in 1. On maximum likelihood estimation for the spiked tensor model with spherical prior, [3] 6 studied the loss landscape, providing intuition that contains many saddle points and local minima near the equator, but no bad critical points off the equator.
The best currently known polynomial-ting algorithms can achieve a sharp threshold of A = (nn(1-2)44) These include spectral methods with tensor unfolding [I), sum-of-squares algo- rithms
34 36.. sophisticated iteration algorithms 37 39]. and gradient descent on the smoothed
landscape 40 41
Another line of research has attempted to prove computational lower bounds in restricted computa- tional models, including low-degree polynomials and statistical query algorithms 42 43
Under the secreted leakage planted clique conjecture, [13] proved that any classical polynomial-timg time algorithm requires An (2nn(9-2)/4 for weak recovery of the signal.
quantum algorithm by Ref. (4). To the best of our knowledge, the only prior quantum algorithm proposed for the spiked tensor model with provable guarantees is by Hastings in Ref. [44.. Hastings' algorithm is based on a spectral method for a Hamiltonian on M bosons over n modes, living in a Hilbert space of dimension nM where M > (g(9-2)/4 /Ax] (/((//))) 2) x polylog(n). Finding the dominant eigenvector of this Hamiltonian allows for weak recovery in the regime where X..
()/44-))44) In this regime, where M = 2(polyyog n),, the standard classical matrix power iteration algorithm can extract the dominant eigenvector and recover the signal in Ö(n") time. For the proposed quantum algorithm, Ref. 44 uses combination of quantum phase estimation, amplitude amplification, and clever state initialization to recover the signal Om///4) time, achieving a quartic speedup. (A few months after our paper appeared online, a related work (45] emerged, simplifying Hastings' algorithm and generalizing it to another planted inference problem.)
We remark that Hastings' algorithm runs in superpolynomial time n (pooyylog and does not improve over the asymptotic computational threshold in SNR for recovery (although a constant factor im- provement is possible). For comparison, the classical spectral method based on tensor unfolding I1 achieves recovery when An > n2 in polynomial time ((poly(n2)) In this work, we study the QAOA in the constant-step regime, where the gate complexity grows only linearly in the problem size O(n9).
2.2 Quantum approximate optimization algorithm
The quantum approximate optimization algorithm (QAOA) was introduced by 14] as a quantum algorithu for finding approximate solutions to combinatorial optimization problems. The QAOA can be applied to optimize any cost function on bit-strings, C: {+1)² + R. In the spiked tensor model, consider optimizing the log-likelihood function given by
ÚM, arg max a aE(=1)= a {clo)= (Y, (Y, *0) ///n0
(2.2)
The maximum likelihood estimator ûMLE achieves non-trivial correlation with the signal when An > AMLE for some constant AMLE = (1). However, classical algorithms cannot efficiently compute the MLE unless An = 9 2)/4) [13.. This paper investigates whether QAOA could compute ÚMLE, or an approximate estimator, for smaller values of Xn
The inputs to the QAOA algorithm are a cost function C {+1)" + IR and parameter vectors 7. E R". The initial QAOA state [s) = 2-n/2 Σ2 |2) is the rescaled all-one vector 2- 2~n/21gm E C²", assigning equal probability to measuring each possible bit-string upon quantum measurement. See Appendix for review of quantum computing terminology, where we also define the Pauli operators {XR,, Ys. ]k acting on the k-th qubit. The cost function C' associates with a 2" x 2" diagonal matrix, where the 1='th diagonal gives C(z). For the spiked tensor model with cost function
C(z)= (Y, (n(n)//nn))))))))) 22/2 this matrix is C =1 Ysr..., Zi ... Zg/n' (2-22/2 E C² x2" Letting B Σj=,, X, x22 for any parameter (y, the unitary matrices _ ee
C² x2" are matrix exponents of - C and B. Given 7, E IRP, the p-step QAOA state is
hr 18, B -i, ...e 18, B in - E C²"
(2.3)

---

One can verify 17 is a unit vector since (s) E C²" is unit and e BB E x2" and e e-i E C x2" are unitary matrices. After preparing the quantum state 17, QAOA samples a bit string ~ 33 in [+1]" by quantum measurement. In our main results, we will analyze the distribution of the overlap Roson of this quantum measurement 2 with respect to the signal u:
RoADa = = uu/n
2 E 1-1,]]
(2.4)
For any function f(z) = Ex=o Egrr S6) fn ... 2/a its expectation under the QAOA state 1) is given by (f. (, 3). where (r, Clx2" is the conjugate transpose of 13, C xI, and f(Z) = Σx E Einn sil fn Zn ... Zi. E R2" x2" for Pauli-Z matrices Zz. To simplify the notations, we denote (1 by the expectation with the quantum measurement from ,,, that
(f(Z))> (1,8)
(2.5)
In the main theorems of this paper. we will focus the second moment of the overlap of QAOA, denoted (RoAos),,a
B Iy, B), where R = 1> u.Zi- We defer further related literature on theoretical analyses of the QAOA to Appendix A.2
In terms of experimental realizations, the QAOA has been implemented in quantum computing platforms such as trapped ions [T6] [9], superconducting qubits (17), and neutral atoms [8], for optimization problems with up 179 bit variables. Implementing the QAOA for the spiked tensor model, however, poses additional challenges due to the all-to-all connectivity in its cost function, leading to higher overhead in the number of quantum gates and circuit compilation costs. Cur- rently, the largest experimental implementations for problems with dense connectivity include 17-bit Sherrington- Kirkpaarrik spin-glass models superconducting qubits [17), and 18-bit LABS problem on trapped-ion quantum processors [9]. We expect larger problems can be implemented as quantum hardware matures, but quantum error-correction is likely necessary observe any quantum advantage at scale [46)
Main results
3.1
Weak recovery threshold and overlap distribution for 1-step QAOA
We first consider the general 1-step QAOA for weak recovery in the spiked tensor model. Consider the (ni and the 1-step QAOA quantum
spiked tensor model Y [1.Ib with planted signal
state (Yr (x) = e 1/,, 13 e Cns quantum state Iire B.) depends randomly on Y through C(o) = (Y,
(see Section 2.2) with parameters (Th. Px) E R>o x [0, 2n.. The
results characterize the distribution of the overlap RQAOA à T (Y/ (0) (n-2))2 Our main and the signal vector u.
2)
u/n between sample á IT,, Br)
Theorem 1 (Weak recovery threshold and overlap distribution for 1-step QAOA). Consider the spiked tensor model [77) and the 1-step QAOA overlap as defined above. Then the following hold.
(a) Take any sequence of (7/ In21 C RR (3x)221 S [0, 2m). and any sequence of (va Anini1 E
[0, oo) with lim An/n (1-122 1)/2 = O. We have
lim Ey
0.
(3.1)
(b) Take any sequence of (ri hm21 (Bulnz and (nn which satisfies
lim (Tas Bay >n/n (9- 11/2) = (7, n++00
(3.2)
Then, over the randomness of Y and the quantum measurement, the overlap RoaoA of the sine- Cane-Gasssian law as
1- 1-step QAOA converges distribution
_ - sin( sin(2g where G ~ N(O,, 1).
RQAOA
(3.3)
(c) As corollary (b), under the asymptotic limit of 3.2 with A > 0, 7 > 0, and $3 & (kTT/2
i E Z),, we have
lim Ey (o 0.
(3.4)
n
5

---

The full proof of Theorem is contained in Appendix
Remark 3.1 (Weak recovery threshold). Theorem I () implies that when X. = ((n(9-1)/2), the overlap will be non-zero with non-trivial probability over both the random draw of the tensor and the quantum randomness. In contrast, Theorem [[a] shows that when A o(n/1-11))/01 the overlap will be zero with high probability. This establishes that X, ((n 1) is the weak recovery threshold of 1-step QAOA in the spiked tensor model.
Remark 3.2 (Overlap distribution). Theorem D does not show that the overlap distribution for a typical instance Y converges to the same Line-Gaussial law. In Section 4 we perform numerical simulations that provide evidence that the overlap distribution will concentrate over the random draw of Y, which would imply that the overlap distribution is indeed sine- nae-GGassiin for any typical Y.
Comparison with classical tensor power iteration. The 1-step tensor power iteration estimator
(Eq. (2.1) is redefined here for the reader's convenience: én ynY [ 1) / [ 009- "1]2 where ing Uni a random initialization vector. In the following proposition, we show that the weak recovery threshold for the 1-step power iteration estimator is also A,, = (--1/2)) and
we provide the distribution of the overlap Rp1 = ú u/n between the power iteration estimator ú and the signal
Proposition 3.3 (Weak recovery threshold for 1-step tensor power iteration). Assume that the rescaled signal-to-noise ratio has a limit mim >a/n(9-1)/2 = A. Then over the randomness of W and initialization in the overlap RpI of the power iteration estimator with the signal converges in distribution to
Rp d sin (ar)tanAAG*))), where G ~ ~N((
(3.5)
As a corollary, when lima- An 1n/n(9-1)/2 1)/2 0, we have Ryi P O.
The proof of Proposition 3.3 is contained in Appendix H.I
Remark 3.4 (Comparing the overlaps). Theorem | and Proposition 3.3 show that both 1-step QAOA and 1-step power iteration have the same weak recovery threshold X,, = ((n(9-1)/2). To compare the two algorithms more precisely, we take the limit lim,- \n/n/0-11/2 A for some small A > 0. Eq. (3.3) and Eq. (3.5) give the limiting squared overlap distributions for 1-step QAOA and 1 Itstep power iteration, respectively:
lim A 2 lim Ey (R A-0
(R = 40 4922² sin? -.-
n-000
(3.6)
lim - lim Ey [2] E0 G G2n-2.. A-0
n00
This gives
max lim lim Ey (y // By [Riil] -47 400 2y 7 (28.) = q/e, (3.7)
7
A- n=
where the maximizer is (,,,8,) = ( 2 4/4). Thus, for g > 1-step QAOA gives better overlap
than 1-step power iteration.
Remark 3.5 (Rounding via sign( ( will not improve the overlap). The readers may wonder whether the overlap of tensor power iteration will improved by rounding the estimator via ū = sign((1) e (+1]", outputting an estimator in the signal space. Defining RPi = u. u/n, it straightforward to show that as lim An/n(9-1 1)/2 A.
RpT d (AG where G ~ NN 1), (() = P PZ~ () 1 1.
(3.8)
Hence, the computational threshold has the same exponent by rounding, but the overlap becomes smaller:
lim - lim Ey P (2/T) EG-M((.1) [G
(
(3.9)
A
Remark 3.6 (Sine-Gaussian law versus sine-arctan-Gausse law). The sine-Gaussian law of QAOA is particularly interesting in that the overlap will not concentrate as A + co. Instead, it will satisfy a sine-uniform distribution, i.e., 2 و sUn( for U Unif((0, 2nr)). In contrast, the sinc-arctan- Gausssin law of tensor power iteration will concentrate at {+1} as A +

---

we also study the scenario where prior information about the signal may be leveraged to recover the signal with a smaller SNR. There, we rigorously analyzed the 1-step QAOA applied to boost the signal in weak estimator in Theorem 2 and compared it classical power iteration in Proposition F.2 Our result shows that the 1-step QAOA has the same asymptotic computational efficiency as 1-step power iteration, albeit with a constant-factor better overlap in the A < 1 regime when q > e.
In Appendix [
3.2
Weak recovery threshold and overlap distribution for p-step QAOA
We next consider the general p-step QAOA for weak recovery in the spiked tensor model. Although it is known that the QAOA is able to output the MLE that weakly recovers the signal when p grows unboundedly with n, here we focus on more analytically tractable regime where p is an arbitrary fixed constant in the n - oo limit. Using a physics-style derivation, we show that the p-step QAOA can achieve weak recovery when the signal-to-noise ratio satisfies
An = (
where Ep =
(q-1)--1"
4-2
11
9>7 2,
(3.10)
1/p.
2=
and limp--oo Ep = O. Hence, the p-step QAOA can recover the signal with progressively weaker SNR as p increases. Moreover, we are able to characterize the overlap distribution RQAOA = â uuun of p-step QAOA between a sample ú 13 (see Eq. (2.3 and the signal u as follows:
Observe that 0 < Ep S
Claim 3.7 (p-step QAOA for weak recovery), Consider the p-step QAOA with parameters {(r,, (,n,,,))be B,)1a21 applied to the spiked tensor model 1.1b with signal-to-noise ratio {>a An1n21 Suppose
lim (7ns An/ 2tpp)/2 (,,
(3.11)
Then, there are garameteer-deeeddee coefficients (9) B)) such that over the randomness of Y and the quantum measurement, the overlap RoAOA of the p-step QAOA converges in distribution sine- Gaussian law
RQAOA d
Op sin (in ((9
where G~,1001).
(3.12)
The derivation of Claim 3.7 is contained in Appendix D
We remark that our derivation uses non- rigorous heuristics from physies such the Dirac delta function and its Fourier transform linearize exponents in combinatorial sums (see Appendix D.I for a sketch). Analytical expressions for the coefficients ap (y,,)) and (7 33 can found in Appendix D.5
Remark 3.8 (Weak recovery threshold). As A 0, Eq. (..22 implies that RQAOA -n 0. Thus, Claim 3.7 implies that An, ((((9-2+))))2) is the weak recovery threshold by the p-step QAOA in the spiked tensor model in the regime of fixed QAOA parameter. We believe this scaling is also the weak recovery threshold for the QAOA with any sequence of parameters (7 B,)). ). but proving this requires ruling out better performance of the QAOA when (Y., 3.,) is allowed to depend strongly on as we have done in Theorem [a): we leave this as future work. Since Ep - 0 as p - oo, this means An (n((--2))) 22)/2) is the recovery threshold given diverging number of QAOA steps (but constant with respect to ni). However, this does not achieve the (n computational threshold for classical algorithms.
Comparison with classical tensor power iteration. We now compare the overlap from the p-step QAOA to that from the classical p-step tensor power iteration algorithm. We show that the weak recovery threshold for the p-step power iteration estimator is also Xn = O(n (ttpp)), and we provide the distribution of the overlap Rpi = ú, u/n between the p-step power iteration estimator úp (see Eq. (2.I) and the signal u.
Proposition 3.9 (Corollary of Lemma 3.2 of (3)). Consider a random instance of the spiked tensor model with tom Xn/n /n//n//nt algorithm converges in distribution as
A. The overlap Ret of the p-step tensor power iteration
RpI d sin |arctan(A 1/x
where G ~ N/ 1).
(3.13)
7

---

The proof of Proposition 3.9 is contained in Appendix H.3
Remark 3.10 (Comparing the overlaps), In the small < regime, we have
RoAOA= x (l A))=///*/////////>>>>>>>>
and Ret A
(3.14)
When ldpbpl > 1, the QAOA has constant factor advantage over the classical power iteration algorithm the overlap achieved, assuming the conjectured Claim Cl based on heuristic derivations. To quantify this advantage, we consider the quantum enhancement factor, |apby 1fr,, which is the factor that the Sgnallto-noise ratio can shrink for the QAOA while maintaining the same overlap as the power iteration algorithm. Effectively, this factor apbpl' fr corresponds to quantum improvement in the recovery threshold by the QAOA over classical power iteration. We numerically optimize Japby/5r ( with respect the QAOA parameters (7, (3,, and present the optimized values in Table 1
Table 1: The quantum enhancement factor |apbp of the p-step QAOA over the p-step tensor power iteration, for spiked g-tensors when X, An in the A < 1 regime. Note in the first row, which corresponds to p =1 with E 1, we know the optimal value |ر,رı| / /q/e from Eq. (37). The remaining values are optimized via a quasi-Newton method starting with 1000 heuristic initial guesses of (y, B] and keeping the best value; hence, they currently should be considered as lower bounds on the best possible enhancement factors.
q
2
3
4
5
0.8578
1.0505
1.2131
1.3562
1.4857
1.6047
0.9663
1.0505
1.1916
1,2882
1.4167
1.5162
1.0204
1.0314
1.1615
1.2555
1.3844
1.4917
4
1.0487
1.0144
1.1419
1,2447
1.3795
1.4858
1.0631
1.0063
1.1327
1.2411
1.3770
1.4845
1.0697
1.0013
1.1297
1.2399
1.3743
1.4842
1.0719
Remark 3.11 (Weak recovery threshold for QAOA with tensor unfolding). Although neither the constant-step QAOA nor the tensor power iteration matches the ((n(r-2)/4) recovery threshold for the best polynomial-timg classical algorithms, we can achieve this threshold using the idea of tensor unfolding. When q is even, the tensor Y Raa can be unfolded into matrix Y:
Y (An/n//2) -u + (L/VT) W E RRR xn9/2
(3.15)
W W and à vec( u ((//2)) E {+1]"9? Existing work 2 47) have demonstrated that the leading eigenvec- tor 2 of Y has non-vanishing correlation with the signal à as soon as An. > n (2/44/ Furthermore, for the eigenvector z in such regime, standard analysis as 2 implies that the top singular vector of (nal(z) ) E Rnxx*/a-1 will have non-trivial overlap with the signal u, achieving the (nn(9-2)/1) weak recovery threshold for the spectral method with tensor-unfolding.
Here Y (fn.
Yiuii W (hhn..:a///) (1)
similar tensor-unfolding pre-processing could be applied to the QAOA to improve the computational threshold. Indeed, the QAOA method could be adopted maximize the cost function C(a)
Yo/n 1)/2 with decision variable ō E {=1]=?? Notice that such a QAOA method needs to be applied to a n/ -pu/it system. Effectively. C(σ) could be interpreted as the cost function of spiked 2-tensor model of size ñ = n/ and with rescaled signal-to toll-ttooosssss ratio X An/n( ( 2)/4 According to Claim 3.7 p-step QAOA outputs long bit-string [=1]m overlapping with the signal long as An /2 for Ep 1/p. Translating the scaling of An, the computational threshold for QAOA with tensor unfolding is A = (9(n9-2+e())) where e/ = q/p. This recovers the classical ( threshold as p oo.
4 Numerical simulations
We now validate our theoretical results by conducting numerical simulations of the QAOA through classical computers. In this section, focus on the case of 1-step QAOA (p 1) for the spiked
8

---

matrix model (g 2), where we can obtain an explicit formula the expected squared overlap at any finite problem dimension (see Appendix For derivation):
Ey (y
8 8n sin cos (807
7,3)
2n
(4.1)
1 1y (in(2////)))) cos" 200 (4X7/n) =. n
In Fig.
2.), a). report the overlap distribution of 1-step QAOA (p for the spiked matrix model
(q 2) where the SNR is chosen Å, n²/22 The histogram shows the Monte Carlo simulation results following the predicted sine-Gaure Gaessiann law. The dashed gray lines are from the simulations of the QAOA using classical algorithms for 26, each corresponding to of 40 instances. Note that simulating QAOA classically has complexity O(2"), which limits us to n = 26, We see
(a)
(b)
0.08
Sine- Game-Gansii law (n + 50) data: 40 instances (n = 26)
Finite data
0.5
Finite average (data)
0.06
average
average RoADA
Finite average (theury)
Probahlity
0.45
oo linit
0.04
0.4
0.35
0.02
0.3
0.25
Overlap RQAOA à uu/n
problem size n
Figure 2: (a) Example overlap distribution from 1-step QAOA for the spiked matrix model (g 2), where simulation data is collected from 40 random generated instances with n 26 bits. The signal-to-noise ratio is chosen to be X, = 1/2 and (3. = (v 5/32, 132,, я /4). Dash gray lines from the QAOA
connect data from the same instance. (b) Average of squared overlap (Reaas) 7.8 output distribution for 40 random instances generated various problem dimensions.
p=1
p=2
p=3
p=4
p=5
0.1
0.1
Probability
0.1
0.1
0.05
q
0.05
71 = 26
0
0
0
1
0
1
0
-
0
-1
Overlop RaanA
Overlap RoADA
Overlap ReyaA
Overlap RQanA
Overlup RQADA
0.3
0.4
0.6
0.6
0.8
Probubillty
0.2
0.3
0.4
0.1
0.6
0.4
@ =
0.2
23
0.1
0.2
0
0
0
0
0
-1 Overlap Rasas
-1 Overlap Reyao
-1
0
-1
0
Overlog
ReaDA
Overlap Roaaa
Overlop RoADA
Figure Example overlap distributions from p-step QAOA for the spiked tensor model for p The top shows data from 40 random 26- bitbit instances with q and X, n 1/(p)) The bottom row shows data from 40 random 23-bit instances with 4 = 3 and An n0+1/(2--1)/2 Different columns correspond to different p. using the QAOA parameters (y, () that optimized lapb,l | in Table I Dash gray lines connect data from the same instance. Blue histograms are the theoretical sine- Gaussian distributions in the - oc limit, where Rosoa ap sin 11" according to (Note here = 1.)
G(a-,,
Claim 3.7

---

that, despite some finite sample effects, the predicted sine-Gaussian distribution matches the QAOA simulation.
Fig. 2b)) reports the expected squared overlap from the QAOA simulations. The green dashed line is the theoretical prediction in the - limit. The blue solid line is the finite n theoretical prediction from Eq. (4.1) The gray dots are the squared overlaps from individual QAOA instances simulated classically. The average over instances (red crosses) agrees well with the finite n theory prediction, which converges to the n + do limit with order 1/n deviation.
We also perform simulations for 1 S p S 5 and q 2, 3. Fig. pllots the overlap distribution for p-step QAOA. The simulation curves follow the shape of the theoretical histograms for p S 2. For p 2 3, the shapes of the simulated and theoretical overlap distributions do not match well, likely due to finite size effects (simulations for large n >> 26 are computationally challenging).
In Appendix G we present additional numerical simulation results on higher (p: q) and find the second moment of the QAOA overlap converges to our theoretical predictions up to O(1 (1/n) deviations. We also describe more details of the simulation methods.
An interesting phenomenon apparent from Fig. aa and Fig. 3 is that the output distribution of the QAOA appears to concentrate over the randomness of instances Y. but not over the quantum measurements, This is in stark contrast to previous concentration results on the QAOA where concentration over measurements were shown, e.g., for spin-glass models in [24 26 32
We note
that such anti-concentration also expected in the limit of zero noise (A + oO), where it is known the constant-p QAOA can prepare the GHZ state (48). Since existing limitations of both classical 29 and quantum algorithms 226 32 on various problems over random structures rely heavily on concentration, extending these negative results to the QAOA for the spiked tensor model do not seem possible due to the absence of concentration. Nevertheless, our analysis shows that the constant-p QAOA is unable to improve the recovery threshold in the spiked tensor model achieved by classical algorithms by more than a constant factor.
5
Discussion
In this paper, we have investigated the power of quantum algorithms for the spiked tensor model, canonical problem in statistical inference with a large computationallstatiiicaal gap that has so far eluded classical algorithms. We gave the first rigorous study of a polynomial-time quantum algorithm on this problem by analyzing the performance of the QAÒA, a popular variational quantum algorithm that has been implemented on current quantum computing hardware. We showed that p-step QAOA achieves the same asymptotic SNR threshold for weak recovery as p-step tensor power iteration. A heuristic analysis showed that multi-step QAOA with tensor unfolding could achieve, but not surpass, the classical computation threshold (1,, This implies that achieving a strong quantum advantage via the QAOA requires using a number of steps p that grows with n. However, we revealed that the asymptotic overlap distribution of QAOA exhibits an intriguing Gaussiann law, distinct from tensor power iteration. For certain parameters (p. q). the QAOA effectively has a recovery threshold that is a constant factor better, indicating a modest quantum advantage over the classical power iteration. Overall, while achieving identical scalings as power iteration, the QAOA demonstrates qualitative differences and potential for quantum speedups.
There are many interesting questions that remain open. One worthy challenge would be a rigorous proof for the > analysis without relying on heuristic arguments. Additionally, it would be interesting to prove that the sine-Gausse Gaussian distribution is concentrated over problem instances but not over measurements, as suggested by our simulations. This is in contrast to recent results showing that the low-depth QAOA is concentrated over measurements 226 32). seemingly essential ingredient for many proofs of algorithmic limitations (26) 22)32) Despite the absence of concentration in the spiked tensor setting, our results show that the constant-p QAOA has limited power, similar to the Olog n.). This suggests that demonstrating strong quantum advantage requires analyzing loger-logarithmic depth QAOA, which remains an outstanding open question. Finally, it would be interesting to study quantum algorithms in other statistical inference models that classically exhibit computationallstatistt including planted clique, Bayesian linear models, and sparse PCA. Overcoming any such gap with polynomial-time quantum algorithm would be an exciting superpolynomial quantum speedup with practical relevance.
message of recent works [26 30.32 [1 proving limitations up
gaps,
10

---

Acknowledgments
We thank David Gamarnik for insightful discussions and Stuart Hadfield for detailed comments on the manuscript. We thank Yuchen Wu for providing the proof of Proposition 3.9 and Ruixiang Zhang for the helpful discussion on the potential for making Claim 3.7 rigorous. LZ acknowledges funding from the Walter Burke Institute for Theoretical Physics at Caltech. JB is partially supported by grant from the Simons Foundation under Award No. 825053 and the NASA Ames Research Center, from NASA Academic Mission Services (NAMS) under Contract No. NNA 1614CCD, and from the DARPA ONISQ program under interagency agreement IAA 8839, Annex 114. SM is supported CCF-2315725, CAREER DMSS22339044, ONR N00014-24-S-BON an Amazon Research Award, a Google Research Scholar Award, and an Okawa Foundation Research Grant.
by NSF DMS-221088
References
[1] Wei-Kuo Chen. Phase transition in the spiked random tensor with Rademacher prior. The Annals of Statistics, 47(5):2734-2556 2019.
[2] Andrea Montanari and Emile Richard. A statistical model for tensor PCA. In Proceedings of the 27th International Conference on Neural Information Processing Systems, volume 2 of NIPS 14, pages 2897-2905 Cambridge, MA, USA, 2014. MIT Press.
[3] Thibault Lesieur, Léo Miolane, Mare Lelarge. Florent Krzakala, and Lenka Zdeborová. Statisti- cal and computational phase transitions in spiked tensor estimation. In 2017 IEEE International Symposium on Information Theory (ISIT), pages 511-515. IEEE, 2017.
[4] Alexander S Wein, Ahmed El Alaoui, and Cristopher Moore. The Kikuchi hierarchy and tensor PCA. In 2019 IEEE 60th Annual Symposium Foundations of Computer Science (FOCS), pages 1446-144 1468. IEEE, 2019.
[5] Gérard Ben Arous, Song Mei, Andrea Montanari, and Mihai Nica. The landscape of the spiked tensor model. Communications on Pure and Applied Mathematics, 22:122:222- 2019.
[6] Valentina Ros, Gerard Ben Arous, Giulio Biroli, and Chiara Cammarota. Complex energy landscapes in spiked-tensor and simple glassy models: Ruggedness, arrangements of local minima, and phase transitions. Physical Review X, 91)):11 1003, 2019.
[7] Aukosh Jagannath, Patrick Lopatto, and Leo Miolane. Statistical thresholds for tensor PCA.
Annals of Applied Probability, 1914):19101193) 2020.
[8] Amelia Perry, Alexander S Wein, and Afonso S Bandeira. Statistical limits of spiked tensor models, Annales de I'Institut Henri Poincaré, Probabilités et Statistiques, 56:230-264, 2020.
[9]
Gérard Ben Arous, Reza Gheissari, and Aukosh Jagannath. Algorithmic thresholds for tensor
PCA. The Annals of Probability, 48(4):2052 2087, 2020.
[10] Jiaoyang Huang. Daniel Huang, Qing Yang, and Guang Cheng. Power Iteration for Tensor
PCA. The Journal of Machine Learning Research, 23(1)55567-5613, 2022.
[11] Gérard Ben Arous, Daniel Zhengyu Huang, and Jiaoyang Huang. Long random matrices and tensor unfolding. The Annals of Applied Probability, (3(6)))5753-7788 2023.
[12] Gérard Ben Arous, Reza Gheissari, and Aukosh Jagannath. High- figh-dimensional limit theorems
for sgd: Effective dynamics and critical scaling. Advances in Neural Information Processing Systems, 35:25349 223622, 2022.
[13] Matthew Brennan and Guy Bresler. Reducibility and catissical-comppuationnn gaps from secret leakage. In Conference on Learning Theory, pages 648 847. PMLR, 2020.
[14] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv preprint 141 1.4402, 2014.
[15] Leo Zhou, Sheng- Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D Lukin. Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near- term devices. Physical Review X, 10(2):021067, 2020.
[16] Guido Pagano, Aniruddha Bapat, Patrick Becker, Katherine S. Collins, Arinjoy De, Paul W. Hess, Harvey Kaplan, Antonis Kyprianidis, Wen Lin Tan, Christopher Baldwin, Lucas Brady, Abhinav Deshpande, Fangli Liu, Stephen Jordan, Alexey V. Gorshkov, and Christopher
11

---

Monroe.
Quantum approximate optimization of the Langrrange ising model with a trapped-ion quantum simulator. Proceedings of the National Academy of Sciences, 117741)25336-25401 2020.
[17] Matthew P Harrigan, Kevin J Sung, Matthew Neeley, Kevin J Satzinger, Frank Arute, Kunal Arya, Juan Atalaya, Joseph C Bardin, Rami Barends, Sergio Boixo, et al. Quantum approximate optimization of non-planar graph problems on a planar superconducting processor. Nature Physics, 17(3):332-336 2021.
[18) Sepehr Ebadi, Alexander Keesling, Madelyn Cain, Tout T Wang, Harry Levine, Dolev Bluvstein, Giulia Semeghini, Ahmed Omran, J-G Liu, Rhine Samajdar, et al. Quantum optimization of maximum independent set using Rydberg atom arrays. Science, 12666598) 2022.
[19]
Ruslan Shaydulin, Changhao Li, Shouvanik Chakrabarti, Matthew DeCross, Dylan Herman, Niraj Kumar, Jeffrey Larson, Danylo Lykov, Pierre Minssen, Yue Sun, Yuri Alexeev, Joan M. Dreiling, John P. Gaebler, Thomas M. Gatterman, Justin A. Gerber, Kevin Gilmore, Dan Gresh, Nathan Hewitt, Chandler V. Horst, Shaohan Hu, Jacob Johansen, Mitchell Matheny, Tanner Mengle, Michael Mills, Steven A. Moses, Brian Neyenhuis, Peter Siegfried, Romina Yalovetzky, and Marco Pistoia. Evidence of scaling advantage for the quantum approximate optimization algorithm on classically intractable problem. Science Advances, 10(22):eadm6761, 2024.
[20] Seth Lloyd. Quantum approximate optimization is computationally universal. arXiv preprint arXiv:1812.11000
2018.
[21] Seth Lloyd. Bobak T Kiani, David RM Arvidsson-Shan -hhukur, Samuel Bosch, Giacomo De Palma, William M Kaminsky, Zi-Wen Liu, and Milad Marvian. Hamiltonian singular value transforma- tion and inverse block encoding. arXiv preprint arXiv:2104.01410, 2021.
[22] Edward Farhi and Aram W Harrow. Quantum Supremacy through the Quantum Approximate Optimization Algorithm. arXiv preprint arXiv: 102.07160. 2016.
[23] Hari Krovi. Average-case hardness of estimating probabilities of random quantum circuits with a linear scaling in the error exponent. arXiv preprint arXiv:2206. 05642,, 2022.
[24] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Leo Zhou. The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpen 6:759, 2022.
Model at Infinite Size. Quantum,
[25] Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga, and Leo Zhou. The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the AnteriinttonKKikpattiiee Model. In 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022), volume 232, pages 7:1-7:21, 2022.
[26] Joao Basso, David Gamarnik, Song Mei, and Leo Zhou. Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 335-343. IEEE, 2022.
[27] Sami Boulebnane and Ashley Montanaro. Predicting parameters for the Quantum Approx- imate Optimization Algorithm for MAX-CUT from the infinite-size limit. arXiv preprint
arXiv:2110.106855 2021.
[28] Sami Boulebnane and Ashley Montanaro. Solving Boolean Satisfiability Problems With The Quantum Approximate Optimization Algorithm. PRX Quantum, 5:030348, 2024.
[29] Brice Huang and Mark Sellke. Tight lipschitz hardness for optimizing mean field spin glasses. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 312-322, 2022.
[30] Edward Farhi, David Gamarnik, and Sam Gutmann. The quantum approximate optimization algorithm needs to see the whole graph: A typical case. arXiv preprint arXiv:2004009002 2020.
[31] Chi-Ning Chou, Peter J. Love, Juspreet Singh Sandhu, and Jonathan Shi. Limitations of Local Quantum Algorithms on Random MAX-K-XOR and Beyond. In 49th International Colloquiam on Automata, Languages, and Programming (ICALP 2022), volume 229, pages 41:1-41:20, Dagstuhl, Germany, 2022.
[32] Anurag Anshu and Tony Metger. Concentration Bounds for Quantum States and Limitations on the QAOA from Polynomial Approximations. 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), volume 251, pages 5:1-5:8, 2023.
12

---

[33] Yuchen Wu and Kangjie Zhou. Sharp analysis of power iteration for tensor PCA. Journal of Machine Learning Research, 25(195):1-42, 2024.
[34] Samuel B Hopkins, Tselil Schramm, Jonathan Shi, and David Steurer. Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors. In Proceedings of the forty-eighth annual ACM symposium Theory of Computing, pages 178-191, 2016.
[35] Samuel B Hopkins, Jonathan Shi, and David Steurer. Tensor principal component analysis via sum-of-square proofs. In Conference on Learning Theory, pages 956-1006. PMLR, 2015.
[36] Chiheon Kim, Afonso S Bandeira, and Michel X Goemans. Community detection in by- pergraphs, spiked tensor models, and sum-of-squares. In 2017 International Conference on Sampling Theory and Applications (SampTA)) pages 124-128. IEFF, 2017.
[37] Rungang Han, Rebecca Willett, and Annu R Zhang. An optimal statistical and computational framework for generalized tensor estimation. The Anmals of Statistics, 50(1):1-29, 2022.
[38] Yuetian Luo, Garvesh Raskutti, Ming Yuan, and Anru R Zhang. A sharp blockwise tensor perturbation bound for orthogonal iteration. The Journal of Machine Learning Research, 22(1):8106-8153, 2021.
[39] Anru Zhang and Dong Xia. Tensor SVD: Statistical and computational limits. IEFE Transactions on Information Theory, 64(11):7311-7338 2018
[40] Anima Anandkumar, Yuan Deng, Rong Ge, and Hossein Mobahi. Homotopy analysis for tensor PCA. In Conference on Learning Theory, pages 79-104. PMLR, 2017.
[41] Giulio Biroli, Chiara Cammarota, and Federico
How to iron out rough
landscapes and get optimal performances: averaged gradient descent and its application to tensor PCA. Journal of Physics A: Mathematical and Theoretical, 53(17):174003, 2020.
[42] Rishabh Dudeja and Daniel Hsu. Statistical query lower bounds for tensor pea. The Journal of Machine Learning Research, 22(1):3799-379) 2021.
[43] Afonso S Bandcira, Ahmed EI Alaoui, Samuel Hopkins, Tselil Schramm, Alexander Wein, and Ilias Zadik. The franz-parisi criterion and computational trade-offs in high dimensional statisties. Advances in Neural Information Processing Systems, 35:33831-33844, 2022.
[44] Matthew B Hastings. Classical and quantum algorithms for tensor principal component analysis. Quantum, 4:237, 2020.
[45] Alexander Schmidhuber, Ryan O'Donnell, Robin Kothari, and Ryan Babbush. Quartic quantum speedups for planted inference. arXiv preprint arXiv:2406.1993 2024.
[46] Daniel Stilck França and Raul García-Patrón. Limitations of optimization algorithms on noisy quantum devices. Nature Physics,
2021.
[47] Jinho Baik, Gérard Ben Arous, and Sandrine Péché. Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices. 2005.
[48] Wen Wei Ho, Cheryne Jonay, and Timothy H. Hsich. Ultrafast variational simulation of nontrivial quantum states with long-range interactions. Phys. Rev. A, 99:052332, May 2019.
[49] Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. Obstacles to variational quantum optimization from symmetry protection. Physical review letters, 125(26)220500, 2020.
[50] Edward Farhi, David Gamarnik, and Sam Gutmann. The quantum approximate optimization algorithm needs see the whole graph: Worst case examples. arXiv preprint arXiv:2005.08747 2020.
[51] Antares Chen, Neng Huang, and Kunal Marwaha. Local algorithms and the failure of log-depth quantum advantage on sparse random CSPs, arXiv preprint arXiv:2310.0155 2023.
[52] Jahan Claes and Wim van Dam. Instance independence of single layer quantum approximate optimization algorithm on mixed-spin models infinite size. Quantum, 5:542, 2021.
[53] Asier Ozaeta, Wim van Dam, and Peter L McMahon. Expectation values from the single- layer quantum approximate optimization algorithm on ising problems. Quantum Science and Technology, 7(4):045036, 2022.
[54] Michel Talagrand. The Parisi formula. Annals of mathematics, pages 221-263 2006.
13

---

Contents
Introduction
Background and related work
2.1
Spiked tensor model and prior algorithms
2.2
Quantum approximate optimization algorithm
3
Main results
Weak recovery threshold and overlap distribution for 1-step QA0A
3.2
Weak recovery threshold and overlap distribution for p-step QAOA
Numerical simulations
Discussion
10
Additional background
15
A.1 Review of quantum computing terminology
15
A.2 Related literature on the QAOA
15
Moment generating function of the QAOA overlap at p
16
Proof of Theorrmm
17
Proof sketch for Theorem
(b) and emergence of Gine-Gaussian law.
17
Proof of Theorem l(b)
18
Proof of Lemma
20
22,
Proof of Lemma
22
22.3
Proof of Lemma
23
C.3
Proof of Theorem
23
Proof of Lemma
24
Proof of Lemma C.6
25
Derivation for general p-step QAOA (Claim 3.7)
25
D.I
Sketch of derivation ideas
25
D.2
Organizing the finite n sum
................................
26
D.3
Rescaling the summand for the 00 limit
................................
29
D.4 MGF at general in the n > xc limit to show Claim 3.7
31
D.5
A self contained formula for a, (7. and (,(r,))
34
Signal boosting with 1-step QAOA
35
Proof of Theorem
36
Proof of Lemmal
38
Proof of Lemma
39
14

---

Proof of Lemma E.5
40
Finite n calculation for 1-step QAOA the spiked matrix (q 2)
40
Additional numerical simulations
43
Analysis of classical power iteration algorithm
44
Proof of Proposition 3.3
H.2 Proof of Proposition E.2
44
H.3 Proof of Proposition
44
A
Additional background
A.1 Review of quantum computing terminology
For the convenience readers who are unfamiliar with quantum computing terminology, we briefly introduce relevant linear algebra concepts. A quantum state of an n--ubit system is 2" ""-dimensional unit complex vector zb E C² satisfying Eie(2n] |///2 = 1. Each bit-string
E [+1]²* associates with a quantum state |=) E C²", representing the |=|"th canonical basis vector 0,,,,, ... ,0]T C²", where only position |>| equals 1 (with |z| ΣjE(n 21-1(1 =2)/2 denoting the rank of bit-string 2). Therefore, vb = Eze(Li) </=|1>) where 1/ | gives the probability of observing upon measurement. This represents up probability distribution over all 2" bit-strings {=1)".
The Pauli operators Ty. on a single qubit are represented as 2 x complex matrices:
1 0
0 1 1
0
i
0 -1
-
0 1
0
02 =
(A.1)
In n--ubit system, the Pauli operators {Xa, Ye, Zx} E x2"x2" associated to the k-th qubit are defined by [o(k-1) @ {aa, ( J2) 69 (e(n-k) E C x2" where 6 is the Kronecker product operator.
A.2 Related literature on the QAOA
In terms of theoretical analysis of its computational complexity, the performance of the QAOA has been studied for various models, including the Seterington-Kirppaate model [24]. MaxCut
22 [27, the Mlxx--XXORAAT for regular hypergraphs (25). q-spin spin-glass models 266 52 the
ferromagnetic Ising model [53] and random constraint satisfaction problems
(28). While 24 shows
promising evidence for the QAOA achieve the ground state energy of the Sherrington Kirkparrik
model [54]] 26 proves that constant-step QAOA cannot achieve the ground state for q-spin spin-glass models in general.
There also a line of work aiming to prove computational hardness results for the QAOA and related quantum algorithms. (30 3 50 51 studied the limitation of local quantum algorithms like the QAOA for solving combinatorial optimization problems on sparse random graphs, using the bounded light-cone of the algorithms at sufficiently low depths. This limitation was translated to the dense spin-glass models in [26]. Furthermore, 32 proved hardness results for the QAOA by exploiting the symmetry of the problem. Note all previously known limitations of the QAOA in the average-cat setting 226 30 32 have relied on concentration of the output distribution the Hamming weight basis, which is not present in the spiked tensor model.
Our work studies the QAOA for statistical inference problem, distinct from these existing results. Furthermore, we develop new techniques for analyzing the QAOA that do not exist in prior work.
15

---

B Moment generating function of the QAOA overlap at p = 1
We dedicate this section to derive a combinatorial expression for expected moment-generatin function of the QAOA overlap, defined as
Ms Yno Pn, An) == (E Ba.Ba
(B.1)
We write (C) = (S: To: Sn An) for short. This quantity will be used in future derivations.
We use the techniques and conventions first introduced [24]. First, we define bistrings a E B == {=1}3 indexed as a (a1, am. a2). Since p 1, write BI, 7 71- Additionally, define the quantities given by
1
Qa = (a1 (a1let8x111 (1) (11e-1ax
198 (a2).
(B.2)
2
Pa = =01== - -2).
(B.3)
We may also write {NaJaEB S l where Eass aa = n to assign count to each bit-string, If underscore the bit-string, mean a (a1: 02 .9....... a.)) B We also write T T Pa10z--aa"
We now have the notation to state the following lemma.
Lemma B.1 (QAOA overlap expected comment-geneatinng function in the configuration basis for p = 1). The expectation over the spiked tensor disorder in Eq. [.T) of the moment function defined in Eq. (B.1) for p 1 is given by
moment-generant generating
i
Ey [Mn(()]] = Σ (na]
Qa exp a
II
Σ La
II a Ma.
{ma))
2n
aa
79-1
2t
B9
(B.4)
71
BEB
Proof of Lemma B.1
Without loss of generality, assume that and proceed in 24
Section 5] and 26 Appendix D.2]. By definition, we have that
Mn = {T. B e5 1r,
= {s} ic eB c e -DB
(B.5)
Inserting 3 resolutions of the identity 1 = Σn (z) (zl observing that every computation basis state |z) is an eigenvector of and R, we have that
Ma(() = Σ
e
(z)) (z1 10B c
| (zT e 1BB 1z2) (2²1 e0C [s)
-
m
SBB | (,)((=)) { (R(= ( (2 c-t0B 122)
nn
(= th ),8( 2 exp [ix(C(=)) + [[((
exp
2"
fz 2 (z(z²²²²)
2n
2 22
An +
W Win..dy
n +
cxp
iy
19-1 $1....9==1
Σ
11/-11/2 11/2
(2)
2/ 2/1
m n j=1
(B.6)
where we defined f3(2z') (z) é c |z') since this quantity only depends on the bitwise product
zz', We also used the definitions of C(z) = 20) / (22)/ and R(z) n Σラ= Zj. Next, we tranform the z as follows:
1
z + zz m
22 - 2
(B.7)
16

---

This gives
Ma(3)
Σ
f0(2)){((2))
2
t
x²
n
An
W
Win...ng
n
x exp
by
1291
+
n!a-1)/2
mm
b1
(2)
1/1
b
n
Σ
(f(22))
2
x²
An
n
exp
19-1
7/9-11/2
2i1
24
m
Pi
(2)
+
72
}
m
(B.8)
$1
where we denoted Z = (=1, (z,,2²)
22) and
ig (Z) -
2
(B.9)
Hence, the expected moment- nomenttgennrating function is
Ey [c)]
1
Σ
fz(=)){a()))
2
iAn
x exp
129-1
2ia
do (Z)
2n
ii....i (2)
3j
(B.10)
Now we change to the so-called configuration basis. For any bit-string $ S n, we look at a new bit-string:
(e), m 2 B.
(B.11)
For any E B, we represent by na the number of times that configuration a happens. Note that EaeB For more details, we again refer the reader to [26 Appendix D.2]. Now, instead of counting over each bit of ==, " 2², we count over configurations in A:
iin n
Ey [M)( = Σ {na)
II a
-h exp
S aa (a1)m (ay)m nay
(na))
EB
Σ alm0.,
2
a Bay
nay
C
Σ
amma
(B.12)
2n
EB
aEB
which finishes the proof of Lemma B.1
C Proof of Theorem 1
C.1 Proof sketch for Theorem lbb) and emergence of sine-Gaussian law.
Here briefly sketch the proof of Theorem for 1-step QAOA, explain how the Gaussaasni law appears, and highlight the technical ideas.
To derive the distribution of the QAOA overlap, we compute its expected moment-generating function.
We start by following the steps from 24 26 reformulate the expected moment-generati function
(MGF). With some algebra, we arrive at the following equation (see Appendix B and Lemma C.I for
17

---

the derivation):
sin (23)
Ey ((e5 1os
71
e 1n Snt
(C.1)
8
4n
1=0
Sngt = n¹ Σ
(--)m=-nato t2 ns no (((/n)(mi tao ns na)) 7m, - 122 -nn + na),
{mn})
Enzz
(C.2)
1
n-tt) t (T+: (e5/m cos² 3 5/m sin" B) (e-S/n 5/m cos² B + estn sin? B)--
(k,
E
2n-t
x
(C.3)
Looking upon the term (k), we can interpret the summand 7+ as binomial variable Binom(n t, 1/22, and by the Central Limit Theorem, we have (T+ - --)// - G ~~~M No,, 1). This gives
lim (k) = Ea- 2ghAA 220hh777
(k).
This is the step where the power of Gaussian appears. Next, assuming that we can replace Zn by Ze in the expression of S,,e as in (C.2) and using the multinomial theorem, we get
Su,t = EG n'
Σ
10001-----0000 1)m tgt ns ((//n)(m) -n3-na) (m1-) 12-
(ni))
Σ =
-EG-W(0 ( ((Ansinh((//) sing 11') EG-NiO.1) (HCoo)))((((((AAAAG))))})))
S.-
This is the step where the sine-Gaussie distribution appears. Finally, suppose that we can replace Sn,t by St in (C.Tp. and using the Taylor expansion of the exponential function, we get
Ey RR
())
(inn(23) 4n
(n0
(BaN((1)) {IAC sin sin(2gA
1=
E
Ise
2mm2
(23) sin sin(24A7G* = BE { fere 200 sin(2))ssn(222)))))))
t=0
This gives the moment-generatie function of the sine-Gaussian law.
We should notice that several steps in the above proof sketch are non-rigorous, in the sense that we could not sequentially take n + co in Zn.,. Sm.t. and the MGF. To make this step rigorous, we use the idea of discrete Fourier transform in Eq. (C.2) to decouple the two terms e(C/n)(n) pan---a---- m2) and Zn, (see Lemma C.Ip. which allows one treat the + do limit of these two terms separately in the expression of Sn,t. For more details, see the full proof in the following section.
C.2 Proof of Theorem 1b)
To prove Theorem [b), it suffices to show that the moment- geeerttggn function (MGF) of the QAOA overlap converges the MGF of sine-Gaussian law follows:
lim Ey (M,(() = (G-N((,))) { exp [<e -2m? sin( sin(2 =: M()) (C.4) 000
We start the proof of Eq. (C.4) with the following lemma, which obtains a more explicit expression for the MGF that we derived in Section
Lemma C.1 (Expected moment-generating function). The expected cooennt-geerratin function in Eq. (.4) can be evaluated as
[M,((()) =
Σ t=0
11
e - f1n (n- (n-22) 2/101 ssinh(C/n) sin(2 En.t:
(C.5)
18

---

where
1
En,t 2f +++1
sin' (2T + 1)) (()
f=-1
(5)
221th/ (k),
bm-t
(x),(())
1
Σ
11 11-
(eS/n cos? B e c/n
e-nm sin? 3)*+ (e-C/n c/n cos?
+ e/nssi?? 3)
2
(4,
T+tT_ =n-
x edlnnil((T )--))) (())) 11/2
(C.6)
Here we have An = An/nn/n -nnnn111-1)/2
The proof of Lemma
is deferred to Section C.2.1 Now we define
lim An: 12 11+20
In,t
e 7 (m-)-11- (sinh((())sin((3})}) En,t
(C.7)
Ba-A((.)) [cce sin(23) sin
Then easy to see that
By M2
Σ
M(() Σ
4
==
t=0
As consequence, we have
Ey (M,(()) - M(() S
Tel +
Σ 1
Σ
(C.8)
1=0
127+1
t=T+1
The following lemma gives the limit of En,t for fixed / as oc, which indicates that I, is the limit of In,t-
Lemma C.2. For any fixed integer I, we huve
lim Fn, EEn (200)))) = E.. n-+00
As a consequence, we have
lim In,t It- 1=
Furthermore, we have the following upper bound of In,t-
Lemma C.3. For any S n and n, we have
1 |n < t!
(o(C)) + 1)el = =st
where
< 00.
(=0
The proof of Lemma C22 and 3
C.2.2 and C.2.3 respectively. Now we assume that these two lemmas hold. By the fact that Ei finite and by Lemma C.3 for any
is deferred to Section
& >> 0, there exists T T- such that
Σ 12T
4 Se/3.
Σ
< s/3.
12
19

---

Furthermore, by Lemma C.2 there exists N Ng such that as long as n 2 Ne, we have
Σ nt E//3.
As a consequence, by Eq. C.8), for any n 2 ne and ( S n, we have
Ey [M, - M({)
Σ
I I
Σ
Σ
S
E.
(C.9)
t=u
12
T
This proves Eq. (C.4) as desired, and hence finishes the proof of Theorem b).
C.2.1 Proof of Lemma
Our starting point is Eq. sum. To this end, let
B B.4.. which we can compute explicitly with careful organization of the
4 - +
t- ----- + 12_ +1
d. = + - 11 +
d_ -14- - 11
(C.10)
T4 ++++ + n
-+ 11-4-1
A+ = n+++
A_ = 14-+ 11 -
Observe that these 8 variables completely determine {na B}. Furthermore, let
t= n --t- 7+ +
(C.11)
Then explicit computation shows that
q
Σ aE
2 na. 472 Σ 1fa11 ... 0y # ........ ag2) II
nha
2
8=1
= 2-² n2 - (n - 2/)0/
(C.12)
Σ 4
(a m na, = - Σ
01 am na 99 - a2am na)) )]
a
s=1
a
> - T-) (d4 d-))² ((----))- (d+ d_)),, (C.13)
Σ
um 4 - + A+ AA_.
(C.14)
DEB
Plugging this into Eq. B.4 and breaking up the sum, we get
n n-
Ey [M, (c) = 1m" (n 22/
Σ
Σ
14,t_
T+,
4+-=
++++_=n-
T+
04441
Σ
0 Q=1
n+++
14
4_
b+
Q"
Q Q=
M4+
Mi,d - ((+ )-( -d 1/9//00011/2
(C.15)
where An An/ / (m1/11/22 1)/2 as shorthand. Now, let evaluate the over A+. We can use the following identity
2
Q Q"_ c(/nn)++ (2Q f20+++e5/+ + +2Q 2QQ- e
(C.16)
n4++)
20

---

Applying this to the earlier sum, and note that Q+++ = Q++ and Q--- = =Q++- we get:
Ey [M,( = 1=
n2
20)
Σ
Σ
11 1 1
(4+,t)
T+ =n- T4,
4+
(2Q (2Q++455/n +2Q 6/ng--- (2Q+++ <//n + 2Q -Q--2__000000 -llnnt- c(m(--(((/n)(e-)))))
2
Σ
1+
0++ Q= Σ
n4 @+ Q==
1-
M++-/
e Annlkdy -ocl4-d--tig - 8- ((-+-11))))1-) - (d4 - 19///6111122
(C.17)
To further simplify the expression, we define (1k) as in Eq. C.6 which we reproduce here:
(k),
1
Σ
n- t (65/" cos² B + e s/n sin B)T (e-S/n cos? 8 + e sin? By S/n
2
[4., =n-
x ) -10-) -))
(C.18)
Then we have
Ey [Mx
=
Σ
11
e (1220///---/
4+c= (4,tt_ (1))))))
Σ E
(n++-)
L-
1=
dt
Σ
L-
Q Q² cl//m)(e-- -t-) (n,
Zm, - d-).
x
d
(C.19)
Let S2 = (tt 1.....t-
.t.,tt1,,, 1,tt, and let (2n.(E))eEe. to be the discrete Fourier transform of Zn, (k)) as defined in Eq. (C.6),
= (5) = (()
(21+1 Zn.
(C.20)
k=-t
By the property of Fourier transforms, we have
(k) = (F, () = 21
e 2xiEk/ L.))(
(C.21)
E--r
Plugging Eq. C.2T
into Eq. C. we have
Ey [M, = Σ
1
n2
72 In (n 20)
Σ (4it_
Σ
t+
Q+++=000
Q
14+
0=
dt
t-
Q hh+ Q Q== ((/)))(+----
1
2r1((d,-d-1/(344)) 2m,)(E)
21+
(C.22)
Σ
12
11
- -n2 2/00/1100
Σ
(
E
14,1-
x (-1)²
1
2214++ minn2mt/ + 111 (m,((E)
(C.23)
2t +
12
-lnn" (n-)))))/
(sinh({/n)sinll (in()
x
Σ
(sin(2nE/(21 11))) 2m,
(C.24)
2t + 1
8=-6
21

---

where (i) used the equation
Σ
Q+==-=+++ jed, 2ii+++singf ct n+++
f+
(C.25)
and (ii) used the equation
Σ r+s=t
Σ (1,5) (-1) explC(r- - s)} = sinh(()).
(C.26)
Note we have also used 4iQ ++Q++== = sin 2/3 to get rid of the two factors of 2 This completes the proof of Lemma C.I
C.2.2 Proof of Lemma C.2
We first look at the limit of (k, for fixed integer -t k t (c.f. Eq. (C6)). We denote
Tn (e5/" cos? c/n sin? B), Un (e-S/n cos? 8 + e//n sin? (3 and G, (T+ T-)/ //v/n
with T_ ~ Bin(n- - t, 1/2)) to be a random variable. Then we have
(k))(k) EG., T (A
(C.27)
Vv2/2 vn/2 lim (T, m/2 and by Note that we have lim TV lim (Tn Un) assumption we have lim An A. Furthermore, by central limit theorem, we have G. - G N(00 1) so that for any fixed -1 S k S 1,
Vn[(G, + k/vn) - -G,, kk/vn))) - 29kGa-1
This implies that
lim (k) = Eo. "1 =(()). 700
As consequence, we have
lim En, 2t sin(tnt/(2t 1))² 2x1gk/ (o,)(()))) le ( 1-000
Finally, by Lemma C.4 below and noting that sin (in22(//(2 + 1))² can be expressed as a degree polynomial of (c2m157(211) e 2mit/ (2(4)),,, the right hand side of the equation above gives
2t sin(2mE((2L-1))
2m11k/(2(+11 BC B (220A)00)))) = (einn
This proves Lemma
Lemma C.4. Let Zzo be an integer and let Sr -1 Iy..,, 1,,). For vector (Z(K))kEo we denote F, 22++1 - 22++1 to be the discrete Fourier transform
(FIZ)(E) Σ 2x1EE// Z(k).
Let P C² + C be any fixed polynomials with degree less or equal to t E Zzo Let X be real-valued random variable. Then we have
2t P(62715/22411) 2x13//2242)) (00
1
Σ
(F(x (5) = =Ex[P(cLX _xx))]. [xxP(cxX,e_xX111 (C.28)
Proof of Lemma C.4 By linearity of the expectation operator and the discrete Fourier transform operator, we just need to prove Eq. (C.28) for 2(22x1/(21++1 -2xx5/(2(+1)) (2(p(/(((+1) for
22

---

some integer -t S t. Note that we have
Ex (Exeetxx))
2t +
1
2 22thE/ Ex(e
+
Ex
2xi(p- 2010-k)1//241)-X/eem)) = Ex(eeax]
(C.29)
2t
f=-tk=-
where the last equality used the fact that
Σ
2t ++1
8 km-tkm=t
for any integer -t -t p and any real X. This completes the proof of Lemma C.4
C.2.3 Proof of Lemma
By the definition of (k, as in Eq. (C.6 is easy to see that
[k)) S 2
1
Σ n-6
es/n cos? 3 + c/a sin? 8 4² e c/" cos? B + es/n sin? 3) "
c/c
[T.
TT =
( - //nj///n 1/22
1
n n-t - =n-
Σ
2n-t
T4:
(n-t/////n
< els
(C.30)
As consequence, we have (,, < (2t + 1)els) which gives
En,el S (2t + 1)els),
As a consequence, by the definition of nn, as in Eq. we have
|nnel $ n² /
siinh(/n))(ee + 1) ta
Note that when Ç/n $ 1, we have sinnh(//n]] - 6|c//n This gives
|n < 7!
(6)))) 1)e
This proves Lemma
C,3
C.3 Proof of Theorem
Theorem is combination of the two lemmas below.
Lemma C.S. Take any sequence of Jnz1 S [0, 2T), (7rtag S IR with lim 00, and any sequence of (Ma)22 S [0, oo). We have
lim Ew (R =0. n-000
(C.31)
Lemma C.6. Take any sequence of (3,) Jn21 C [0, 2T., (7m322 C R with sup, Va oc, and any sequence of (ndr21 S (c) with lim \n/n /n/n/0 1)/2 = 0. We have
lim Ew (o . n-000
(C.32)
23

---

C.3.1
Proof of Lemma C.5
Proof of Lemma C.5
Denote A, An/n//113/2, We can write
8²
By (m)
0²² <=0 By Mn Ihs Br, Am]]
(C.33)
Using Eq.
we can see that only a few terms depend on C, whose derivative gives
(sinh((//)) (in22)2))) (e5/n (os + e c/u sin? (8)) 71 (e-</m
</" cos? + el/a sin? sin)
<=0
d=
(2lsin(23)) + [(T+ - ---2 (T+ + +-)] (43) + [(T+ x-)2+ + (r+ + +-)]
2n
11= t(T+ -in)3)
n²
612
t(t 1) (28). n2
(C.34)
Hence, only the L = 0, 1, 2 terms survive, and we can write
Ey (R = To + Ti + T2
(C.35)
where
To n
Σ
n ([(T+ - -- + +-]] cos(4)3) + [(T+ - =_)² + (T+ + +-)]])
=++T==n (T+,T_)
(C.36)
T 3n 2-
sin(43n)
e -2 (m-)))(n-))
Σ
sin(2
Σ
2rigk/3
$E{=1}
km-1
Σ
1
(T+ T te [( - 1--
(C.37)
T-,
7i =
(n 1) sin (255))
T2
(n=)"=(n-4))//=--
Σ
sin (2 2migk/5
10n 2n
k=- 2
x
Σ
n 2-2
e (0 -(4 - 1)/2
(C.38)
T-,
+
=n-2
Lemma C.5 then immediately follows from the Lemma C.7 below.
Lemma C.7. For any n 2 no for some large Thg, we have
To (1 cos(43,))) (433))) (2n),
T < 2 sin (14g))) 97
[2g < 2 sin 2 (2,3.) -
Proof of Lemma C.7
We can compute the first term directly follows. Note that
Σ
T
(T+ --)
8
Σ
e
(++-----)
(C.39)
T+,
dr
(4,,
8a
(2cosb(z)))
(C.40)
Or9 l==0
In particular,
n
(T_ -T-==)=0 =0,
(C.41)
T+, T
Σ
(T+ - )- n
(C.42)
[4,T_
24

---

It follows that
To 2 ((2"n 0) cos(48) + (2"n + 0)) c0s(433) +
1
(C.43)
2n
For the remaining terms, upper bounds suffice:
sin -1211==((1222111
n-11)
Trl -
Σ
1 Σ
(n-
(n - 1).1
3n 2n-1
(4,
{E(+1)
h=-1
T+TT_=n-
sin sin(4,n)) .
2sin(433)e -ah
(C.44)
and
(n 1) siiinnnnn -
(n-2) 2
[2 <
Σ
1. Σ 1. Σ
1
10n 2n-2
[4,
(E(#1+2)
k=-2
34t7_
sin (28m)
<
-07n 5
10
2 sin (28,))
(C.45)
This finishes the proof Lemma C.7
C.3.2 Proof of Lemma C.6
Lemma follows from Theorem Ib).
D Derivation for general p-step QAOA (Claim 3.7
D.1 Sketch of derivation ideas
We now briefly sketch some ideas behind the derivation for Claim 3.7 that characterizes the overlap
distribution of the p-step QAOA when the SNR ratio scales as in Eq. 3..0). Similar to Theorem | our approach is to evaluate the moment-generating function of the QAOA overlap in the n oo
limit. As evident in the proof of Theorem I as well as in previous analyses of the QAOA applied to
spin- glass models [24]]]]]] 26 28), the key technical difficulty is handling "generalized multinomial
sum" of the following form:
S=
n 2020, Σ, my=n )
Σ
11 exp[P(m)),
(D.I)
where P(m) is a polynomial over entries of m (m;); with degree Note the above summation has no analytical simplification when P is not a linear polynomial (q > 1). Previous works have evaluated this sum in the n - oo limit either by proving a "generalized multinomial theorem" that exploits combinatorial structures of the polynomial integration trick and the saddle-poin method when g 2
[2 26), or by employing Gaussian
28 However, neither approach is
sufficient for the spiked tensor model that we study the present paper.
Instead, we develop an alternative approach based on the Fourier transform to linearize exponents in the summands. The idea is to replace with continuous variables μ via Dirac delta functions, which after Fourier transforms yield exponents that are linear in m, enabling us to analytically evaluate the multinomial sum over m as follows:
S s= s=f
ffd du | di
my20, E, my=n ((m)))
Σ
(II (1 )
expl exp(P()))e (m-
= =f dp
(eeth)) " iim
(D.2)
25

---

See Appendix for more details. This is a powerful approach to replace the cumbersome multi- nomial sums with simpler integrals. However, difficult make such manipulations involving Dirac delta functions rigorous, which we leave open as future work. Nevertheless, we proceed with the heuristic derivation in the current paper: by writing the variables (m;); j in an alternative basis and rescaling them cleverly, we are able to evaluate the integrals to obtain the moment-generating function in the n + oo limit.
D.2 Organizing the finite n sum
Our goal is evaluate the moment-generating function of the overlap with signal, M, ( | exp((R))yr (3), for the general p-step QAOA. Using the same method as in the p case, we can show that the disorder-averaged moment- -emnenttgeeerating function can be written as the following combinatorial sum:
Ey [M](C)] = Σ
n
II o
Qh exp i cc|
(D.3)
{mai
{na]
where
Σ @EB'
2
Bax
B
Σ
aa.
C=
Σ
Un
2n
n2-1
@E
5=1
VEB
(D.4)
and
B {(11, .2. ap. Om: a.p....,.................... a-1) : aj {+1)}}
Qa 11 (cos 3r) ta (sin B,) (a,a, 1/0
(D.5)
Φ. Σ 7r (a, art1 ... ap a-p 1a-r)
La & Pajaz..-a.'
Note Qa and 4a are independent of am-
This is straightforward generalization of the proof in Appendix where insert 2p resolutions of the identity instead of 3. This also closely follows the derivation in Ref. [26 Appendix D.2]. B, Qa, Ta are also generalizations of the same quantities in Appendix B for p
Define the rank function
((a) = max((i: a_; :
0;} (0)))
(D.6)
canonical basis. am. First we define the set of 2p-bit strings as
We next perform further simplifications that remove the explicit dependence on
A (a1, 02. ap................ a.p. a, {+1)}.
and define Ao and D according to similar convention that in 226 as follows:
Ag = {a E A: ((a) = 0} {a E A a for 1 < k ph.
D D:= a A: ((a)
and 11 -1 03 +1]
(D.7)
Given the rank function in Eq. D.6). we can define an ordering on D, which we borrow from [26]
For any two distinct element a1 02 D, define the - relation following: (1) If ((a)) < l(a2).
we let ai < a2: (2) If {(a)) > f(a2), we let a2 < ai (3) If f(a)) = f(az) and if a is lexically {(az) and if a lexically greater than dg
less than ag. let a1 02; (3) If E(a,)
let < ai (here lexical order means that, for example, (-1, (-1, (1, (1, 1) are in
lexically increasing order). It easy see that such relation full order, so that we can also define 3, 2, and > accordingly.
For any E A, we define
Mat
where b = (0), aps +1, ,.. 0-1).
(D.8)
26

---

Let
la nat Batt
la- na- na-;
Ya E D,
da+ a tl
da Baa 11a
Ya E D,
(D.9)
na naa na--
ôna nat na--
Va E Ap.
Furthermore, Va E D, let
to tot + ta-1
da = dat da-, ōd, - da+ da
ala- - lat la-
(D.10)
Observe that these new variables constitute basis transformation via
{naLaEB = (ta=;da+ U {nay ôna JaEAo = (la: òla, da ddaaast U {ma anatacAo
(D.11)
We will call the last line as the "canonical basis". As a side note, comparing to the 1 derivation in Eq. (C.6). we have 6d4- and T4 T- 88+++ ón_
In what follows, we will convert all our expressions into the canonical basis. is also helpful to denote the shorthand
ta
and thus n n-t=
Σ na.
(D.12)
aED
aE
Ao
In this basis, we can rewrite (D3) as
Ey [M
Σ
Σ
II ao
Qua
na
(nah)
Ra+
fnatasap
Ora
(D.13)
Σ
A + idn + ccl
exp
(ta)
aED du 5da
JEED
where we have used the fact that Qai = Qa does not depend on (here we also slightly abused notation allowing Qa take as argument). Here also define, for any a E D and ta Zzo. the little-sum operator on functions of (da, ōda, 5t as
(...) = Σ
(1ate ta (attlaa- Vats/a-)
)
Σ
fat da- Mat
Quat Q
Σ {(1o-
(aa
Qua Qa (...).
ta ita
da-
(D.14)
Now let us rewrite in the canonical basis, and we will show that purely function of {ōda, öt Mta U (ōnc)eEAg. Observe that
(B7)") and we have denoted a Op...a ap for any r we have
n- B
7h (B+) (B+)"
where B
Σ aaz Umaa:
(D.15)
aEB
Note a a=,, + 0 only if ((a) Hence,
B = Σ a,ona
+
Σ
at +
Σ
a,
acAD
dE
aED)
B,
Σ a,ona +
Σ
a at
Σ
5,
a
aED,f(a)sr-1
aED,E(a)2r
To reveal additional structures B, we write
12" 9 =
Ir + L.)" (R, L.) = Σ
7r 12 R 1 12-1122 +2 L,R. +.... (D.16)
27

---

where we have defined
L, 2 (B - B
Σ
2 (a ddr)
(D.17)
aED,((a)2r
R2
1 (B, + +B))=
Σ aεAd
ugdna
E
0r
Σ
(a + a_
2
aED,(a)sr-11
aED.((a)2r
(D.18)
We note here that B consists of terms that have at least one power of the {oda (oda variables through the dependence on L,, which is fact that will become important later.
Proceeding in the same way for and C, we can also write them in the canonical basis. We note A is a polynomial that has appeared in [26]. where it can be shown to only depend on {/a, Jaen U Ae In summary, we note dependence of A, B, C on the canonical basis variables as follows:
A A (talaeD. (dalaED: (noloEdo):
1A i'nB(((dda òlaJaen (ōna)aEAo):
(D.19)
C ona 5ta)
aED
Operator shorthands for different parts of the sum. To streamline notations, now introduce three operators T, S, U as shorthands for different parts of the sum that appear in Eq. (D.13)
Let us define the TV operator acting on function f(fta a D))
T
11
Σ
f(tla)).
(D.20)
ta 2o20.VaDD... la=t
Next, let define the operator (((a)
acting on any function g((da: åda, St, bagn) follows:
na ta! daa jo
pla
s(ta) =
aED
II
(nQa)
Σ
ta
Σ
fat
(+1)"ot(-I)m++
Natila-)
matt
a ta+ita-
dat
la-
(41)aa-(11)00 j9.
(D.21)
Ma-
da-
Note s fbat 1tt Va E D}.
Lastly, we define the U, operator acting on a function h( (((ne/nn /ne/ VT: Aa)) as
Σ
II
Qa
Σ 5na
aa
(D.22)
{ma))
nax
(na)aeAo
aEAAg
With these summing operators defined, we can rewrite D.13) as
n
[x) = Σ (t),
(D.23)
where
(t) T [exp(A (exppp
i (C))
(D.24)
28

---

D.3 Rescaling the summand for the n - oo limit
In the oo limit, we want to rescale the canonical basis variables (ta. òta, da ÖdalaED {ne, A so that the summing operators (U, Th T s,fsa)))) and the summand A + id, B + ςC converge to simplified forms. To this end, for all a, b E D, As, we will rescale by defining
la Ta
ôla ôla/n"a òTa:
db/ n 7
òdb /n 1o--pb pb 871b
(D.25)
ne/ We
/ne/ V Swee
where (Ta: 7j. We, STa, 87/6, owe) are new dimensionless variables that will be integrated over, and Pa scaling exponents which will define shortly.
The goal of this subsection is derive the summand the n + 3o limit. Specifically, we consider the summand broken into two parts, each as a polynomial of a distinet subset of the rescaled variables as follows:
[nt(ta 76, wel) A(fta 16n, wen)),
(D.26)
En((ôTa, Orp, dwe]) == ( (6Tan'n 8mput~Pb Swe)n() + CC((6Tan (wey,w (D.27)
where the subscripts in the arguments implicitly iterate over a, and E Ao. We think of I'x and E,, as polynomials in their arguments, whose coefficients can depend on n.
First, we know from [26] Lemma D.2] that with the rescaling specified in Eq. D.25 and Yg.
(1), we have
lim (n(aaas T/b, b.. n=
Pa (( (wotnene) =: Σ
(D.28)
aED
For the rest of this subsection, we derive the limit of E 1,,++
Choosing the scaling exponents Pa- We want to choose the scaling exponents for (ōda. öt variables, such that all the terms except those are linear in òd, vanish in the n + oo limit. This would then imply the polynomial E, in the limit would only be at most linear in dij, which is very helpful later for evaluating certain integrals as we shall see in Eq. (D.6T).
In the general p-step QAOA applied the spiked g-tensor model, suppose the SNR parameter À has a scaling as follows
An An (P-.))
(D.29)
where c(p, q) is to be determined. Also suppose that the appropriate scaling for 6d,, and ōt, are
ådg peco), St nett
(D.30)
so that they only depend on the rank E(a) of a. Based on the explicit derivation at 1, we believe we only care about the terms in B that look like ōdgōng when {(a) = 1 and {(b) 0, or 5d Stg-1
when {(a) = l and {(b) = f > O. Also recall that 8n, ~ vn for b E Ao from D.25 For these terms B, have
An
5dg ong q-l ~ n (px))) (n (1 1)/10(0011/111111111
(D.31)
n
An
n 8d 0t ~ dp. - 11
(D.32)
To ensure that all such terms in B are order 1, we impose the condition that
clp ②) + Pe + (g () - = 0. and
Po =
(D.33)
Solving this recurrence equation, we get that
(g - 1)
(q - 1)a
=
+ c(p. ②)
(D.34)
2
29

---

If we impose the additional condition that P. = 1 (so that òt = (1) to yield nonvanishing overlap in C), this implies that the SNR scaling needs to be
cp..) - 2
(g 1) 9-2
9 - 2
(D.35)
2
(q 1)2 -1
2
2
1)p 1
Plugging this into Eq. (D34), we get
(g- - 1)p + (q- - -2
Pt
(D.36)
(q - 1)p -
For the special case of q 2, we have c(p, 2)
1
and Pr =3 + F 24
2p'
Note 1/2 S P3 < since S (q - 1)c S (q - 1)2 and 0 s p. This means ód, = ( and
8la= = (2) Another property to note that Pr monotonically increasing with l. In particular, Po = 1/2 and Pp 1.
The limiting expression for E, To get the limiting polynomial for E,, i' B+, substitute ōda= om 8La- = 8r and one- dweyn, and take the n - oc limit. We first consider
B as written in Eq. (D.16). In terms of the rescaled dimensionless variables, we have
L,
Σ
(a a",))nan" PPa
aED,E(a)2r
R2 2 (B, + B,)
Σ aεAg
E aED.
ar +
Σ aED.((a)2r
Z( (a + d=,))mma''
With the exponents defined in Eq. (D.36), we note that Ly is dominated by {ōlaa {(aa) = r. and R is dominated by {ōwa : a E Ao) when r = and {ÔTa : l(a) = - 1} when r 1. Thus, the appropriately rescaled L, and R, in the limit are
Lr
L, = lim
Σ aED,N(a)=
5 a 0² ,01
Σ
a;
(D.37)
n n I-Pr
aED.((a)=r
R
EaEso o,biaa
E
r=
R lim
p
EaeD, 0,
r> 1
(D.38)
For An Anela.),
we have
iAn
iAn
2
L R
n--1
k
odd
iAn ((F-))
P
lim iA lim
2
k R k ((1---))(--kpp--
no-
ould
One can verify that for any 1 r (((p9) no0 n n ((1--)))(0-b)pp)))
1, 1/n for some e > 0,
h = 1
lim
(k- 1)-1)(1-pp) pr-1)
(D.39)
k 3
Hence, the n + oo limit, only the k 1 term survives, and
lim iAB = iA Σ 24t R, n=000
(D.40)
Similarly, consider
Σ ina
öt
Swa
8Tan
C=
(D.41)
Vn
acAo
aED
aEAr
aeD
In the + oo limit, the only terms that survive are 85a when ((a) p for which Pa 1.
Combining the two equations above, we have
lim E, ((8ra, 8%/, Swi) (eE in 100000
Σ
2 T,
P + Σ ÔT. =: (D.42)
1=1
a:l(a)=p
30

---

D.4 MGF at general p in the n - oo limit to show Claim 3.7
For succinctness, we denote the following vectors of (rescaled) variables t (ta)aED.
d (db/n)<ED,
(ne/1)oEAA
öt ((tta/n=)))r )aED We can then write the MGF as
ôd (ōdp n - BED:
ôn (Dee//)cEAoo
(D.43)
By [M](C))] = Ey (xpp(e
Σ 2,) 33 = Σ (t), n 1=1
(D.44)
1=
where
- = -T T S U exp (t, d, + E.. (ôt, 5d, 5n))
(D.45)
Here, n, and E, are polynomials of their arguments whose coefficients can depend n. Furthermore, TV s((a)) and U are summing operators defined in Eqs. (D.20). (.21)) (D.22) earlier.
We now introduce dummy variables (ÔT, ön, w, ,w) which will replace (őt, d, öd, n, on) via Dirac delta functions:
(t) S J J8..n,8n..000
T
exp (T, n. w. (öT, ow))
8(ôt - 8r) n)) 8n)o(n - w))(ōn ow)
Sormona / J 57,
T (r exp (T n. w) - (ÔT, 6n, dw))
(8t-6))))) + (5d-5n) (n-))) (:n---i----n-a-en ow))
where in the last line we used the Fourier representation of delta functions and introduced dual variables (6f, , nj 81). W. 60).
Note that (((x) is sum over (d, öd, öt.) and U, is sum over (n, ōn). We can apply them directly to the relevant exponentials since their dependence is now linear, but involves the dual variables.
First, let evaluate the s((²) sum, which is defined in Eq. (D.21 composition of many little- sums. We start by considering a single little-sum with parameters (Ki, 611, K111) of the following form:
Fa (K1, KII, Kmn) = $1
erida traddd
(D.46)
) 8ta
Σ
lat Σ da-
Qua
Σ
(a-
Quo Q"a-- mida + t +8m8t
Nat ta
na-
Tha
tu
This can be evaluated using
Qa sinh x|
Qa and the basic identity
Edst (lat (+1) (- 1a enda
Applying this to the two inner sums
Fa. we get that
Fa Fa(Ki, K11, Kmn)
Q:a Σ
(
to
ta tt-
[2sinh(Ma kn)] sinh(K1 kn)) Minôt
lat.ta-
= (2Qa)) )a [sinl((x] + km)e + sinh(kr - "onne"mnn "m]
= (4Qa) ymu (sinh Ki cosh in cosh KIι + cosh kj sinh in sinh (D.47)
Returning to St. get
n'o Coa
S(ta) (e .0 151
II
la! Jo Sdu Bi
(4nQa)*a
iin Ma n nl
dūa 87
ia
díaa sin
8ia t0
)ta)""
II aED
cos
cos
cos
sin
(D.48)
to!
nPw
n Pu no.
31

---

Next, for U we have from the multinomial theorem that
U
Σ
II aEAD
Qa
Σ
na
{na)
Mat
{nataEAo
ona
( acAo
2Qa @waeaal
wwa/n
cos
dwa
n-t
(D.49)
Vn
Take n + oo limit of (t). We now take the n
+ limit while keeping t fixed, assuming
An An Recall the fact from Appendix D.3 that < Pa < 1 when {(a) p and Pa
when {(a) = Then taking the + do limit of (D.48 yields
(QQa)
lim S ( 18 in
[ga (dTa, Aa, diaa))
(D.50)
n00
La!
aED
where
iña
dñjafa.
((a) < {(a)
Io (ofa na. 89)a)
(D.51)
iñaa cos 8iaa dia sin dna
Similarly, taking the n + oo limit of D.49 gives
lim U [e n- exp
Σ
2Q (iwa
(D.52)
2
aεAa
where used the fact that Eaes. 2Qa 1. We also note that for any sequence of functions (f)(t)), that pointwise converges to ftt), have
lim (t) n-000
lim nd
n2
Σ
fn(t)
Σ
lazt
to t.E0 1a=t
(D.53)
Plugging these back into (t), we get in the limit
e(l) = lim (1)
Tt ((tt...)) -6 -8 - 1 w---i---i880 18
br 87. 64, 9899,89,0000
(4Qa)'
(22222))600-11 62) II
Iga (dfa Ma. 8ña) )
ta!
(D.54)
where denoted the vector Q (Qa)aEAo and (2Q ow); 2Q mean element-wise product.
Sum over e(t) to get MGF. Now we perform the sum over f to get the moment- moment-generatinn generating function of the overlap distribution, since (heuristically) lim,- Ey [M, D e(t). Note that
TT'(()
Σ f(t).
(D.55)
20,0D
So in the limit, effectively summing over (ta) independently. We can also the fact from 26 Lemma D.2] that T(t, n, w) is linear in f,
n.w) Σ CaPa(n.w)
(D.56)
aED
Hence, we have
e(t) [
E 188 in in
1897.nn i w) 188 (20 a2)
1=0
Σ
4Qaga n. 8. (a(w)) Pa
_(8r,ōn 5n.)w)
exp
a
(D.57)
32

---

The integrals over (@,w) w) yield Dirac delta functions that set each wa = 2Qa. The integral over dā yields Gaussian density function for dw, each with mean and variance 2Qa. So we can set dwaa = Ga ~ (0, 2Qa). and replace the integrals over (dw, dw) with an expectation over G (Ga)aEAo Our expression then simplifies to
e(t) = E&G
exp
Σ aED
(Qaga(dt, n. (())e ((67,,n,
dr.n.8n 8..0
1=0
(D.58)
ÔT d...m,ōn 64 n.89
To do the remaining integrals, it is necessary to use additional structure of the polynomials Pa. 9a and E. From [26]. we know there ordering (-) of the elements of D such that the n dependence Pa is only on (17 b < a). Furthermore, from Appendix D.3 we know E(ôT, on, dw) has
particular form:
E(ôr,ôn, dw) = Σ ( +
Σ
8Tb.
(D.59)
aED
b:((b)=p
We also know that the ôr dependence in Ra is only (ÔTσ : ((b) {(a)). More explicitly, from Eq. D.38).
(ōT G) = 2, where r = E(a) and X, EbE b,Gb,
EbED, b,ôTb:
(D.60)
Let us now write out the exponent S in (D.58) using the form of ga in D.51) and E in D.59
S = -00 8T
in n iōn on
Σ
(iaaa - óñj dfaa ( (m(2))) +
Σ
4Qa cos òña 8ia sin 3e Pan (n).2QQ)
a <p
oE oED:
+i Σ
Ra (ŌT G) + Σ 6lb.
aED
b:((b)=p
Regrouping terms, we have
S=
Σ
iia Pa -aa)=
Σ
(4a cos Pa(n.Q))
maa)
<ED:
aED:t(a)=p
Σ
igta (italiiQ.c (i4Q (14Qa Palm220) òTa) +
idia (iAQa sin Pa(,.2)) STa)
a aED:((a)<p
aED:((a)=p
Σ aED
iòna (a(T: G) - -8faa] +
Σ
8Tb.
(D.61)
bED:(()==
Integrating over (ń) 17) yields delta functions that assign 7aa PQ when E(a) < or Ma = =QQa cos dijae" Pa (q)2)) when {(a) = p. Note 4Qae"a = 2W, where Wa is defined the same way for q-spin models in (26. so we will use Wa eQa Pa in what follows. Then, integrating over (8n. 5r)) yields delta functions that assign dija (āT Note here the linear dependence in ō1%, in E(ôT, 5n, 8w), as in Eq. D.59p. is important for allowing us evaluate the integrals. Finally, integrating over (8f, 87) yields delta functions that assign ôT, idQaBaefe
i2W Ra when {(a) < p. and 8T. = i4Qa sin Pae i2Wa sin Ra when f(a) = p. Note that these assignments by delta functions are consistent if we perform the integrals according to the ascending order of the set D. since Pa- Ra only depend on the variables [76, 87,) x a}, which would have already been assigned values from earlier integrals.
The MGF of the overlap distribution is then
lim By By(,(()) n00
=
Σ e(l) = EG
exp (5
Σ
i2W, sin Rb (G)
(D.62)
1=0
be =
33

---

In what follows, let us denote D, = { D: ((b) = r) for < Also let 7r =2gA and
G EaE aiGa. Note G ~~ (V, 1) since G. (0, 2Qa) and Eae Ao 2Qa 1. To get sense of the MGF formula, observe that
((a) =1 = Ra = 51a9Ga
((a) = 2
Ra - 5202
Σ
9-1 = =202 R2
Σ :2Wbb))
bED,
BED:
Note in the last line used 6963 b1. Doing this iteratively, we that when ((a) T, we have
Ra -,K, where K, = 3r Σ
22
9-1 K
(D.63)
BED, D
with initial condition K1 "1- Note that K, ~ A 11ke-1)"-1/(60 -1/(0-- when 9 > and Kr A" when g = 2. Furthermore, using the fact that sin(aX) = a sin X when a E {=1}. we have from Eq. (D622) that
RosOa
Σ
i2aa;) sin [Kp [KGG(e-1"]
(D.64)
aED,
which is indeed of the form of the sine-Gausse Gausiin law in Claim 3.7
We then note that the factors
Σ
2W
Σ bED,
2W6b
(D.65)
BE DED
can be evaluated efficiently using the iterative procedure in [25 due Theorem 3 in 26] We give
this procedure in the section that immediately follows. This concludes the derivation that shows Claim 3.7
D.5 self contained formula for ap(7, B) and bp(r, 3)
In this section, we give self-contained description of the formula for (Ap. bp), following Eq. (D64]. Let B be the set of (2p + 1)-bit strings indexed as B = {(11, 22,..., 2p, 2-p- p....... 2-1) 2j {+1]}. Define
1 f(z)
2 (211e
(22) (zp- (5p-1/et00 10000 (zp) (2ple (20)
(zole 18,x1 |=p) (z-ple
118p-11---0- -1pp11 1z-(0-1) ... (z_2/e (
(D.66)
where
E (+1, 11, 1}, and (=1 (x 122) cos B if = 22, or i (3) otherwise. Define matrices
H ((2++)) for 0 I m S p as follows. For j, E fl...., ....... -0 1), let
H = ELEB f(=)2zz ( and
P
H im
Σ fz)2geh exp ZEB
(-9
9
Σ
(H) (1)=-1))0 8-1 28 for mmsmmmp (D.67)
j.k
2
jkk==p
where we use the convention that 7-r - for 1 < < p. and 0. Note these matrices first appeared (25] in the context of assessing the performance of the QAOA on locally treelike Max-q-XORSAT problems and can be evaluated in 4pp24) time.
Once we have the matrix H
we compute for 1 S S P.
= i Σ f(z)
2r 2-,
1 2,2
Σ
Hil j,k
exp
2
2
2
ZEB
#=++1
j.k=-p
(D.68)
Finally, let b, 2 and for 2.3.....P1 compute
b, 22 (ar-16
(D.69)
34

---

Example formula at 2. As an example, we now describe the explicit formula at 2, which applies in the regime where A, An(9-2+1/9)/2 (note here Ep=2 = 1/q). We have
b2 29 20(0 1)m
sin (2,1)
Q2 = - 24(n + 71 sin 2,3x x
cos² 31 + 847172 Re(X] sin? 31 + 22(T +2 Re(X]) sin 231 sin(4471 Im Im[x])]
where (cos 2,31 + 2n sin ) 9-1 Then the overlap - d2 sin(b2A"G'oo1)"
Although the above formula is complicated, we can understand the scaling with by considering a simple choice of ?1 = 72 1/2 and B1 32 x/4. Then the above simplifies
b2 e 221)/22007
a2 = - cosh(e (1 (1-1)/2 si] e 112 sin(e ()//2 cos(TT/2))
(D.70)
E
Signal boosting with 1-step QAOA
Consider a scenario where we have some prior information about the signal, in the form of a weak estimator that overlaps partially with the true signal. Our goal to boost the overlap of this weak estimator. We study the SNR threshold of the 1-step of QAOA and compare it to the 1-step of power iteration. For QAOA, we encode the weak estimator into the initial state: rather than initializing with the uniform superposition across all bit-strings [s), we bias a fraction of the qubits toward the signal. For power iteration, instead of starting from a uniform vector, we sample from Bernoulli distribution biased toward the signal.
More precisely, for QAOA consider the following initial state:
(hiased)
Oo (uy) + sin 02 (
(E.1)
jml
where the 8 are drawn i.i.d. according to
T T/4, 0, = TT/4 - 5,
with probability 1
with probability & & n
(E.2)
and > 0. As in Eq. 2.3 we prepare the 1-step QAOA state as l7, B) 3..3% biased = -iBB ein binsed)
Note the spiked tensor model Y is encoded in this state through C(ar) = (Y. a (09)/n(e-2))) The following theorem concerns the SNR threshold
weak recovery and the distribution overlap
RQAOA,biased = ú u/n between a sample ~ I7, B) biased and the signal u.
Theorem 2 (Signal boosting with 1-step QAOA), Consider the biased 1-step QAOA state 1y, B) biased as defined above. Fix y 0, [0, 2m.. 8 E x/4], and let k = O(π() for 1/2 < 1. Suppose
lim n20000
(1/n(1-0(0-1) = =A
(E.3)
Then, over the randomness of Y and quantum measurement, the overlap RQAOA, biased of 1-step QAOA converges in probability to
RQAOA,biasod
P -2x? (2n() sin (2q4y (2n
(E.4)
We give the proof Theorem in Appendix E.I that follows.
Remark E. Theorem 2 considers an initial state with fraction k/n of qubits biased toward the sig- nal vector u, representing some side information. It shows that the SNR threshold is (1-c)(g--1)) which becomes lower with increasing side information k/n = e-1 In particular, if = ( the weak recovery threshold of 1-step QAOA improves (-n(9-))/4) compared to the ()1 threshold given by Theorem I without any initial overlap between the state and planted signal.
35

---

Comparison with classical tensor power iteration. 1-step QAOA that provided by 1-step power iteration. Recall the 1-step tensor power iteration
We compare the boosting produced by the
estimator 2. is ú biased = vnY (11-1)) /
1ll. where in this case, analogously to Eq. E.I the initial vector d6 2ipusdse has its entry (ūo, (iiseid ) sampled as
binsed
0 D.iisse
@(g-1)
u//Vn, -u//Vn,
with probability ] [1+ & sin (26)
(ito,biusedl) j
(E.5)
with probability
2 A sin(2))
One can check that Vniio, binsed (biassed) is sample from the biased initial QAOA state, so that we are making fair comparison with QAOA. In the following proposition, we show that the required SNR for the 1-step power iteration estimator is also ((n()=o((-))) and we provide the distribution [A1,biased /n between the power iteration estimator th biased and the signal
of overlap Riibid u.
Proposition E.2 (Signal boosting with 1-step tensor power iteration). Assume that the rescaled segnal-to-noice ratio has limit lim An/n!!-o(e-1) = A. Then over the randonness of W and initialization úo biased, the overlap RpI.biased of the power iteration estimator with the signal converges in probability to
Risse P sin(arctan( A sin sin"=((26))]
(E.6)
The proof of Proposition E.2 is contained in Appendix H.2 This shows yet again that the QAOA has the same asymptotic computational efficiency as power iteration. Nevertheless, in the << 1 regime, by choosing y = 1/2./ and / = x/8, the QAOA achieves an overlap that is larger than power iteration by factor //e..
E.1 Proof of Theorem 2
Without loss of generality, we assume that 1. Recall that the initial state is given by Eq. EE.I). which we can rewrite as
bblased) - n II coos 0,)8,, (sin )00 1(z)
(E.7)
1=1
where 0, = 7/44 with probability - k/n, and 0, T ō with probability k/n.
To prove Theorem 2. it suffices to show that the moment-gentn generating function (MGF) of the QAOA
overlap converges to the MGF of deterministic variable as follows:
lim Eg Ey [M,, (S)] = exp [<- 227" sin(2 sin (2qA sin (26)r-1) =: (().
(E.8)
2-000
The argument for the proof is the same as that for Theorem [b), except that we must prove analogous
versions of Lemma C.I C.2 and C.3 which become Lemma E.3 E.4 and [.. respectively.
Lemma E.3. The expected moment-gentt noment-generating function at p = for the overlap of the QAOA
initialized with (Sbiased) is given by
Eg E [Mn(C)] Σ
n
(n-](m22)))]/ sinh((/n) sin( (1 (1-*
k +
cos
En,,.
n
71
(E.9)
where
1
En,t 2t +
sin' (2 (5),
(5)
2niEt/(2e+ 1) Zn.());
1=-1
1
n n-b
(1,
(es/n cos² B + -c/n sin? (3)=+ (e (c/n cos² 3 + S/0 sin? 3y
-
[T, =n-
ks))(2)))
(28)
1 (25)
1
n
x
(E.10)
36

---

The proof of Lemma E.3 is deferred to Section E.2 (Lemma C.I the presence of the two terms
Note the only difference from the unbiased case
k cos (26)
kssi(26) n
(1
A: sin(()))
+
and
1
n
n
7
and the rescaled power of n in the exponent.
We further define
A lim An:
70000
sinh(C/n)) sin() (1 (1-#) k +
cos(26)
)
La
E (n-))//00))
En,e (E.11)
[se 2012 sin(23) (2n222 sin
where the definition of En, is given in Eq. (E.10). Then it is easy to see that
Eg Ey [Mn(
Σ Ine
M())
Σ
4.
As consequence, we have
T Iel
[M(() - (M()) S
Σ
4
Σ
(E.
1=0
127+1
I=T+1
The following lemma gives the limit of Fn, for fixed as n - oc, which indicates that T, is the limit of Ln,t-
Lemma E.4. For any fixed integer 1, we have
lim En, sin' sin' sin = Ec.
(E.13)
As a consequence, we have
lim In,t It. n0000
Lemma E.S. For any 1. S n and ( S we have
Ln,1
(1811) + 1)elsl Se:
(E.14)
where
8t 00.
(E.
The proof of Lemma E.4 that these two lemmas hold. By the fact that E J is finite and by Lemma E.5 for any > 0, there exists T T2 such that
E.4jand and
E.S deferred Section and E.4 respectively. Now we assume
Σ SE/3. 12
Σ
S
2T
Furthermore, by Lemma E.4 there exists N = N₂ such that as long as 2 No, we have
Σ Unt 4el S E/33.
As consequence, by Eq. E..22 for any n ns and < n, have
Ey Ey (M,(()) (000))M(M)) M(5)
Σ Ine
11+
Σ
4
S E.
(E.16)
t=U
12T+11
T++1
This proves Eq. (E.8) as desired, and hence finishes the proof of Theorem
37

---

E.2
Proof of Lemma E.3
With an added expectation over 0, Eq. (B.4) still holds with modified Qa:
Eg By [M](([]]
Σ
n
II aEB
Qa
exp
na.
(ma)
2n9-1
(na)
am
in
5
Σ
+
ass Ma.
Um
(E.17)
72
11
and
Q aa) (m)))))))))) f3.x,5(a1, am, 02)
(E.18)
with f defined below:
sin(28) (28)
cos B,
if
11,1,1),
-1 (1 A (26)
sin cos B,
if (2]. ( (1, -1),
$1 {1 k kin((25)
cos B,
if (2)., (L, 1,,
(1 k + (2)
i sin cos B,
if (2]. (1,-1,-1) 1),
A cos(26)
sin B cos B3
(2).25).2) (-1,1,1),
(1 ksin(26) sin B.
if (2).,f])
11-1,1,-1,
(1 cost (6))
sin , cos 33
if (f). --11,-1,
2 (28))
sin B
if (f). (-1, 10,--1,111 -1). 1).
(E.19)
This proof follows very closely that of Theorem [b) in Appendix C From the change of variables in Eq.
CC100) to the breaking up Eq. (C.15), the same expression still hold, except that we redefine
A,
A, n (1 (1=e))e11,, which amounts to the power of in the exponential changing: when compared
to Eq. C.15):
Eg Ey [M)
Σ
n
y 1 (nn200
Σ
(
n n-t
(4,t_)
(T,IT]
4+h=
T+ -
T+
0411000 1"_
Σ
T- Q²1 0414400 0=4L c(S/n)(++ -L--
n+++
4_
1
Q Q= Σ
2+ Q"=
14+-)
dp
cinnlld4 dd +T+ ((T (d4 - 119/16111--
(E.20)
However, it is not true anymore that Q+++ = Q+++ and Q- =Q QQ++ in general. We use the identity in Eq. (C.16) to write
Eg Ey [M,((S]
Σ
(n (n- -1:0--nn--
(n_22)
Σ
(tx)tt
Σ
n n-b
#4+T-=n- (T,TT)
t=
4+
(2Q 204++e5/n -2Q_--e-s/npt (onn)++(20+-p)) -c/n f +2Q_4_ - (((/n)(+---))
2n-1
4
1-
Q Qat Qthh
Q Q²t== Q"
1++
12
d+
Minilld -d - ((T (dd d 1190011
38

---

Then we redefine
(0,,((1) 2
E
n -
(eS/n cos? B + e -
(/- c/" sin? 3) (e- c/u cos? 3 el sin? 3)-
[4,
=n-t
[ ts (20)
T+
-- ks)) )
(E.21)
and, analogously to Eq. (C.19) write
Eg Ev [Mn(S]]
Σ n
7 (n-2-(nn22)//m
E
(4, (1)11)
t Σ
( t+
Q++ Q==
(1++-
4t
d+
n4 )0t
1-
2+h 0TL Q= (((/n))t+---) - d-).
d_
(E.22)
Using the discrete Fourier transform, we have
Eg Ey [Mn({)]
Σ
(mm)==(mm20))//mm Σ
(4,t_ )
Σ
14
2+++= Q"
(1++-)
4+L=1
d1
f-
Q Q= (((/n)(4+--))
1
-n- (5)
-d
14
21 +
5=-t
Σ
( (1+,
e((/a)le+-e_)
(4,6_
44 4+t==t
(-1)- 28 5=-1
[2iQ++ sin (T (2T2/ + 111) (5)
(E.23)
since the same relations between Q++-, Q Q-++. Q+ -----QQ---0 Q-- hold. Finally,
(mn 20) (sinh(S/n) sin()))) (1- k
1c cos(
*
Eg By [Mx
7
7
Sin(2n/(21+1))) 2m,
x
(F.24)
2t +
which is analogous to Eq. CC.4
This completes the proof of Lemma E.3
E.3 Proof of Lemma
We first look at the limit of (I) for fixed integer -t S 1 $ t. Letting T, = (eS/n cos? B
-c/n sin? B), Un (e- cos² 3 + e//n sin? 3) and k sin())) n, we can write
n n
(l) -
Σ
T U (1+c)*+ (1 (1- c)- -----he T+,T_
T4+T =nー
(E.25)
We let G. = (T4 - +en 1(E-((11)) - ((()-)))/oo / so that
Zn,(l!) = EG. oo
(E.26)
39

---

where Binom - -t +11 so that Gn - G GNNN, by the central limit theorem since Er, [+ --]==0t = en f(c 1) and Var [T+ - [-] = (n t)(1 -2
Recall that sin(28) where 1/2 < c < 1. It follows that linn To ((cct()))(((+())122 lim,-+0o U/4 (=(=((-1))at((((t))//2 as well as lim Ty lim Un UN 1. Hence, for
any fixed -t 1 t, it follows that
(VnG, + on - toa-tlcti 1) +1 (VnG, + t(c 1) 1)9
1) 1)
[Vvn ne sin(28) t(n n sin + + + 1)4
1)
- (VvnG, + n + (2n
t(n - sin (26) + 1) - 1)8
+ sin
(E.27)
With this, we can conclude
lim (l) 2200)21sin"~1220
(E.28)
Hence
lim En,t 2t sin((2mt/ + 1))² 22 2211///2241112222222111100000 (200)
= =sin' -in' sin (26)),
(E.29)
where we used Lemma C.4 with X with probability 1. This completes the proof of Lemma E.4
E.4 Proof of Lemma D.5
We first bound Zn (l)):
(2n S 2 +1
Σ
n n-t
6c/" cos? B te e--5/n
</n "insinn 3
</n cos² 8 + c//n sin? 8
[T,TT]
=
(25)
1 (in()
x
11
n n-t) tt ) (1 (1- (2))
(1+ siin(2)) n
)T e Kl// Kl/n
Σ
2
T+,
+T mn-t
= e (m-0)////n.)
I 14|
(E.30)
The rest of the proof is exactly as the proof of Lemma extra factor which can bound:
C.3
except that Ln involves the following
(1-
k ccos(20)
(E.31)
n
So the end bound on Anae ends up with a different constant factor:
T
(181CI) 1)e
(E.32)
This finishes the proof of Lemma E.5
F Finite calculation for 1-step QAOA on the spiked matrix (q = 2)
In this appendix, we calculate the average squared overlap outputted by the QAOA at any finite problem dimension and obtain the formula we reported in Eq. (4.1). As done in Appendix B we first take to be the all-one vector without loss of generality. The cost function is
An
C(z)
where
YA
+ Vn
Wak
(F.I)
j,k=1
40

---

Here W,, ~ 10)
The QAOA state at level p with this cost function is
hr.3) = e 18B 6 inC (6).
(F.2)
We interested in the overlap of the QAOA output with the hidden signal u 1. Following the same method as in Appendix we can write the disorder-averaged overlap as
By (Ro
Σ {ma?
n (mai)
II aEB
Tu Ea,DEn Pasmamat thn EnDen Pa
1
Σ
Um
n
}
vEB
(F.3)
where
B = {(11. am: a2) : as E {+1}},
(F.4)
1 2 (a1 (a11e [1) (1le-188 18x a2))
Qa
(F.5)
and
ab (a,b, a2b2).
(F.6)
We can calculate Ey (R A 7, explicitly with careful organization of the sum. To this end, similar to what we did in Section C.2.1 we perform a change of variables given by
4 4 +
t_ n. + 1--
d. = 1 +
d_ = n4 -4 - 71
(F.7)
T+ ++++
T_ -4+++ 11 -
A+ = ++++
A_ = 14-+ - -
Observe that these variables completely determine {Ma B). Furthermore, let
t = T+ + T_. Using the identity aib, a2h2 = [(a) + a2) - b2) + (a) - a2) + b2)1/2, we can show that
= 4 +t and thus
(F.8)
Σ aab = -8:2(1r l),
(F.9)
B
Σ
Pabambm nan 47 d_ ( T-),
(F.10)
B
Σ um = - + A AA.
(F.11)
BEB
Plugging these into FB
and breaking up the sum yield
Σ (1)
Σ (M-1))
Ey (RR
--7 t//n
n
(4,t_)
(t,T-
4th
T+tt- =
T+
Q"
Q" Q- (14 -t A4 A_)²
11+++/
114-4/
t4
Q Q=
Σ
f_
Q
Q i4dd - (oldd-d-)(rr d-+
1++
n
d+
(F.12)
where we' 'ee denoted A 4Xy/n as shorthand. Note we need to perform these sums carefully chosen order in order to get closed-form answer at the end.
We start with the last line, where & sin B3 cos for any x, y E { Then, for example we have
over dj. We can use the fact that Q+z- -Q
Σ d+
t+ n
Q++== Qu t ind (T+ (T+-T-) (2iQ +- sin(A(T, --)1
(F.13)
41

---

After doing the same thing for the sum over d_, we get
Ey (Ros
1
(72 f)/n Σ
t
T4 =n- (t,TT-)
Σ
n2
(1.1-)
t=
4 =t
Σ
T+
Q+ Q E
Q7 0+=+ (t+ to - A+ A_)²
(++++)
(+-+)
A
[2iQ++
- -T-1l) Sii(++-sin[Art-
(-1)+((=----
Next, consider the sums over {(t+, f-) it + =t.. +t==th. We can use the following identity
68=00- if 0,
Σ 1 r+a=t r,
1- -3)
261=1,
if = 1,
(F.14)
if = 2. 86
Collecting the relevant terms and applying this identity yield
Σ ( (4+ -t- + (-+1++
L+c==
801=2 4(A+ A )o11 + +A+ - P0 (F.15)
So we have
By [(
(2
1
Σ
n2
47 172t(1- f)/n Σ
(n-t)
30Q++=sin|A(6 - ---
n
T4.
Σ
T+
Q Q- Σ T-
2 0+ e-
n++++)
114
A+
A_
86,=2 + 4(4+ ) + (A+ 2
(F.16)
Note the Kronecker deltas will collapse the sum over t, so it remains to evaluate the sums over A and T+. To perform the sum over A+, note that Q+++ 1N2 cos² 3 and Q 1 sin? 3, for any I, E } Thus, we can use the following identity
1, T+ cos 2,3,
if 1:
2
T+ n+++)
(*+)*
if k: = 1,
(F.17)
T+ [1 + (r+ 1) cos (2:3),
if k = 2,
write
0 o"_ Σ {(T+ T- Qth Q""L'00 )
2 Σ
(A A
1++++
2_ (2-+))
A.
1,
if = 0,
(T4 T- (,8))
if k 1,
(F.18)
74 + T_
[ + +
1) -1- (1+++++) c2s))
if 2.
Finally, we just need to evaluate the sum over T subject to the three possible values of Returning to F.16 can break E (R3 S2 + St + So into three parts, corresponding to f = 2, 0.
42

---

where
S
8
12
872(n (n- 2//n
Σ
(n-2)
(2QQ++ sin[A(r+ - r-)1] 2- (F.19)
(n-2),
n
2
T4,
+4 =n-
S
4 11
17
(n 1)
Σ
(20Q++ sin(A(T+ - -- 2- - r-) cos 23,
n²
1
T4,7-
++
(F.20)
1
Su
(F.21)
Finally, since, sin (e E (2i)) we have the following identities:
Σ
sin [A(r s)] 2m cos 2A].
(F.22)
Σ
m
sin(A(r - s)](r - s) = s))=
=22 m sin A cosmm-_ A.
(F.23)
8,8)
++==m
Thus, plugging in A 4 n and using the fact that 2iQ++- = 1/2 sin 23, we arrive
Ey ( 71
8y (n sin 2inn( cos"
2n
1 1- (m-1)/ sin(4 sin(4\7//n) cos" 24X7//n) (F24)
1
+
n
G Additional numerical simulations
In this appendix, complementing the simulation results in Section additional numerical simulations are performed for S S at q = 2 and 5 S at =
Fig. 4 displays the second moment of QAOA overlap versus problem dimension n. The y-axis plots the simulated second moment subtracting the theoretical value in the oo limit. For all demonstrated (p, q) pairs, the simulation appears to converge the theoretical value with order 1/n deviations. This is consistent with the rigorous finite-n formula for (p, q) = (1, 2) in Eq. (F244.
0.4
0.3
(Rogoo) - liim (RQuo
Q
2
q
0.2
0.2
lime-
0.1
p=1
0.1
[Rig
0.05
0.05
0.03
problem size
problem size
Figure 4: Log-log plots of the difference between observed overlap (averaged over instances and quantum measurements) at various problem dimension and the predicted value from the sine- Gaussian law in the n - oo limit. Different colored lines correspond to different QAOA depth with parameters (7, B) set to be the same as in Table We choose A = 0.2, An = 1/(p))) (left), and An An 11/12/1(22 1112211))]11)) 11]//2 (right). Error bars are standard errors of the mean.
Our numerical simulations use the GenQAOA library, available at huttps://githut com/ leologist/ /eesstt/GGenAAAAA The simulations are conducted on a laptop (MacBook Pro M2), where the simulation of each 26-qubit instance with p-step QAOA for 1 S p S 7 took about 160 seconds. Data used in the figures available upon request.
43

---

Analysis of classical power iteration algorithm
H.1
Proof of Proposition 3.3
Define An = An/n(1111//01 1)/2 we have
Y (( 1 An (ito; u)
u
W "]= A.
Vn V' h
u 1
vn
Vn
where we define Gn = (ūo, u), and h independent h, and G,, converges in distribution to Gaussian random variable G G~ N/ ~ (00 1n). As consequence, we have
W Then marginally over W and uo. we have G2.
(Gns (
Ola I112) 2s (G, V 220
n -
This gives
(, d1)/n= An Gg- + (u, hi/n
AG
V --000
(Y @ 1112
This proves the Proposition 3.3
H.2 Proof of Proposition
In this proof, we denote in short ún ú biased
Define An An/n1 (1-(e-1)))))) we have
Y (
0(a-1) An (1112))-0(0) (ūt, 10 Vn +
W W
An Un-1
Vn + h,
vn
Vn
where we define Un = n 1/2- w), and h = W Then marginally over W and ún we have Un sin() and h ~ No. As consequence, have
(Un, || (000000000000000 1112)) Py (sin(28), VI AP sin (20 00
This gives
A, (u, h)/n
sin Sin( n - 00.
(u1, in/nn
Y a0
60 1al----1ll 111l2
A si
This proves the Proposition E.2
H.3 Proof of Proposition 3.9
We prove this proposition using results in The notations in are slightly different from the notations in this paper, and in the following, we will adopt the notations in the former.
Suppose we observe the spiked tensor model
T + W.
(H.1)
where v ~ Unif((+1/Vn)") and each element of W is iid Gaussian. Note that the X, in Eq. different from the X, in Eq. 1.11) We should take X, = Vnd, so that X (n/n(9-1+ep)1/ A.
H.1
Consider the tensor power iteration algorithm with initialization 8 56 Unif($ 1), and
g-+1 = -T('==T(o- = Xn (v, 8'y0-1 + W 8+t1 = - / (H.2)
We let ar := Xr, (U, 5
6 100- Then 33 shows the following lemma.
Lemma H.l (Lemma 3.2 of
Consider the spiked tensor model as Eq. H. and consider H.2 For any fixed & E (1/4, 1/2), define the stopping time
the tensor power iteration
Te = min {1 E NN+ laol 2 n²}.
(H.3)
Then, there exists an absolute constant C. > 0, such that with probability no less than 1-exp(-Cvm) the following happens: For all t < min(T,, n 1/2((-11)) we have
d ac+1 (Anm ( + by + + 9-
0,
(H.4)
where Z, ~ NN(0 1) is independent of (S,, ac. by, c). 1/6
G 1 + 1/6,, bel < On 1/4 1/460--))6-1/1
les
5 Cn 2(4 2(1-))(--11))
(H.5)
44

---

We take ([(g - -11/2(-11-
to be fixed. By Lemma H.1 for fixed N4, with high probability, we have T. 2 p. as well the upper bounds indicated Eq. (H.5) for all
t S 1. Applying Eq. (H.4) recursively implies that
(1 or(1)) n 12 M/ - G~ NN,11.
By the last equation page of 33
that (for H, 20.
v" a2p
E
((p-1)
W w 1911
where dag Rid I.), and de
i1,da, in 12 1. Invoking
the uniform law large numbers, we are able to conclude that RpI (0,, u) w)/l|oP|12 4 (anlaaccan(A//s ((1)))) This concludes the proof of Proposition
45

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justifiicton right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]", ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: We have carefully written the abstract and introduction to accurately reflect the paper's contributions and limitations.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
46

---

Justification: We are explicit in our abstract and introduction that our theoretical results on p-step QAOA are only rigorous for p = 1 and rely on heuristics for p > We also conduct careful comparisons to classical algorithms in Section 3
We have also explicitly stated in our Introduction and Discussion sections that our results are limited to constant-step QAOA.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Every theorem, proposition, and lemma is very clear about the assumptions.
Results that depend on conjectures are listed as claims with explicit reference to the conjec- tures.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
47

---

Answer: [Yes]
Justification: The sections on numeric experiments include detailed choices of all parameters that may reproduce the simulation results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, it may be that access to the model is limited in some way (e.g.. registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code for numerical simulation based on an open-source library as stated in Appendix G
The data used to generate the figures are available upon request.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cd.
quuides/CodeSuumissst
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https! for more details.
//nips /nipps.ccppublll http:cccppppccc/tettette.e...clt http:/plllcggddee/eeeeee /oupuddeee/ddduuuuiisiiioooooo..
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
48

---

The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
We do run any machine learning experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: All of the figures in this paper either plot all acquired data points explicitly, or show error bars which are explained the caption.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (c.g. negative error rates).
If error bars are reported in tables or plots. The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
49

---

Justification:
The information about compute resourees used for our numerical simulations is provided in Appendix G
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Question:
Answer: [Yes]
Justification: We abide by the Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our paper is theoretical study of a quantum algorithm applied to a statistical estimation problem. There is immediate societal impact to discuss.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (c.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI).
11. Safeguards
50

---

Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper is theoretical study of a quantum algorithm and hence does not pose such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwwpsswieeesseeeeeeeeee thcode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mooel part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
51

---

At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper involves neither crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The paper involves neither crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
52


Reviews:
[{"review_id": "e9U7NwOLRx", "reviewer": "Reviewer_TiV7", "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.\n\nThis 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.", "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})$?\n2) Do you see other candidate problems where techniques developed in this paper can potentially be used to study the performance of QAOA?", "limitations": "na", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "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.\n\nThe 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.\n\nThe 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\nRegarding 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.\n\nTo address the reviewer’s questions:\n\n1) 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.\n\n2) 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4yzSgs9Mak", "reviewer": "Reviewer_9dK4", "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.\n\nUsing 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.\n\nFor 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).\n\nAs 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. \nAs such, I believe the work is worth sharing to the community. Hence, I recommend accept.\n\n(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.)", "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.\nThe 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.\nHence, 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.\n\n2. 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.\"\nI understand that multiple (possibly infinite many) steps is needed to achieve a better performance for QAOA.\nHowever, 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.\nHence, whether there is a rigorous advantage for QAOA still remains unclear to me, even p approaching infinity.\n\n3. 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.\nI highly recommend the author(s) to be more careful about the phrasing of quantum advantage throughout the paper.", "limitations": "The limitations are addressed in the manuscript. I also summarized them in Weaknesses.\nYet, since this submission is a theory work, I think the practical limitation is not a big concern.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "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.\n\n2. Discovering an intriguing sine-Gaussian law also verified through numerical simulations.\n\n3. The manuscript is well written and explained.", "weaknesses": "1. The asymptotic analysis requires the number of qubits n approaching infinity, which is practically demanding.\n\n2. The analysis of the p-step QAOA is based on an heuristic calculation.\n\n3. It is not known if QAOA could achieve the same threshold as in the state of the art classical algorithm. \nNumerical experiments do provide some potentials of matching the result. Whether there is a quantum advantage remains unclear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\nWe now address the reviewer’s questions one-by-one:\n\n1) 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.\n\n2) 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.\n\n3) 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6l69IfY9Vt", "reviewer": "Reviewer_a21g", "summary": "The quantum approximate optimization algorithm is analyzed for the spiked tensor model. Weak recovery\nof 1-step QAOA is rigorously shown to matche that of 1-step tensor power iteration. Heuristic calculations for p-step QAOA\nmatche that of p-step tensor power iteration.", "questions": "Maybe authors could discuss the limitations of implementing such algorithms on NISQ devices ? Any realistic prospects ?", "limitations": "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, "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.\nWeak recovery of 1-step QAOA is rigorously shown to matche that of 1-step tensor power iteration. Heuristic calculations for p-step QAOA\nmatche that of p-step tensor power iteration. the paper argues that \nthat multi-step QAOA with tensor unfolding could achieve,\nthe asymptotic classical computation threshold of spiked q-tensors.\nThe asymptotic overlap distribution for p-step QAOA is characterized and \nsome 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\nAddressing 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OUd3lk0wiP", "reviewer": "Reviewer_nUte", "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.", "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?", "limitations": "- The analysis for p-step QAOA (where p > 1) relies on heuristic arguments from physics, which may not be as rigorous as desired.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "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.\n\n- 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.\n\n- 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.\n\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\nIn 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.\n\nTo 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qrNToo4xPK", "reviewer": "Reviewer_R5pw", "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\n1. 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. \n2. 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.\n3. 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$. \n\nBackground: 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.", "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?\n2. 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.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "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.\n2. 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.\n\nOn 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\nTo answer the reviewer’s questions:\n1) 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.\n\n2) 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
In this global rebuttal, we address the concern raised by Reviewers 2, 3, and 4 about our use of physics-style heuristics and the rigor of theoretical results. We emphasize that our result at depth $p=1$ is fully rigorous. While the analysis for $p>1$ is not fully rigorous due to the use of Dirac delta functions and an unjustified change in order of limits, we expect that it could be made rigorous with more advanced harmonic analysis techniques in dealing with Dirac delta functions. For example, Ref. [25] adopted a heuristic approach for analyzing the QAOA performance of another problem, and showed that changing the order of limits can be justified with a series of bound estimates and the dominated convergence theorem. 

In any case, we believe there is strong evidence for the correctness of our general $p$-step QAOA analysis because: (1) after setting $p=1$, our general-$p$ framework yields a result identical to our rigorous result at $p=1$ obtained with a different method, and (2) after setting $\lambda=0$, our result agrees with the prior rigorous result for the QAOA’s performance on spin glass models in Ref. [25]. The latter agreement is implicit in the discussion of Appendix D.4. Furthermore, our heuristic derivation can be viewed as an approach to obtain the correct result that is simpler than the rigorous method in Ref. [25], and may be applied to more general problems.

Meta-review: Consider statistical estimation in the spiked tensor model. The *weak recovery threshold* refers to the signal-to-noise ratio (SNR) above which weak recovery—an estimator that achieves non-trivial overlap with the signal—is possible. The paper proposes computing the maximum-likelihood estimate via the quantum approximate optimization algorithm (QAOA) and analyzes the weak recovery threshold of $p$-step QAOA.

- It is rigorously proved that 1-step QAOA achieves the same weak recovery threshold as 1-step tensor power iteration.
- It is proved that, if a heuristically proved claim regarding the sine-Gaussian law of the overlap holds, then $p$-step QAOA can be a constant factor better than that of $p$-step tensor power iteration.

Although the results of this paper do not surpass state-of-the-art classical algorithms and are not fully rigorous, it marks the first theoretical work to study QAOA for statistical estimation in the spiked tensor model and provides useful insights into whether there is a quantum advantage for this task. Hence, I suggest accepting this paper as a spotlight.
Decision: Accept (spotlight)