Amplitude Amplification

Let $H$ be a nonzero finite-dimensional complex inner-product space, let $\mathrm{\mid }0⟩\in H$ be a specified unit input vector, let $A:H\to H$ be a supplied measurement-free unitary, and let ${\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}$ be an orthogonal projection on $H$. The access contract supplies and charges calls to $A$, its inverse $A^{†}$, the good phase reflection $S_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}:=I_H-2{\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}},$ and the zero-input phase reflection $S_0:=I_H-2\mathrm{\mid }0⟩⟨0\mathrm{\mid }\mathrm{.}$ The signs are part of the contract: $S_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}$ is $-I$ on $\mathrm{ran}{\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}$ and $+I$ on its orthogonal complement. Reflection about the prepared state is the composite $A{S}_0{A}^{†}$, with its component calls charged unless a separate direct-reflection access is supplied.

Put $\mathrm{\mid }\psi ⟩=A\mathrm{\mid }0⟩$ and define the initial success weight $a:=\mathrm{\parallel }{\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}\mathrm{\mid }\psi ⟩{\mathrm{\parallel }}^2\in [0,1]\mathrm{.}$ When $a>0$, define $\mathrm{\mid }G⟩:={\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}\mathrm{\mid }\psi ⟩\mathrm{/}\sqrt{a}$. When $a<1$, define $\mathrm{\mid }B⟩:=(I_H-{\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}})\mathrm{\mid }\psi ⟩\mathrm{/}\sqrt{1-a}$. These vectors are normalized and lie respectively in the range and kernel of ${\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}$. If $a=0$ or $a=1$, the corresponding zero component is omitted and no vector is normalized from it. With this convention, $\mathrm{\mid }\psi ⟩=\sqrt{a}\mathrm{\mid }G⟩+\sqrt{1-a}\mathrm{\mid }B⟩$ means the sum of the nonzero component terms. Under the projective measurement $\{{\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}},I_H-{\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}\}$, the probability of the good outcome is $a$; the finite-dimensional rank-one density and projective-measurement outcome laws are A unit-vector outer product is a density operator and Projective measurement outcome weights are probabilities.

The output task may return the conditional quantum state after the good outcome; that state is defined only on a positive-probability branch and is supported in $\mathrm{ran}{\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}$ by Conditional state for a projective measurement. A classical output additionally requires ${\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}$ to be diagonal in a specified output basis and a costed coherent or ordinary verifier. An arbitrary projection does not supply a classical predicate.

The unitary must be supplied coherently. A measured randomized procedure is not an admissible $A$ unless a separate coherent embedding is supplied. Controlled access to $A$ is not assumed. A controlled verifier, if used, is a distinct charged access capability.

Let $A,{\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}},a,\mathrm{\mid }G⟩,\mathrm{\mid }B⟩$ be as in Prepared unitary and success subspace for amplitude amplification, with $0<a<1$, and let $\theta \in (0,\pi \mathrm{/}2)$ be the unique angle satisfying ${\sin }^2\theta =a$. For $Q:=-A{S}_0{A}^{†}{S}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}},$ the subspace $\mathrm{span}\{\mathrm{\mid }B⟩,\mathrm{\mid }G⟩\}$ is invariant. In the ordered orthonormal basis $(\mathrm{\mid }B⟩,\mathrm{\mid }G⟩)$, the restriction of $Q$ is $\left(\begin{array}{cc}\cos (2\theta )& -\sin (2\theta )\\ \sin (2\theta )& \cos (2\theta )\end{array}\right)\mathrm{.}$ For $a=0$ the prepared vector spans an invariant bad line and $Q\mathrm{\mid }\psi ⟩=\mathrm{\mid }\psi ⟩$; for $a=1$ it spans an invariant good line and $Q\mathrm{\mid }\psi ⟩=-\mathrm{\mid }\psi ⟩$.

