Weakly Measured Loops for Quantum Amplitude Amplification: Oracle Savings and Adaptive Search with Unknown Target Probability

Abstract

We present a family of quantum amplitude amplification algorithms that interleave ordinary Grover rotations with tunable weak measurements in loops. A successful measurement yields the target state and stops the algorithm, while after a failure, the loop resumes from the post-measurement state without restarting. We express the leading costs in expected Grover iterations as $p\to 0$. For a known target probability $p$, an exact weak measurement-conditioned loop for states near the angle $\pi /4$ uses $(\pi /8+1/4+o(1))/\sqrt{p}$ iterations, improving on the standard Grover constant $\pi /4$ and on optimised restart Grover, and matching the corresponding infimum in our continuous-angle analysis. When only a lower bound $0<p_0\le p<1/2$ is available, a discrete Lyapunov equation gives the exact expected oracle cost for every fixed measurement strength and a closed-form optimal strength. Using the strength selected from $p_0$, the expected number of Grover iterations is at most $\frac{1}{2\sqrt{2}}(\frac{1}{\sqrt{p}}+\frac{1}{\sqrt{p_0}})$, where the expected cost decreases as the actual $p$ increases, and gives the leading constant $1/\sqrt{2}$ at the promise boundary $p=p_0$. For completely unknown $p$, we identify measurement strength $\kappa (t)=\Theta (1/t)$ as the critical scale within the regular schedules considered here and analyse ${\kappa }_b(t)=\min \{1/2,b/t\}$. For each fixed $b>2$, we rigorously derive a closed-form Gamma-function expression $C(b)$ giving $(C(b)/2+o(1))/\sqrt{p}$ expected iterations. Numerical minimisation of this explicit expression gives $b\approx 5.2$ and $C(b)/2\approx 1.01$. The results show that weak measurements preserve the $\Theta (1/\sqrt{p})$ search scale while adding an explicit fixed-point control mechanism and provable oracle savings.

41 pages, 3 figures