10:45
11:45

Let f, g1, …, gm be polynomials with real coefficients in n variables. Suppose the minimum f* of f over the semialgebraic set S(g) = {x in R^n : g_i(x) >= 0 for i = 1, …, m} is attained within the l_1-ball of radius 1/2 centered at the origin. Let lambda_k denote the value returned by Lasserre’s relaxation of order k for this problem, and assume f* = lambda_k.

Under appropriate coefficient rescaling of f and g_i, our quantum algorithm, which combines binary search with Hamiltonian updates, can compute an approximate value of lambda_k with accuracy epsilon and the following runtimes:
• Unconstrained case (S(g) = R^n):
O( [ sqrt( (n+2k choose n) ) + sqrt( (n+k choose n) ) / epsilon ] / epsilon^4 )
• Constrained case:
O( s_g [ sqrt( (n+2k choose n) ) + sqrt(m) * sqrt( (n+k choose n) ) / epsilon ] / epsilon^4 ),
where s_g is the maximum number of nonzero coefficients of each g_i for i = 1, …, m.

These complexities are derived from the work of Apeldoorn and Gilyen. Within this framework, our approach for solving Lasserre’s relaxations achieves a quadratic speed-up over state-of-the-art methods in terms of the problem’s dimensionality. We apply our quantum algorithm to compute the stability number of a graph, achieving a triple speed-up over classical methods.

This is joint work with Daniel Stilck Franca.

https://combalgo.labri.fr/pmwiki.php/Groupe/Info-Quantique

On Zoom