Tight Bounds for Quantum Phase Estimation and Related Problems

Mande, NS ORCID: 0000-0002-9520-7340 and de Wolf, R (2026) Tight Bounds for Quantum Phase Estimation and Related Problems Quantum, 10. 2140-. ISSN 2521-327X, 2521-327X

PDF q-2026-06-15-2140.pdf - Open Access published version Download (723kB) | Preview

Abstract

Phase estimation, due to Kitaev [arXiv’95], is one of the most fundamental subroutines in quantum computing, used in Shor’s factoring algorithm, optimization algorithms, quantum chemistry algorithms, and many others. In the basic scenario, one is given black-box access to a unitary U, and an eigenstate |ψ⟩ of U with unknown eigenvalue e^iθ, and the task is to estimate the eigenphase θ within ±δ, with high probability. The repeated application of U and U−1 is typically the most expensive part of phase estimation algorithms, so for us the cost of an algorithm will be that number of applications. Motivated by the “guided local Hamiltonian problem” from quantum chemistry, we tightly characterize the cost of several variants of phase estimation where we are no longer given an arbitrary eigenstate, but are required to estimate the maximum eigenphase of U, aided by advice in the form of copies of a state (or a unitary preparing that state) that is promised to have at least a certain overlap γ with the top eigenspace. We give algorithms and matching lower bounds (up to logarithmic factors) for all ranges of parameters. We show a crossover point below which advice is not helpful: o(1/γ²) copies of the advice state (or o(1/γ) applications of an advice-preparing unitary) are not significantly better than having no advice at all. We also show that having much more advice (more than O(1/γ²) copies or more than O(1/γ) applications of the advice-preparing unitary) does not significantly reduce cost, and neither does knowledge of the eigenbasis of U. As an immediate consequence of a key technical component of our proof, we obtain a lower bound on the complexity of the Unitary recurrence time problem, matching an upper bound of She and Yuen [ITCS’23] and resolving one of their open questions. Lastly, we study how efficiently one can reduce the error probability in the basic phase-estimation scenario. We show that a phase-estimation algorithm with precision δ and error probability ε has cost Ω (formula presented), matching the obvious way to amplify the basic constant-error-probability phase estimation algorithm. This contrasts with some other scenarios in quantum computing (e.g., search) where error-probability reduction costs only a factor O( log(1/ε)). Our lower bound uses a variant of the polynomial method with trigonometric polynomials.

Item Type:	Article
Uncontrolled Keywords:	5108 Quantum Physics, 51 Physical Sciences
Divisions:	Faculty of Science & Engineering Faculty of Science & Engineering > School of Computer Science & Informatics Faculty of Science & Engineering > School of Computer Science & Informatics > Algorithms and Computing Systems
Depositing User:	Symplectic Admin
Date Deposited:	06 Jul 2026 16:16
Last Modified:	09 Jul 2026 10:15
DOI:	10.22331/q-2026-06-15-2140
Related Websites:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3199299
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.