Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

A Quantum Speed-Up for Approximating the Top Eigenvector of a Matrix via Improved Tomography

Simons Institute via YouTube

Overview

Explore a quantum algorithm that provides a polynomial speed-up for approximating the top eigenvector of a matrix in this 47-minute lecture by András Gilyén from the Alfréd Rényi Institute of Mathematics. Delve into the algorithm's ability to output a classical description of the top eigenvector with a time complexity of ~d^{1.5}, significantly faster than the best classical algorithm's Ω(d^2) time. Learn about the algorithm's extension to output the subspace spanned by the top-q eigenvectors and the nearly-optimal lower bound on quantum query complexity. Discover how this quantum approach implements a noisy variant of the classical power method, utilizing block-encoding techniques and a new time-efficient unbiased pure-state tomography algorithm. Examine the development of a time-efficient process-tomography algorithm for reflections around bounded-rank subspaces, which enhances pure-state tomography capabilities.

Syllabus

A Quantum Speed-Up for Approximating the Top Eigenvector of aMatrix via Improved Tomography

Taught by

Simons Institute

Reviews

Start your review of A Quantum Speed-Up for Approximating the Top Eigenvector of a Matrix via Improved Tomography

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.