Friday, March 25, 2016 - 12:00pm to 1:00pm
Location:Traffic 21 Classroom 6501 Gates & Hillman Centers
Speaker:JOHN WRIGHT, Ph.D. Student http://www.cs.cmu.edu/~jswright
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.