Computer Science Thesis Proposal

Wednesday, May 27, 2015 - 1:00pm


Traffic 21 Classroom 6501 Gates & Hillman Centers


JOHN WRIGHT, Ph.D. Student

For More Information, Contact:

Anyone interested in using a quantum computer to learn something about a real-world physical system is faced with a quantum version of the “big data” problem: as the number of subsystems grows, the dimension of the whole system grows exponentially. The result is that even small systems can be described by an enormous number of parameters, and algorithms running in small-exponent polynomial time can still be intractable from a practical perspective. This thesis proposal is focused on designing and analyzing efficient algorithms for natural learning problems dealing with quantum systems represented as mixed states. Given a mixed state rho, we consider the standard problems of (i) state tomography, (ii) spectrum estimation, (iii) truncated spectrum estimation, and (iv) property testing. For each of these problems, we propose new algorithms or analyze old algorithms, with the goal of improving the best-known asymptotic sample complexity. Our techniques are primarily representation theoretic, and in particular we focus mainly on algorithms derived from Schur-Weyl duality. Thesis Committee: Ryan O’Donnell (Chair) Anupam Gupta Venkatesan Guruswami Aram Harrow (MIT_ Copy of Proposal Summary


Thesis Proposal