Tight Success Probabilities for Quantum Period Finding and Phase Estimation

Period finding and phase estimation are fundamental in quantum computing. Prior work has established lower bounds on their success probabilities. Such quantum algorithms measure a state $|\hat\ell\rangle$ in an $n$-qubit computational basis, $\hat\ell \in [0, 2^n - 1]$, and then post-process this measurement to produce the final output, in the case of period finding, a divisor of the period $r$. We consider a general post-processing algorithm which succeeds whenever the measured $\hat\ell$ is within some tolerance $M$ of a positive integer multiple of $2^n / r$. We give new (tight) lower and upper bounds on the success probability that converge to 1. The parameter $n$ captures the complexity of the quantum circuit. The parameter $M$ can be tuned by varying the post-processing algorithm (e.g., additional brute-force search, lattice methods). Our tight analysis allows for the careful exploitation of the tradeoffs between the complexity of the quantum circuit and the effort spent in classical processing when optimizing the probability of success. We note that the most recent prior work in most recent work does not give tight bounds for general $M$.