Nengkun Yu

We prove that to learn an $N$-qubit state with $\varepsilon$ error in trace distance, $\Tilde{\Theta}(\frac{10^N}{\eps^2})$ copies are necessary and sufficient using Pauli measurements, where $\Tilde{\Theta}$ hides a $\sqrt{N}$ factor. The lower bound holds under adaptivity. Thus, we nearly settle the worst-case copy complexity of Pauli tomography, which has been a long-standing problem. Our main technical contribution is a novel lower bound framework for adaptive single-copy state tomography with measurement constraints. Our method allows measurement-dependent hard instances for tighter lower bounds, and characterizes the hardness of learning using the \emph{measurement information channel}. The power of our framework extends beyond Pauli measurements: We prove that Pauli measurements are near-optimal among single-qubit measurements, and further prove tight lower bounds for adaptive $k$-outcome measurements.

The quantum marginal problem asks whether a set of given density matrices are consistent, i.e., whether they can be the reduced density matrices of a global quantum state. Not many non-trivial analytic necessary (or sufficient) conditions are known for the problem in general. We propose a method to detect consistency of overlapping quantum marginals by considering the separability of some derived states. Our method works well for the $k$-symmetric extension problem in general, and for the general overlapping marginal problems in some cases. Our work is, in some sense, the converse to the well-known $k$-symmetric extension criterion for separability.