Input a coherent sampler $A$, an orthogonal success projection ${\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}$, and a fixed integer $k\ge 0$, under the access contract of Prepared unitary and success subspace for amplitude amplification. Additionally supply the good/bad projective instrument $\{{\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}},I-{\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}\}$, charging each measurement and its implementation costs separately. Prepare $\mathrm{\mid }\psi ⟩=A\mathrm{\mid }0⟩$. In the displayed right-to-left operator convention, set $Q:=-A(I-2\mathrm{\mid }0⟩⟨0\mathrm{\mid })A^{†}(I-2{\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}})\mathrm{.}$ Apply $Q$ exactly $k$ times. Then apply the projective instrument $\{{\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}},I-{\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}\}$. On a positive-probability good outcome return its conditional quantum state; on the bad outcome return fail. The conditional state exists only on a positive-probability branch, as in Conditional state for a projective measurement.

For the classical-output specialization, additionally require ${\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}$ to be diagonal in the designated output basis and supply a costed verifier. Measure that basis only after the success-projector instrument has accepted; verify the resulting candidate and return it or fail. No arbitrary-projector-to-classical-predicate conversion is implicit.

This fixed-$k$ procedure makes no controlled-$A$ call. Any controlled or inverse access used by an enclosing procedure must be separately declared and charged. The scalar minus sign in $Q$ is retained exactly.

This is a sequential randomized procedure, not a bounded-$T$ circuit family. Fix $c=3\mathrm{/}2$. For rounds $\mathrm{\ell }=1,2,\dots$, compute the finite integer $M_{\mathrm{\ell }}=\lceil c^{\mathrm{\ell }}\rceil$ by exact rational arithmetic. In classical-output mode, require the diagonal-predicate specialization of Prepared unitary and success subspace for amplitude amplification and a costed verifier that accepts exactly the basis labels designated good by ${\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}$; measure the designated output basis only after the good/bad instrument and then run the verifier.

1. On a fresh register prepare $A\mathrm{\mid }0⟩$ and perform the declared good/bad projective instrument. On a bad outcome, continue to step 2. On a good outcome, return the conditional quantum state in quantum-output mode; in classical-output mode, measure the designated output basis, verify the candidate, and return it if accepted.

2. Prepare $A\mathrm{\mid }0⟩$ on a second fresh register. Draw $j$ uniformly from the finite set $\{1,\dots ,M_{\mathrm{\ell }}\}$, apply exactly $j$ standard $Q$-iterates, and perform the good/bad instrument. On a good outcome, return the conditional quantum state in quantum-output mode; in classical-output mode, measure the designated output basis, verify the candidate, and return it if accepted. If the outcome is bad or verification rejects, discard the registers and continue to round $\mathrm{\ell }+1$.

The random choice is fresh and independent in each round; the schedule depends only on $\mathrm{\ell }$, never on the unknown $a$. Every round is finite. When $a=0$, the loop runs forever and does not decide whether the good set is empty.

The expected query cost of this unbounded sequential procedure is interpreted using finite execution prefixes as in Expected query cost from finite execution prefixes. A zero-probability good branch is never normalized.

Input a prepared sampler $A$, a success projection ${\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}$, an integer $m\ge 0$, and phases $\varphi ,\phi \in [0,2\pi )$. In addition to $A,A^{†}$, the access contract must supply the exact phase operations $S_0(\varphi )=I+(e^{i\varphi }-1)\mathrm{\mid }0⟩⟨0\mathrm{\mid },S_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}(\phi )=I+(e^{i\phi }-1){\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}},$ and charge each call. Such access does not follow from a $\pi$-phase reflection alone. Prepare $A\mathrm{\mid }0⟩$, apply $Q(\varphi ,\phi ):=-A{S}_0(\varphi )A^{†}{S}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}(\phi )$ exactly $m$ times, and apply the declared good/bad projective instrument. Return the conditional quantum output on a positive-probability good branch or fail on the bad branch. A classical output additionally needs the diagonal-predicate and costed-verifier conditions in Prepared unitary and success subspace for amplitude amplification.

The outer minus sign is retained in the operator. An uncontrolled $m$-fold sequence differs from the sequence without that scalar only by the global factor $(-1{)}^m$. It cannot be dropped inside a controlled use: the controlled block treats the two control branches differently, as in A Controlled Global Phase Becomes a Relative Control Phase. Controlled access to any factor is separately supplied and charged.

Let $a\in [0,1]$ be the initial success weight and let $\theta \in [0,\pi \mathrm{/}2]$ be the unique angle satisfying ${\sin }^2\theta =a$. After exactly $k\ge 0$ standard amplitude-amplification iterates, the probability of the good outcome of $\{{\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}},I-{\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}\}$ is ${\sin }^2((2k+1)\theta )\mathrm{.}$ The endpoints $a=0$ and $a=1$ are included by direct evaluation, without normalizing a zero component.

