Date：2025/5/16 15:40-17:00
Location: R103, CSIE
Speakers: Dr. Yanlin Chen (陳彥霖)
Host: 李彥寰教授
Abstract:
Finding a good approximation of the top eigenvector 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 Hermitian matrix A and assuming a constant eigenvalue gap, output a classical description of a good approximation of the top eigenvector: one algorithm with time complexity \tilde{O}(d^{1.75}) and one with time complexity d^{1.5+o(1)} (the first algorithm has a slightly better dependence on the ℓ_2-error of the approximating vector than the second, and uses different techniques of independent interest). Both of our quantum algorithms provide a polynomial speed-up over the best-possible classical algorithm, which needs Ω(d^2) queries to entries of A, and hence Ω(d^2) time. We extend this to a quantum algorithm that outputs a classical description of the subspace spanned by the top-q eigenvectors in time qd^{1.5+o(1)}. We also prove a nearly-optimal lower bound of \tilde{\Omega}(d^{1.5}) on the quantum query complexity of approximating the top eigenvector.
Our quantum algorithms run a version of the 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 algorithms. Our first algorithm estimates the matrix-vector product one entry at a time, using a new "Gaussian phase estimation" procedure. Our second algorithm uses block-encoding techniques to compute the matrix-vector product as a quantum state, from which we obtain a classical description by a new time-efficient unbiased pure-state tomography procedure.
Our quantum algorithms run a version of the 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 algorithms. Our first algorithm estimates the matrix-vector product one entry at a time, using a new "Gaussian phase estimation" procedure. Our second algorithm uses block-encoding techniques to compute the matrix-vector product as a quantum state, from which we obtain a classical description by a new time-efficient unbiased pure-state tomography procedure.
Biography:
Dr. Yanlin Chen (陳彥霖) is a Postdoctoral Researcher at the Centrum Wiskunde & Informatica (CWI) in the Netherlands and will soon join the University of Maryland (UMD) as a Postdoctoral Researcher. He received his Ph.D. in theoretical computer science from the University of Amsterdam, where he was advised by Prof. Ronald de Wolf in the Algorithms and Complexity group at CWI.
His research lies at the intersection of theoretical computer science and quantum computation. His work focuses on quantum algorithms for optimization problems, particularly for convex and non-convex optimization, high-dimensional geometry, and lattice problems. He is interested in both designing more efficient quantum algorithms and understanding their fundamental limitations.
His research lies at the intersection of theoretical computer science and quantum computation. His work focuses on quantum algorithms for optimization problems, particularly for convex and non-convex optimization, high-dimensional geometry, and lattice problems. He is interested in both designing more efficient quantum algorithms and understanding their fundamental limitations.