arXiv:2609.39621
Weakly Measured Loops for Quantum Amplitude Amplification: Oracle Savings and Adaptive Search with Unknown Target Probability
Wang Fang, Chris Heunen
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 $π/4$ uses $(π/8+1/4+o(1))/\sqrt{p}$ iterations, improving on the standard Grover constant $π/4$ and on optimised restart Grover, and matching the corresponding infimum in our continuous-angle analysis. When only a lower bound $0 < p_0 \leq 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 $κ(t)=Θ(1/t)$ as the critical scale within the regular schedules considered here and analyse $κ_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 $Θ(1/\sqrt{p})$ search scale while adding an explicit fixed-point control mechanism and provable oracle savings.
AI Summary
The paper studies amplitude amplification with intermediate weak measurements: can measurement backaction prevent Grover over-rotation while reducing expected cost? Each loop weakly measures the target flag, halts on success, and otherwise applies an ordinary Grover iteration without restarting. Costs count state-preparation queries, with $N_{\mathcal A/\mathcal A^\dagger}=2N_G+1$; weak measurements of the flag are not charged as oracle queries. For known target probability $p\to0$, a schedule first rotates near $\pi/4$, then chooses a measurement strength whose failure branch is restored to the checkpoint by one Grover iteration. Its expected iteration count is $(\pi/8+1/4+o(1))/\sqrt p$, about 18% below standard Grover and below optimized restart Grover. This constant matches the infimum within the analyzed continuous one-checkpoint family. With only $0<p_0\le p<1/2$ known, solving a discrete Lyapunov equation gives the exact fixed-strength cost and its optimizer. Choosing strength from $p_0$ yields expected query cost $1/\sqrt{2p_0}+\sqrt{p_0}/(\sqrt2p)$, decreasing with actual $p$. For completely unknown $p$, the schedule $\kappa_b(t)=\min\{1/2,b/t\}$, $b>2$, has expected iteration count $(C(b)/2+o(1))/\sqrt p$. A singular-ODE limit, uniform convergence and tail estimates, followed by Fourier analysis, give an explicit Gamma-function formula for $C(b)$; numerical minimization gives $b\approx5.2$ and $C(b)/2\approx1.01$. Weak-measurement search already achieves quadratic scaling; the focus here is explicit constants. The savings concern repeat-until-success expectations, not deterministic query budgets. The $1/t$ critical-scale claim is restricted to specified asymptotic schedule classes, and global optimality among adaptive schedules is not established.
The authors used ChatGPT Pro (GPT-5.5/5.4) and OpenAI Codex to assist with language editing, exploratory coding, preliminary literature searches, and brainstorming of analytical approaches.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 41 pages, 3 figures