Theory Lunch Seminar

Wednesday, October 25, 2017 - 12:00pm to 1:00pm


ASA Conference Room 6115 Gates Hillman Centers



Quantum State Certification

We consider the problem of quantum state certification, where one is given n​ copies of an unknown d​ -dimensional quantum mixed state ρ​ and one wants to test whether ρ​ is equal to some known mixed state σ​ or else is ε​-far from σ​. The goal is to use notably fewer copies than the Ω(d2)​ needed for full tomography on ρ​ (i.e., density estimation).

We give two robust state certification algorithms: one with respect to fidelity using n = O(d/ε)​ copies and one with respect to trace distance using n = O(d/ε2)​ copies. The latter algorithm also applies when σ​ is unknown as well. These copy complexities are optimal up to constant factors.

Joint work with Ryan O'Donnell and John Wright.


Event Website:

For More Information, Contact:


Seminar Series