Doctoral Thesis Oral Defense - Costin Bădescu

— 3:30pm

Location:
In Person - Newell-Simon 4305

Speaker:
COSTIN BĂDESCU , Ph.D. Candidate
Computer Science Department
Carnegie Mellon University
https://www.costinbadescu.com/

Improved bounds for state certification, separability testing, and shadow tomography

We present improved sample complexity bounds for three fundamental quantum information tasks: state certification, separability testing, and shadow tomography. Given measurement access to n identical copies of an unknown quantum state 𝜌, we consider:

i. State Certification: The task of verifying 𝜌 is equal to a reference state sigma or at least ε-far in trace distance.  We present a testing algorithm for state certification that uses O(d/ ε2) copies of 𝜌.

ii. Separability Testing: For a bipartite state 𝜌 on a d2-dimensional system, we prove a lower bound of  𝛺(d2/ε2) copies are necessary to distinguish separability from being ε-far in trace distance from the set of all separable states.

iii. Shadow Tomography: The problem of estimating the expectation values tr(𝜌Ai) for m observables Ai,...,Am  to +/-ε accuracy. We present an algorithm that accomplishes this with O(log2(m) log(d)/ε4) copies, which simultaneously achieves the best known dependence on each parameter m, d, and ε.

Thesis Committee
Ryan O'Donnell (Chair)
Aayush Jain
David Woodruff
John Wright (University of California, Berkeley) 

For More Information:
matthewstewart@cmu.edu

Add event to Google
Add event to iCal