Abstract
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"), and estimating its von Neumann entropy. These are foundational problems in information theory which date back to the prehistory of quantum computing. However, in recent years they have also gained practical application due to advances in experimental quantum computing, and it is now common to see quantum devices verified using state tomography and entanglement in many-body systems demonstrated via entropy estimation.


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. I have also given the best known algorithm for entropy estimation. These rely on a new, unifying framework connecting the topic of quantum state learning to the seemingly unrelated topic of longest increasing subsequences of random words from combinatorics. Motivated by questions in quantum state learning, I have proven many new results about longest increasing subsequences, and I will discuss some of these in the talk.

Bio
John Wright received a B.Sc. from the University of Texas at Austin in 2010 and a Ph.D. from the CMU Computer Science Department in 2016. His Ph.D. advisor was Ryan O'Donnell. He is currently a postdoc at the MIT Center for Theoretical Physics in Eddie Farhi, Aram Harrow, and Peter Shor's group. His research areas include quantum information theory and quantum complexity theory.