How to learn a quantum state

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"), 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 Erdos 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.

Biography: 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.


Share this event:

facebook linked in twitter email

Media Contact: Sean Hallgren



The School of Electrical Engineering and Computer Science was created in the spring of 2015 to allow greater access to courses offered by both departments for undergraduate and graduate students in exciting collaborative research in fields.

We offer B.S. degrees in electrical engineering, computer science, computer engineering and data science and graduate degrees (master's degrees and Ph.D.'s) in electrical engineering and computer science and engineering. EECS focuses on the convergence of technologies and disciplines to meet today’s industrial demands.

School of Electrical Engineering and Computer Science

The Pennsylvania State University

207 Electrical Engineering West

University Park, PA 16802


Department of Computer Science and Engineering


Department of Electrical Engineering