Sample-optimal tomography of quantum states

Abstract

It is a fundamental problem to decide how many copies of an unknown mixed quantum state are necessary and sufficient to determine the state. Previously, it was known only that estimating states to error ε in trace distance required O(dr <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> /ε <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ) copies for a d-dimensional density matrix of rank r. Here, we give a theoretical measurement scheme (POVM) that requires O(dr/δ)ln (d/δ) copies to estimate ρ to error δ in infidelity, and a matching lower bound up to logarithmic factors. This implies O((dr/ε <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> )ln (d/ε)) copies suffice to achieve error ε in trace distance. We also prove that for independent (product) measurements, Ω(dr <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> /δ <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> )/ ln(1/δ) copies are necessary in order to achieve error δ in infidelity. For fixed d, our measurement can be implemented on a quantum computer in time polynomial in n.