skip to main content

IQI Weekly Seminar

Tuesday, January 29, 2019
3:00pm to 4:00pm
Add to Cal
Annenberg 107
How to learn a quantum state
John Wright, MIT,

Abstract: In the problem of quantum state learning, one is given a small number of "samples" of a quantum state, and the goal is to output a good estimate of the quantum state. This is a problem which is not only of theoretical interest, but is also commonly used in current-day implementation and verification of quantum technologies.  In this talk, I will describe the first optimal quantum algorithm for this problem.  In addition, I will describe optimal algorithms for the related problems of testing and learning specific properties of quantum states.  These results make use of a new connection between quantum state learning and longest increasing subsequences of random words, a famous topic in combinatorics dating back to a 1935 paper of ErdÅ‘s and Szekeres.  Motivated by this connection, I will show new and optimal bounds on the length of the longest increasing subsequence of a random word.

This is based on joint works with Costin Badescu and Ryan O'Donnell.














For more information, please contact Bonnie Leung by phone at 626.395.4964 or by email at [email protected].