John
Wright,
Postdoctoral
fellow
Center
for
Theoretical
Physics,
MIT
In the area of quantum state learning, one is given a small number of "samples" of a quantum state, and the goal is use them to determine a feature of the state. Examples include learning the entire state ("quantum state tomography"), determining whether it equals a target state ("quantum state certification"), or estimating its von Neumann entropy. These are problems which are not only of theoretical interest, but are also commonly used in current-day implementation and verification of quantum technologies.
In this talk, I will describe my work giving efficient algorithms for a variety of these problems, including the first optimal algorithms for tomography and state certification. My 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.
Bio: John Wright got his B.Sc. from the University of Texas at Austin and his Ph.D. from Carnegie Mellon University, where he was advised by Ryan O'Donnell. He is now a physics postdoc at the Massachusetts Institute of Technology.