Nonasymptotic bounds for quantum purity amplification

In quantum purity amplification, one is given n copies of a noisy quantum state ρin mathbb{C}^{d times d} and asked to prepare k copies of its principal eigenstate |v_drangle. Several prior works have derived information-theoretically optimal algorithms for this problem, but the bounds they prove are only shown in the asymptotic regime as the number of samples n tends to infinity. In this paper, we establish the following nonasymptotic guarantee: if ρ's eigenvalues are sorted p₁ leq cdots leq p_d and p_d-1 < p_d, then \begin{equation*} n = O\Bigk + frac{k}δ cdot frac{1-p_d}{(p_d-p_d-1^2}\Big) \end{equation*} copies suffice to output a state with fidelity at least 1-δ with |v_d^{otimes k}rangle. Our bound holds for arbitrary spectra, and is independent of the dimension d. In the case of depolarizing noise, our finite-sample guarantee matches the optimal asymptotic scaling. Our proof is based on the combinatorics of random Young diagrams.