Input a coherent sampler with an exactly represented known success weight $a\in [0,1]$. For the finite rational-input procedure, $a$ is given as a binary rational; exact algebraic inputs are also allowed when the supplied representation supports exact comparisons. If $a=0$, return fail without normalizing a good component. If $a=1$, prepare $A\mathrm{\mid }0⟩$, apply the declared good/bad projective instrument, and return its good conditional state (or, in the diagonal classical-output specialization, measure and verify the output).

For $0<a<1$, set $\theta :=\arcsin \sqrt{a}\in (0,\pi \mathrm{/}2)$, using the principal inverse-sine and nonnegative-square-root conventions of Principal inverse sine and inverse cosine and Square roots exist: a unique $\sqrt{a}\ge 0$ with $(\sqrt{a}{)}^2=a$; the positives are $\{x^2:x\mathrm{\ne }0\}$. Then $\theta$ is the unique angle with ${\sin }^2\theta =a$. Set $K:=\lceil 1\mathrm{/}\sqrt{a}\rceil$, equivalently the least positive integer $K$ with $K^{2}a\ge 1$. For each integer $k=0,\dots ,K$, compute $p_k={\sin }^2((2k+1)\theta )$ exactly by the rational recurrence $x_0=1,x_1=1-2a,x_{n+1}=2(1-2a)x_n-x_{n-1}(n\ge 1),p_k=(1-x_{2k+1})\mathrm{/}2.$ Indeed, writing $x_n=\cos (2n\theta )$, double-angle gives $x_0=1$, $x_1=\cos (2\theta )=1-2a$, and cosine addition gives the displayed recurrence. Also ${\sin }^2((2k+1)\theta )=(1-\cos ((4k+2)\theta ))\mathrm{/}2=(1-x_{2k+1})\mathrm{/}2$. Choose the least $k$ attaining the maximum of this finite list. Run the fixed-$k$ procedure Amplitude amplification with a fixed integer iteration count, verify when a classical candidate is requested, and return the good conditional output or fail. For rational $a$, every $x_n$ and $p_k$ is rational, so the comparisons are exact. No time bound for this classical preprocessing is claimed.

For a general real $a$, the same mathematical maximizer is defined, but a finite implementation requires an exact representation and a procedure that decides all finitely many comparisons, including ties. The item makes no computation claim for an arbitrary unrepresented real.

Input a prepared sampler $A$, its inverse $A^{†}$, an orthogonal good projection ${\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}$, and an exactly represented known $a\in [0,1]$ equal to the success weight. The model must supply the coherent flag unitary $C_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}={\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}\otimes X+(I-{\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}})\otimes I$ and its inverse, a clean flag qubit $F$, a clean temporary qubit $T$, external clean implementation workspace, and exact real arithmetic and controlled flag-rotation access, including inverse rotations. These are explicit capabilities; a bare phase reflection does not supply $C_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}$, and no finite-bit gate synthesis is asserted. The input data space is the possibly abstract space $H$ and specified vector $\mathrm{\mid }0⟩$ of Prepared unitary and success subspace for amplitude amplification; no full classical description or computational-basis test for that vector is inferred. No controlled access to $A$ is required.

If $a=0$, return fail without normalizing a good component. If $a=1$, prepare $A\mathrm{\mid }0⟩$ and apply $\{{\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}},I-{\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}\}$. Supply and charge that instrument directly, or construct it by applying $C_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}$ to data and a clean scratch bit, measuring only that bit, and applying $C_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}^{†}$; this costs two flag calls and one bit measurement and resets the scratch. Return the good conditional state; in the diagonal classical-output case, measure the designated output and verify it.

