Abstract
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 ψ|U^k|ψ for a large integer k for an efficiently preparable initial state |ψ 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_ tot scales as O(k³/ε²r_ min²) where r_ min is the minimum value of | ψ|U^k'|ψ| among all integers k' ≤ k. Typically r_ 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 |ψ 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} ≤ k to estimate ψ|U^k|ψ. The total run time T_ tot is O(k²ln k/ ε² s_ min⁶). Here s_ min is the minimum value of | ψ|U^k|ψ among all integers 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_ min ≪ 1 in typical cases because there is wide freedom in choosing the random binary sum tree.