Sandwich test for Quantum Phase Estimation

Quantum Phase Estimation (QPE) has potential for a scientific revolution through numerous practical applications like finding better medicines, batteries, materials, catalysts etc. Many QPE algorithms use the Hadamard test to estimate $\langle ψ|U^{k}|ψ\rangle$ for a large integer $k$ for an efficiently preparable initial state $|ψ\rangle$ and an efficiently implementable unitary operator $U$. The Hadamard test is hard to implement because it requires controlled applications of $U^{k}$. Recently, a Sequential Hadamard test (SHT) was proposed (arXiv:2506.18765) which requires controlled application of $U$ only but its total run time $T_{\rm tot}$ scales as $\mathcal{O}(k^{3}/ε^{2}r_{\rm min}^{2})$ where $r_{\rm min}$ is the minimum value of $|\langle ψ|U^{k'}|ψ\rangle|$ among all integers $k' \leq k$. Typically $r_{\rm min}$ is exponentially low and SHT becomes too slow. We present a new algorithm, the SANDWICH test to address this bottleneck. Our algorithm uses efficient preparation of the initial state $|ψ\rangle$ to efficiently implement the SPROTIS operator $R_ψ^ϕ$ where SPROTIS stands for the Selective Phase Rotation of the Initial State. It sandwiches the SPROTIS operator between $U^{a}$ and $U^{b}$ for integers $\{a,b\} \leq k$ to estimate $\langle ψ|U^{k}|ψ\rangle$. The total run time $T_{\rm tot}$ is $\mathcal{O}(k^{2}\ln k/ ε^{2} s_{\rm min}^{6})$. Here $s_{\rm min}$ is the minimum value of $|\langle ψ|U^{\hat{k}}|ψ\rangle$ among all integers $\hat{k}$ which are values of the nodes of a random binary sum tree whose root node value is $k$ and leaf nodes' values are $1$ or $0$. It can be reasonably expected that $s_{\rm min} \not\ll 1$ in typical cases because there is wide freedom in choosing the random binary sum tree.