SCS Student Seminar / Computer Science Speaking Skills Talk

Friday, March 25, 2016 -
12:00pm to 1:00pm


Traffic 21 Classroom 6501 Gates & Hillman Centers


JOHN WRIGHT, Ph.D. Student

Event Website:

For More Information, Contact:

In quantum computing, one is often faced with the problem of producing the description of a quantum system in an unknown state.  Common examples include learning the outcome of a quantum experiment or verifying that a quantum device outputs the promised state.  This problem, known as quantum state tomography, is frequently encountered in real-world quantum applications, and a wide variety of algorithms have been proposed to solve it.  In this talk, we give the first algorithm for quantum state tomography which is provably optimal.  Surprisingly, the analysis of our algorithm reduces to solving various combinatorial problems involving longest increasing subsequences of random words, an we give several new results in this area. No prior knowledge of quantum computing is assumed.  This is joint work with Ryan O'Donnell. Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.


Speaking Skills