For a partial Boolean function $f:D\to\{0,1\}$, choose opposite-output inputs $x,y$. A sabotaged input agrees with their common bits and replaces every differing bit by the same symbol $\ast$ or $\dagger$. The quantum algorithm must either distinguish the symbols or output a sabotaged coordinate [CMP24, Section 3].
| Oracle | Distinguish $\ast$ / $\dagger$ | Find a sabotaged index |
|---|---|---|
| Only the sabotaged string $z$ | \(\mathrm{QS}_{\mathrm{weak}}(f)\) | \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}}(f)\) |
| Triples $(x_i,y_i,z_i)$ | \(\mathrm{QS}_{\mathrm{str}}(f)\) | \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}(f)\) |
These four distinctions disappear up to constant factors for randomized sabotage \(\mathrm{RS}(f)\). Quantumly, their equivalence is open. The proved inclusions are $\mathrm{QS}_{\mathrm{str}}=O(\mathrm{QS}_{\mathrm{weak}})$, $\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}=O(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}})$, and decision costs at most index-finding plus one query in each oracle model. All four are $O(\mathrm{RS})$ and $O(\sqrt n)$.
For partial as well as total functions, $\mathrm{QS}_{\mathrm{str}}=O(\mathrm{Q})$ and $\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}=O(\mathrm{Q}^{3/2})$ [CMP24, Lemma 1.1 and Theorem 1.2]. The general weak-model upper bound in terms of $\mathrm{Q}$ is only stated here for total functions, via $\mathrm{QS}_{\mathrm{weak}},\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}}=O(\mathrm{R})=O(\mathrm{Q}^4)$.
The common lower bound is $\Omega(\sqrt{\mathrm{fbs}})=\Omega(\mathrm{QC})$. [CMP24] state its theorem for total functions; [KLLPV26, proof of Theorem 4(v)] explicitly verify that the proof also covers partial functions. Grover meets this bound for AND, OR, PARITY and MAJORITY. It is not always tight: on \(\mathrm{ADDR}_k\), all four sabotage variants are $\Theta(n)$ and $\mathrm{fbs}=n+1$. For total functions the paper gives the converse polynomial relation $\mathrm{Q}=\widetilde O(\mathrm{QS}^6)$ for each variant.
Applying the Operational certification complexity transform collapses all four variants to $\Theta(\mathrm{QC})$ [KLLPV26, Theorem 4]. This does not establish equivalence of the original measures. See Do the quantum sabotage variants coincide, and how do they compare with Q?.