Quantum speed-ups for solving semidefinite relaxations of polynomial optimization

We study quantum algorithms for approximating Lasserre's hierarchy values for polynomial optimization. Let f,g₁,ldots,g_m be real polynomials in n variables and f^star the infimum of f over the semialgebraic set S(g)=\{x: g_i(x)ge 0\}. Let λ_k be the value of the order-k Lasserre relaxation. Assume either (i) f^star=λ_k and the optimum is attained in the ell₁-ball of radius 1/2, or (ii) S(g) lies in the simplex \{xge 0: sum_j x_jle 1/2\}, and the constraints define this simplex. After an appropriate coefficient rescaling, we give a quantum algorithm based on matrix multiplicative weights that approximates λ_k to accuracy varepsilon>0 with runtime, for fixed k, \[ On^{kvarepsilon-4}+n^k/2varepsilon^-5,\qquad O\!\lefts_gleft\[n^{kvarepsilon-4}+left(n^k+sum_i=1^m n^k-d_iright^{1/2}\!\varepsilon^{-5}\right\]\right), \] where s_g bounds the sparsity of the coefficient-matching matrices associated with the constraints. Classical matrix multiplicative-weights methods scale as O\(n^3kpoly(1/varepsilon\)) even in the unconstrained case. As an example, we obtain an O\(nvarepsilon^-4+sqrt{n}varepsilon^-5\) quantum algorithm for portfolio optimization, improving over the classical O\(n^ω+1log(1/varepsilon\)) bound with ωapprox2.373. Our approach builds on and sharpens the analysis of Apeldoorn and Gilyén for the SDPs arising in polynomial optimization. We also show how to implement the required block encodings without QRAM. Under the stated assumptions, our method achieves a super-quadratic speedup in the problem dimension for computing Lasserre relaxations.