Inverse-free quantum state estimation with Heisenberg scaling

Abstract

In this paper, we present an inverse-free pure quantum state estimation protocol that achieves Heisenberg scaling. Specifically, let $\mathcal{H}\cong {\mathbb{C}}^d$ be a $d$-dimensional Hilbert space with an orthonormal basis $\{|1⟩,\dots ,|d⟩\}$ and $U$ be an unknown unitary on $\mathcal{H}$. Our protocol estimates $U|d⟩$ to within trace distance error $\epsilon$ using $O(\min \{d^{3/2}/\epsilon ,d/{\epsilon }^2\})$ forward queries to $U$. This complements the previous result $O(d\log (d)/\epsilon )$ by van Apeldoorn, Cornelissen, Gilyén, and Nannicini (SODA 2023), which requires both forward and inverse queries. Moreover, our result implies a query upper bound $O(\min \{d^{3/2}/\epsilon ,1/{\epsilon }^2\})$ for inverse-free amplitude estimation, improving the previous best upper bound $O(\min \{d^2/\epsilon ,1/{\epsilon }^2\})$ based on optimal unitary estimation by Haah, Kothari, O'Donnell, and Tang (FOCS 2023), and disproving a conjecture posed in Tang and Wright (2025).

17 pages