Exact query count for the finite-grid iterative estimator

Suppose first that $0<a<1$, so the normalized vectors $B,G$ are defined. Inductively applying the rotation matrix from [F21] to $\cos \theta B+\sin \theta G$ gives $Q^{m_k}\psi =\cos ((2m_k+1)\theta )B+\sin ((2m_k+1)\theta )G$. Its good projection therefore has squared norm ${\sin }^2((2m_k+1)\theta )$, so the listed good/bad measurement has the Bernoulli likelihood factors displayed in the definition.

If $a=0$, then ${\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}\psi =0$ and $\theta =0$. The endpoint clause of [F21]’s supplier gives $Q\psi =\psi$, hence $Q^{m_k}\psi =\psi$ for every $m_k\ge 0$, including $m_0=0$. The good/bad probabilities are therefore $0$ and $1$, equal to ${\sin }^2((2m_k+1)0)$ and ${\cos }^2((2m_k+1)0)$. Almost surely every $h_k=0$; any record with a good outcome has probability zero under this endpoint model. The displayed Bernoulli factors give exactly these probabilities: a positive good exponent gives a zero factor, while the prescribed zero-exponent convention makes $0^0=1$ when no good outcome occurs. No normalized good vector or conditional state on a zero-probability outcome is used.

Set $s=2J$ and ${\zeta }_s=e^{2\pi i\mathrm{/}s}$. For each $k,j$, use the residues $r_{kj},r_{kj}^{\mathrm{\prime }}$ in the algorithm's polynomial factors and put $\alpha =(2m_k+1){\theta }_j$. By [F26], ${\zeta }_s^{r_{kj}}=e^{2i\alpha }$ and ${\zeta }_s^{r_{kj}^{\mathrm{\prime }}}=e^{-2i\alpha }$; [F27]–[F28] give their sum as $2\cos (2\alpha )$. Therefore [F29] gives $U_{kj}({\zeta }_s)={\sin }^2\alpha$ and $V_{kj}({\zeta }_s)={\cos }^2\alpha$. It follows that $P_j({\zeta }_s)=L_j$ for each $j$. The comparison procedure [F23] decides every pair exactly, including equality; the nonempty finite set $\{0,\dots ,J\}$ therefore has a maximizing label, and the least-label tie rule determines a unique output, including when all $L_j=0$ (then the chosen label is $j=0$). Its output polynomial $E_{\widehat{j}}({\zeta }_s)$ is exactly ${\sin }^2{\theta }_{\widehat{j}}$ by the same identity.

A shot in stage $k$ uses one initial $A$ and then $m_k$ iterates. Each iterate contributes one more $A$, one $A^{\ast }$, one zero-input reflection, and one good reflection by [F2]. Therefore the per-stage counts are respectively $S(m_k+1)$, $S{m}_k$, $S{m}_k$, and $S{m}_k$.

If $a=1$, orthogonality gives $\mathrm{\parallel }(I-{\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}})\psi {\mathrm{\parallel }}^2=1-a=0$, so ${\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}\psi =\psi$ and $\theta =\pi \mathrm{/}2$. The other endpoint clause of [F21]’s supplier gives $Q\psi =-\psi$, hence $Q^{m_k}\psi =(-1{)}^{m_k}\psi$ for every $m_k\ge 0$, including $m_0=0$. Its good/bad probabilities are $1$ and $0$, agreeing with ${\sin }^2((2m_k+1)\pi \mathrm{/}2)=1$ and ${\cos }^2((2m_k+1)\pi \mathrm{/}2)=0$. Almost surely every $h_k=S$; a record containing a bad outcome has probability zero under this model. The bad factor is zero exactly when its exponent is positive, and the same $0^0=1$ convention applies when no bad outcome occurs. No normalized bad vector or conditional state on a zero-probability outcome is used. Together with step 1.1, these cases establish the claimed Bernoulli likelihood factors on the whole task domain.

Summing over $k=0,\dots ,K$ gives the first four formulas. Since $m_0=0$ and $m_k=2^{k-1}$ for $k\ge 1$, $2m_k+1=2^k+1$ for $k\ge 1$, yielding the stated total. The geometric sum is $O(2^K)$, so the total is $O(S{2}^K)$.

Every stage has finitely many shots and iterates because $K,S$ are finite. Fresh state preparations and measurements are part of the instructions, so no controlled $Q$ or QFT call is used. The likelihood selection is finite by step 1.3, but this argument establishes neither a sample-size error bound nor an $ϵ,\delta$ guarantee.

The call totals established in step 1.4 and step 2.2 only tally explicitly invoked queries. By [F1], the analyzed procedure is a finite-grid likelihood schedule with no finite-sample success guarantee; [F3] counts its declared query actions but supplies no probability or approximation-error bound. Thus this resource count establishes no success theorem.