Nearly Time-Optimal Pure State Tomography with Pauli Measurements

Abstract

We give an algorithm for pure state tomography with near-optimal copy and time complexity using only single-qubit measurements. Specifically, given $\tilde{O}(2^n/\epsilon )$ copies of an unknown $n$-qubit pure state $|\psi ⟩$, the algorithm performs only nonadaptive Pauli measurements, runs in time $\tilde{O}(2^n/\epsilon )$, and outputs $|\hat{\psi }⟩$ with fidelity at least $1-\epsilon$ with $|\psi ⟩$ with high probability. This is the first algorithm for pure state tomography that achieves near-optimal running time.

arXiv commentThis version contains a new result: our algorithm now has a near-optimal runtime