BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.41.92//
CALSCALE:GREGORIAN
METHOD:PUBLISH
UID:e235b217-5606-4618-b58a-facf572f924f
X-WR-CALNAME:[ICQ] Mai Ngoc Hoang Anh (ENS Lyon) Quantum speed-ups for solv
 ing semidefinite relaxations of polynomial optimization
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
TZUNTIL:20261025T010000Z
BEGIN:STANDARD
TZNAME:CET
DTSTART:20241027T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RDATE:20251026T030000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:CEST
DTSTART:20240331T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20250330T020000
RDATE:20260329T020000
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:e235b217-5606-4618-b58a-facf572f924f
DTSTAMP:20260307T191231Z
CLASS:PUBLIC
DESCRIPTION:\nLet 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-bal
 l of radius 1/2 centered at the origin. Let lambda_k denote the value retu
 rned by Lasserre’s relaxation of order k for this problem\, and assume f* 
 = lambda_k. \n\n\nUnder appropriate coefficient rescaling of f and g_i\, o
 ur quantum algorithm\, which combines binary search with Hamiltonian updat
 es\, can compute an approximate value of lambda_k with accuracy epsilon an
 d the following runtimes: \n• Unconstrained case (S(g) = R^n): \nO( [ sqrt
 ( (n+2k choose n) ) + sqrt( (n+k choose n) ) / epsilon ] / epsilon^4 ) \n•
  Constrained case: \nO( s_g [ sqrt( (n+2k choose n) ) + sqrt(m) * sqrt( (n
 +k choose n) ) / epsilon ] / epsilon^4 )\, \nwhere s_g is the maximum numb
 er of nonzero coefficients of each g_i for i = 1\, …\, m. \n\n\nThese comp
 lexities are derived from the work of Apeldoorn and Gilyen. Within this fr
 amework\, our approach for solving Lasserre’s relaxations achieves a quadr
 atic speed-up over state-of-the-art methods in terms of the problem’s dime
 nsionality. We apply our quantum algorithm to compute the stability number
  of a graph\, achieving a triple speed-up over classical methods. \n\n\nTh
 is is joint work with Daniel Stilck Franca. \n\n\n\nhttps://combalgo.labri
 .fr/pmwiki.php/Groupe/Info-Quantique\n\nImport automatique depuis https://
 webmel.u-bordeaux.fr/home/bf-labri.ca@u-bordeaux.fr/gt.info-quantique.ics 
 par sync_icals_to_drupal.py pour gt-iq
DTSTART;TZID=Europe/Paris:20250207T104500
DTEND;TZID=Europe/Paris:20250207T114500
LOCATION:On Zoom
SEQUENCE:0
SUMMARY:[ICQ] Mai Ngoc Hoang Anh (ENS Lyon) Quantum speed-ups for solving s
 emidefinite relaxations of polynomial optimization
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR
