Almost Tight Sample Complexity Analysis of Quantum Identity Testing by Pauli Measurements

This paper studies the quantum identity testing problem, a quantum analogue of distribution identity testing. The goal is to determine whether a quantum state is identical to another fixed quantum state, using as few state samples as possible. Rather than general entangled measurements, we consider the less powerful but experimentally friendly Pauli measurements. We follow the standard setting where Pauli measurements are regarded as two-outcome measurements, i.e., each η-qubit Pauli measurement has a one-bit outcome.We prove that for an η-qubit quantum system, the sample complexity of this problem is ?(poly(η) (Equation Presnted)if only Pauli measurements are allowed. In other words, we provide simple algorithms to determine whether two n-qubit quantum states, ρ and ρ, are identical or €-far in trace distance using Pauli measurements, using O(Equation Presnted)copies of ρ and ℙ. Interestingly, O(Equation Presnted) copies are not sufficient under this setting.