For $0<a<1$, set $\theta :=\arcsin \sqrt{a}\in (0,\pi \mathrm{/}2)$, using Principal inverse sine and inverse cosine and Square roots exist: a unique $\sqrt{a}\ge 0$ with $(\sqrt{a}{)}^2=a$; the positives are $\{x^2:x\mathrm{\ne }0\}$, and define $m=\lceil \frac{\pi }{4\theta }-\frac{1}{2}\rceil ,{\theta }^{\mathrm{\prime }}=\frac{\pi }{4m+2},r=\frac{{\sin }^2{\theta }^{\mathrm{\prime }}}{a}\mathrm{.}$ Since $m\ge \pi \mathrm{/}(4\theta )-1\mathrm{/}2$, we have $4m+2\ge \pi \mathrm{/}\theta$, hence $0<{\theta }^{\mathrm{\prime }}\le \theta <\pi \mathrm{/}2$. Sine is strictly increasing on $[0,\pi \mathrm{/}2]$, so $0<{\sin }^2{\theta }^{\mathrm{\prime }}\le {\sin }^2\theta =a$, proving $0<r\le 1$; the square roots in the following rotation are the unique nonnegative roots. On the enlarged data, flag, and temporary registers, construct $A^{\mathrm{\prime }}$ by the following finite gate sequence:

1. Start every added register in $\mathrm{\mid }0⟩$ and apply $A$ to the data.
2. Apply $C_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}$ to the data and temporary bit.
3. Controlled on the temporary bit being $1$, apply the flag rotation $R_r=\left(\begin{array}{cc}\sqrt{1-r}& -\sqrt{r}\\ \sqrt{r}& \sqrt{1-r}\end{array}\right),R_r\mathrm{\mid }0⟩=\sqrt{1-r}\mathrm{\mid }0⟩+\sqrt{r}\mathrm{\mid }1⟩\mathrm{.}$
4. Apply $C_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}^{†}$ to uncompute the temporary bit. This full unitary is $A^{\mathrm{\prime }}$; its inverse reverses these operations and uses $A^{†}$.

The logical enlarged space is $H^{\mathrm{\prime }}=H\otimes F\otimes T$, with specified input $\mathrm{\mid }{0}^{\mathrm{\prime }}⟩=\mathrm{\mid }0{⟩}_H\mathrm{\mid }0{⟩}_F\mathrm{\mid }0{⟩}_T$ and success projector ${\mathrm{\Pi }}^{\mathrm{\prime }}={\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}\otimes \mathrm{\mid }1⟩⟨1{\mathrm{\mid }}_F\otimes I_T$. Its required reflections are $S_0^{\mathrm{\prime }}=I_{H^{\mathrm{\prime }}}-2\mathrm{\mid }{0}^{\mathrm{\prime }}⟩⟨0^{\mathrm{\prime }}\mathrm{\mid }$ and $S_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}^{\mathrm{\prime }}=I_{H^{\mathrm{\prime }}}-2{\mathrm{\Pi }}^{\mathrm{\prime }}$. Select and charge the following access modes before execution.

• Zero reflection. Either explicitly supply one direct $S_0^{\mathrm{\prime }}$ call, or supply controlled access $C(S_0)$ to the original data reflection $S_0=I_H-2\mathrm{\mid }0⟩⟨0\mathrm{\mid }$. In the latter mode, initialize an external scratch qubit $q$ to $0$; apply $X$ to $F,T$, Toffoli$(F,T;q)$, $C(S_0)$ controlled by $q$ on $H$, Toffoli$(F,T;q)$, and $X$ to $F,T$ again. This uses one controlled-$S_0$ call, two Toffolis and four $X$ gates per enlarged zero reflection. Controlled $S_0$ is an additional capability and is not inferred from ordinary $S_0$ access.
• Good reflection. In the constructed mode, apply $C_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}$ to $(H,q)$ with external scratch $q=0$, then $CZ(q,F)$, then $C_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}^{†}$ to $(H,q)$. This uses two flag calls and one $CZ$ per $S_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}^{\mathrm{\prime }}$. An alternative direct mode explicitly supplies and charges $S_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}^{\mathrm{\prime }}$ instead. Here $X$, Toffoli and $CZ$ are the exact supplied qubit gates of The Pauli matrices, Toffoli and Fredkin gates and Controlled-Z and SWAP, with their gate costs charged.

The scratch $q$ starts and ends in $0$ for each reflection and may be reused. It is external implementation workspace, not part of the logical input $\mathrm{\mid }{0}^{\mathrm{\prime }}⟩$ or the projector defining $S_0^{\mathrm{\prime }}$. The constructions implement the displayed logical operators on every vector of $H^{\mathrm{\prime }}$ with clean scratch; neither assumes $T=0$ to implement $I_T$ in the good projector.

