Relative approximate counting query complexity

If $t=N$, [F7] gives phase $1\mathrm{/}2$; at the first rough scale $L=2$, [F9] and [F8] give label $y=1\mathrm{\ne }0$, so the loop stops at $L=2$. For $0<t<N$, ${\sin }^2\theta =t\mathrm{/}N$, and [F2] gives $P_0(L)\le 1\mathrm{/}(L^2{\sin }^2\theta )=N\mathrm{/}(t{L}^2)$. Once $L\ge 18\pi \sqrt{N\mathrm{/}t}$, this is at most $1\mathrm{/}(324{\pi }^2)<1\mathrm{/}4$.

Suppose $0<t<N$ and put $X=18\pi \sqrt{N\mathrm{/}t}$. Choose a natural $q>X$ by [F6]. Induction using the natural-power recursion gives $2^q\ge q+1$, so a dyadic scale exceeds $X$; scanning the rough scales in order reaches a first $L_{\ast }\ge X$. Its preceding scale is smaller than $X$, hence $L_{\ast }<2X=36\pi \sqrt{N\mathrm{/}t}$. By [F5], a rough Count at scale $L$ costs $L-1\le L$ controlled-$Q$ calls. The rough query costs below $L_{\ast }$ sum to less than $2L_{\ast }$. If the loop reaches $L_{\ast }$, each later zero outcome has conditional probability at most $1\mathrm{/}4$ by step 1.1; reaching the $j$th later scale costs at most $2^j{L}_{\ast }$ and has probability at most $4^{-j}$. Hence the expected tail is bounded by $L_{\ast }{\sum }_{j\ge 0}(1\mathrm{/}2{)}^j=2L_{\ast }$. If the cutoff occurs before $L_{\ast }$, it only removes terms from these upper bounds. Thus the expected rough cost is $O(\sqrt{N\mathrm{/}t})$. If $L$ is the actual stopping scale, its final rough Count costs $L-1\ge L\mathrm{/}2$ calls since $L\ge 2$, so $\mathbb{E}L$ is at most twice the expected rough query cost and is also $O(\sqrt{N\mathrm{/}t})$.

The final dyadic $M$ is less than twice its threshold, so $M=O(L\mathrm{/}ϵ)$. By [F5], the final Count uses $M-1$ calls; for $0<t<N$, the bound on $\mathbb{E}L$ in step 2.1 therefore gives $O({ϵ}^{-1}\sqrt{N\mathrm{/}t})$ expected final controlled-$Q$ calls, while the rough term is absorbed because $ϵ\le 1$. If $t=N$, step 1.1 gives $L=2$, so the rough cost is one call and the final size is $M=O(1\mathrm{/}ϵ)$, matching $O({ϵ}^{-1}\sqrt{N\mathrm{/}t})$. If $t=0$, the cutoff scale lies in $[2\sqrt{N},4\sqrt{N})$, the geometric rough-call sum is $O(\sqrt{N})$, and the final schedule uses $M=O(\sqrt{N}\mathrm{/}ϵ)$ calls by [F5]. Thus the stated zero-case cost retains the $ϵ$ factor.

Each repeated controlled-$Q$ call contains exactly one controlled $S_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}$ factor by [F3]; [F4] keeps that query count separate from controlled $A\mathrm{/}{A}^{\ast }$ and other gates. Thus the stated membership-reflection and resource counts follow.