2025/07/31 by Avatar Tulsi, Tulsi, Avatar
Computer Science · Physics and Astronomy · #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #Quantum, superfluid, helium dynamics
paper · pdf · doi:10.48550/arxiv.2507.23716
openalex publication_date 2025/07/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ⟨ ψ|Uk|ψ⟩ 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 Uk. 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 O(k3/ε2r\rm min2) where r\rm min is the minimum value of |⟨ ψ|Uk'|ψ⟩| among all integers k' ≤ 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 |ψ⟩ 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 Ua and Ub for integers \a,b\ ≤ k to estimate ⟨ ψ|Uk|ψ⟩. The total run time T\rm tot is O(k2ln k/ ε2 s\rm min6). Here s\rm 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\rm min \not≪ 1 in typical cases because there is wide freedom in choosing the random binary sum tree.