Prepare $A^{\mathrm{\prime }}\mathrm{\mid }{0}^{\mathrm{\prime }}⟩$, apply exactly $m$ iterates $-A^{\mathrm{\prime }}{S}_0^{\mathrm{\prime }}{A}^{\mathrm{\prime }†}{S}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}^{\mathrm{\prime }}$, then perform the projective instrument $\{{\mathrm{\Pi }}^{\mathrm{\prime }},I-{\mathrm{\Pi }}^{\mathrm{\prime }}\}$. The terminal instrument is an explicitly supplied, separately charged capability. Alternatively construct it with two external clean bits $q,d$: apply $C_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}$ on $(H,q)$, Toffoli$(q,F;d)$, measure only $d$ in the computational basis to obtain the good/bad record, then reverse the Toffoli and the flag call. Both scratch bits return to $0$ on either observed branch; this option adds two flag calls, two Toffolis and one bit measurement, separately from the reflection counts. Return the good conditional output, discarding $F,T$; $T$ is clean and $F=1$ on success. In the diagonal classical-output specialization, measure the designated output after the good outcome and use the supplied verifier.

The ideal exact-real and exact-rotation assumptions are part of the input model. A finite-precision implementation requires a separate error budget and theorem.

Let $0<a<1$, let $\varphi ,\phi \in [0,2\pi )$, and restrict to $\varphi \mathrm{\ne }\pi$. In the ordered $(\mathrm{\mid }G⟩,\mathrm{\mid }B⟩)$ basis of Prepared unitary and success subspace for amplitude amplification, the two diagonal entries of $Q(\varphi ,\phi )$ coincide if and only if $\tan (\phi \mathrm{/}2)=\tan (\varphi \mathrm{/}2)(1-2a),$ where $\tan t:=\sin t\mathrm{/}\cos t$ when $\cos t\mathrm{\ne }0$. The matching phase is the unique $\phi \in [0,2\pi )\setminus \{\pi \}$ satisfying this equation. At $\varphi =0$ it is $\phi =0$. If $\varphi =\pi$ and $a\mathrm{\ne }1\mathrm{/}2$, the diagonal entries coincide exactly at $\phi =\pi$; if $\varphi =\pi$ and $a=1\mathrm{/}2$, both diagonal entries vanish for every $\phi$. For $a\in \{0,1\}$, the good/bad span is one-dimensional and no two-diagonal matching condition is asserted.

For a fixed $k$-iterate procedure, the displayed factorization of $Q$ uses $k+1$ forward calls to $A$, $k$ inverse calls to $A^{†}$, $k$ good-subspace phase operations, and $k$ zero-input phase operations. It then uses one projective good/bad instrument. If classical output verification is requested, count its supplied verifier separately (one call when the task model assigns one query to verification). Controlled $A$, state-preparation synthesis, gates, and classical costs are separate access coordinates and are not inferred to be free.

For $0<a<1$, let $\theta \in (0,\pi \mathrm{/}2)$ satisfy ${\sin }^2\theta =a$, and let $k$ be the maximizer selected by Known-amplitude amplification with integer rounding. Its success probability is at least $\max \{a,1-a\}$. The $a=0$ branch returns fail, and the $a=1$ branch succeeds with probability $1$.

Under the exact access and rotation assumptions of Exact success amplification by attenuating the good branch, its output is good with probability $1$ for every $0<a\le 1$. The $a=0$ branch returns fail and makes no claim that a good output exists.

For $0<a<1$, let ${\sin }^2\theta =a$. For every integer $M\ge 1$, the second fresh sample with $j$ uniform on $\{1,\dots ,M\}$ has good-outcome probability $p_M=\frac{1}{M}{\sum }_{j=1}^M{\sin }^2((2j+1)\theta )=\frac{1}{2}-\frac{1}{2M}{\sum }_{j=1}^M\cos ((4j+2)\theta )\ge \frac{1}{2}-\frac{1}{2M\mathrm{\mid }\sin (2\theta )\mathrm{\mid }}\mathrm{.}$ For every $a>0$, the procedure Unknown-amplitude randomized search returns a good output with probability $1$. If $a=0$, it never returns a good output and does not halt.