BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.41.92//
CALSCALE:GREGORIAN
METHOD:PUBLISH
UID:056b2f6b-74e3-4f6e-9dea-4cf52a8606be
X-WR-CALNAME:[ICQ] Yanlin Chen (CWI\, U. of Amsterdam) A quantum speed-up f
 or approximating the top eigenvectors of a matrix
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
TZUNTIL:20251026T010000Z
BEGIN:STANDARD
TZNAME:CET
DTSTART:20231029T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RDATE:20241027T030000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:CEST
DTSTART:20240331T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20250330T020000
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:056b2f6b-74e3-4f6e-9dea-4cf52a8606be
DTSTAMP:20260510T232448Z
CLASS:PUBLIC
DESCRIPTION:\n \n \n \n \n \n \nFinding a good approximation of the top eig
 envector of a given d × d matrix A is a basic and important computational 
 problem\, with many applications. We give two different quantum algorithms
  that\, given query access to the entries of A and assuming a constant eig
 envalue gap\, output a classical description of a good approximation of th
 e top eigenvector: one algorithm with time complexity d^{1.5+o(1)} and one
  with time complexity \tilde{O}(d^{1.75}) that has a slightly better depen
 dence on the precision of the approximation. Both provide a polynomial spe
 ed-up over the best-possible classical algorithm\, which needs Ω(d^2) quer
 ies to entries of A (and hence Ω(d^2) time). We extend this to a quantum a
 lgorithm that outputs a classical description of the subspace spanned by t
 he top-q eigenvectors in time qd^{1.5+o(1)}. We also prove a nearly-optima
 l lower bound of \tilde{Ω}(d^{1.5}) on the quantum query complexity of app
 roximating the top eigenvector. Our quantum algorithms run a version of th
 e classical power method that is robust to certain benign kinds of errors\
 , where we implement each matrix-vector multiplication with small and well
 -behaved error on a quantum computer\, in different ways for the two algor
 ithms.  \n  \nOur first algorithm used block-encoding techniques to comput
 e the matrix-vector product as a quantum state\, from which we obtain a cl
 assical description by a new time-efficient unbiased pure-state tomography
  algorithm that has essentially optimal sample complexity O(d log(d)/ε^2) 
 and that comes with improved statistical properties compared to earlier pu
 re-state tomography algorithms. Our second algorithm estimated the matrix-
 vector product one entry at a time\, using a new “Gaussian phase estimatio
 n” procedure. We also develop a time-efficient process- tomography algorit
 hm for reflections around bounded-rank subspaces\, providing the basis for
  our top-eigensubspace estimation application. \n  \nThis is the joint wor
 k with Ronald de Wolf and András Gilyén. \n        \n\n\n\nhttps://combalg
 o.labri.fr/pmwiki.php/Groupe/Info-Quantique
DTSTART;TZID=Europe/Paris:20240402T150000
DTEND;TZID=Europe/Paris:20240402T160000
LOCATION:Room 178
SEQUENCE:0
SUMMARY:[ICQ] Yanlin Chen (CWI\, U. of Amsterdam) A quantum speed-up for ap
 proximating the top eigenvectors of a matrix
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR
