log in  |  register  |  feedback?  |  help  |  web accessibility
How to learn a quantum state
John Wright - MIT
Wednesday, March 13, 2019, 11:00 am-12:15 pm Calendar
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)

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.

I will also discuss some recent work in quantum complexity theory.

This talk is organized by Andrea F. Svejda