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 σ or at least ε-far in trace distance. We present a testing algorithm for state certification that uses O(d/ε²) copies of ρ.
ii. Separability testing: For a bipartite state ρ on a d ²-dimensional system, we prove a lower bound of Ω(d²/ε²) 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(ρA_i) for m observables A₁, . . . , A_m to ±ε accuracy. We present an algorithm that accomplishes this with O(log²(m) log(d)/ε⁴) copies, which simultaneously achieves the best known dependence on each parameter m, d, and ε.

93 pages

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

Jignesh Patel, Interim Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Creative Commons: CC-BY-NC (Attribution-Non-Commercial)

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu