Algorithm Composition, Precision Budgets, and Dequantization — Examples

With $L=3$, the allocator sets ${\epsilon }_j=(3\mathrm{/}100)\mathrm{/}3=1\mathrm{/}100$ for each $j\in \{1,2,3\}$.

For each $a,b$, the tensor pairing in [F4] gives $⟨E_{ab}x,y⟩=⟨x,u_{ab}⟩⟨u_{ab},y⟩=⟨x,E_{ab}y⟩$, so $E_{ab}$ is self-adjoint. Since $\mathrm{\parallel }{u}_{ab}\mathrm{\parallel }=1$, $E_{ab}^2=E_{ab}$ and $⟨E_{ab}x,x⟩=\mathrm{\mid }⟨x,u_{ab}⟩{\mathrm{\mid }}^2\ge 0$. The basis expansion from [F4] gives ${\sum }_{a,b}{E}_{ab}=I$; hence the family is a finite POVM by [F5].

Each local error is therefore at most $1\mathrm{/}100$. Applying [F2], the composed channel error is at most $1\mathrm{/}100+1\mathrm{/}100+1\mathrm{/}100=3\mathrm{/}100=\epsilon$.

The input $\rho$ and the four-outcome POVM meet the reference and measurement hypotheses of [F2] by [F3] and step 1.2. Their outcome laws for the ideal and implemented composites therefore differ in total variation by at most $3\mathrm{/}100$.

Use the quantum-state output type from [F1] and the empty circuit. It leaves $\mathrm{\mid }{0}^n⟩$ unchanged using zero gate occurrences. The full amplitude vector has $N=2^n$ entries, one equal to $1$ and the remaining $2^n-1$ equal to $0$; encode these entries by one bit each.

The explicit list has $2^n$ designated output bits, so [F2] gives at least $2^n$ bit operations to write it. The empty circuit has zero gate occurrences, so the state output does not entail a polynomial-time amplitude-list output.

For every finite reference space, the extensions of ${\mathcal{I}}_s$ and ${\mathcal{I}}_f$ are multiplication by the nonnegative scalars $p$ and $1-p$, so they preserve positive operators by [F3]. For every operator $X$, $\mathrm{tr}({\mathcal{I}}_s(X))+\mathrm{tr}({\mathcal{I}}_f(X))=p\mathrm{tr}X+(1-p)\mathrm{tr}X=\mathrm{tr}X$. Thus the maps form an instrument by [F1], and $p_s=\mathrm{tr}(p\rho )=p$ by [F4].

If $p>0$, then ${\mathcal{I}}_s(\rho )\mathrm{/}{p}_s=p\rho \mathrm{/}p=\rho$. If $p=0$, both numerator and success probability are zero, so [F1] assigns $\mathrm{\perp }$ rather than a density operator. The unconditional failure probability is $1-p$, including $1$ at $p=0$; it is reported separately from the conditional-state guarantee, as required by [F2].

The squared-entry law of $A^{(j)}$ is the point mass at $j$. By [F3], error at most $1\mathrm{/}3$ requires output $j$ with probability at least $2\mathrm{/}3$.

Fix the algorithm's internal randomness and suppose it makes at most $t<n$ distinct entry queries. If the queried set contains $j$, it can identify $j$; averaged over a uniformly chosen hidden $j$, this event has probability at most $t\mathrm{/}n$. If the queried set does not contain $j$, all observed answers are zero and the fixed execution can output at most one of the $n-t$ unqueried indices, so its conditional chance to guess correctly is at most $1\mathrm{/}(n-t)$. Thus average success is at most $t\mathrm{/}n+(1-t\mathrm{/}n)\mathrm{/}(n-t)=(t+1)\mathrm{/}n$. Averaging over internal randomness preserves this bound.

To achieve success at least $2\mathrm{/}3$ for every hidden $j$, the average success must be at least $2\mathrm{/}3$, so $(t+1)\mathrm{/}n\ge 2\mathrm{/}3$ and $t\ge 2n\mathrm{/}3-1=\mathrm{\Omega }(n)$. Hence the entry-query interface cannot supply the claimed sublinear sampling cost; any preprocessing that builds a sampler must also be charged. The condition of [F2] is therefore essential.