Amplitude estimation and counting input/output contract

Let $H$ be a nonzero finite-dimensional complex inner-product space, $\mathrm{\mid }0⟩$ a specified unit vector, $A:H\to H$ a supplied unitary, and ${\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}$ an explicitly supplied orthogonal projection. Put $S_0=I-2\mathrm{\mid }0⟩⟨0\mathrm{\mid },S_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}=I-2{\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}},Q=-A{S}_0{A}^{\ast }{S}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}\mathrm{.}$ Each classical instance has an injective encoding $\mathrm{enc}$ from its declared instance set into $\{0,1{\}}^{\ast }$, with input size $\mathrm{\mid }\mathrm{enc}(z)\mathrm{\mid }$; the promise domain and output obligation are stated for that task. Supplied operator or oracle access is a separate resource declaration.

The success amplitude is $a=\mathrm{\parallel }{\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}A\mathrm{\mid }0⟩{\mathrm{\parallel }}^2\in [0,1]$, and $\theta =\arcsin \sqrt{a}\in [0,\pi \mathrm{/}2]$. Amplitude estimation returns an algebraically encoded estimate of $a$; its requested accuracy and failure probability are stated separately.

For counting, let $n$ be a nonnegative integer and set $N=2^n$ with address basis $\{\mathrm{\mid }x⟩:x\in \{0,1{\}}^n\}$ and a Boolean predicate $f$. Write $H_{\mathrm{H}\mathrm{a}\mathrm{d}}=2^{-1\mathrm{/}2}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)$ for the one-qubit Hadamard gate, distinct from the space $H$, and set $A=H_{\mathrm{H}\mathrm{a}\mathrm{d}}^{\otimes n}$, $\mathrm{\mid }0⟩=\mathrm{\mid }{0}^n⟩$, ${\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}={\sum }_{f(x)=1}\mathrm{\mid }x⟩⟨x\mathrm{\mid }$, and $t=\mathrm{\mid }\{x:f(x)=1\}\mathrm{\mid }$. Then the counting amplitude is $a=t\mathrm{/}N$. The preparation uses exactly $n$ ordinary Hadamard gates. Access to the controlled membership reflection is a separate explicit resource.

Two phase-estimation access modes are allowed. In the power-query mode, the model supplies each $C(Q^{2^j})$ for $0\le j<m$ as one declared query, with its individual cost recorded. In the repeated-unitary mode the model supplies $C(Q)$ and implements $C(Q^{2^j})$ by $2^j$ sequential calls, for exactly $2^m-1$ controlled-$Q$ calls. In repeated-unitary mode, each controlled-$Q$ call expands as the composite $C(-I)C(A)C(S_0)C(A^{\ast })C(S_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}})$; controlled $A$, controlled $A^{\ast }$, controlled $S_0$, controlled $S_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}$, and the control phase $C(-I)$ must all be supplied or implemented and charged. In power-query mode each supplied controlled power has its own declared cost vector, including any constituent implementations the model uses. An uncontrolled phase query does not supply any of them. Query, ordinary-gate, state-preparation, measurement, and classical bit costs are separate coordinates.