Worst-case bounded-error correctness

A quantum or classical solver in Quantum query algorithm and Classical query algorithm for a decision task $(Y,N)$ of QA task and promise domain has bounded error (with the QA convention) if its normalized output law assigns probability at least $2\mathrm{/}3$ to the correct answer for every encoded promised instance. A search solver has bounded error if, for every encoded $z$ in its domain $D$, its output law assigns probability at least $2\mathrm{/}3$ to outputs $w$ satisfying $(z,w)\in R$. The guarantee is worst-case per instance, not averaged over an input distribution. The constant $2\mathrm{/}3$ is a convention; amplification and its query/access cost are separate results.

For quantum algorithms the success event is evaluated from the normalized finite-branch output law of Normalized output law for finite quantum query branches. Its normalization follows from the finite instrument and unitary branches in that definition; the success threshold remains a per-instance condition.