AI summaryⓘ
The authors study how many copies of an unknown quantum state are needed to check how close it is to a known reference state, within a small error. They found that when the reference state has rank r, the number of samples required is roughly proportional to r squared divided by the square of the error margin, which improves on previous estimates. They also provide a lower limit on the number of samples needed, which is better than earlier results and has connections to quantum query complexity. Additionally, they explore a scenario where the unknown state has low rank but the reference state can be any state, showing a different sample complexity. Their results help improve methods for quantum state certification, especially when some tolerance for error is allowed.
Quantum state fidelitySample complexityQuantum tomographyRank of quantum statesAdditive errorQuantum state certificationQuery complexityLow-rank approximationQuantum information
Abstract
We consider the problem of estimating the fidelity of an unknown quantum state to a known reference state to within additive error $\varepsilon$. We show that the sample complexity is $O(r^2/\varepsilon^2)$ with optimal $\varepsilon$-dependence when the reference state is of rank $r$, improving the previous best $O(r^2\log^2(1/\varepsilon)/\varepsilon^4)$ due to Utsumi, Nakata, Wang, and Takagi (QIP 2026). We also provide a lower bound of $Ω(r/\varepsilon^2)$, improving the previous best $Ω(r/\varepsilon+1/\varepsilon^2)$, with implications to quantum query complexity. Moreover, we further consider the case where the unknown state is of rank at most $r$ while the reference state can be arbitrary, for which the sample complexity is shown to be $O(r^2/\varepsilon^4)$. As an application, we present an approach to tolerant quantum state certification, generalizing the exact certification studied in Bădescu, O'Donnell, and Wright (STOC 2019).