Strong quantum sabotage complexity
Quantum sabotage decision with query access to both opposite-output completions.
also written:
strong decision sabotage
Definition
Use the same sabotaged input and decision task as \(\mathrm{QS}_{\mathrm{weak}}(f)\), but a query to coordinate $i$ returns the triple $(x_i,y_i,z_i)$, where $f(x)=0$, $f(y)=1$, and $z_i$ is their common bit or the sabotage symbol. The algorithm must distinguish $\ast$ from $\dagger$ with error at most $1/3$.
Basic facts
- $\mathrm{QS}_{\mathrm{str}}=O(\mathrm{Q})$ for partial as well as total functions [CMP24, Lemma 1.1].
- $\mathrm{QS}_{\mathrm{str}}=\Omega(\sqrt{\mathrm{fbs}})$ [CMP24, Theorem 1.4]; [KLLPV26] verify that the proof also covers partial functions.
- Its certification transform is $\Theta(\mathrm{QC})$ [KLLPV26, Theorem 4].
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{QS}_{\mathrm{str}}(f)\). “\(\mathrm{QS}_{\mathrm{str}}(f)\) in terms of it” is the pair with \(\mathrm{QS}_{\mathrm{str}}(f)\) on the left (the matrix row); the other column is the reverse. Each cell gives, per setting, the exponent range a,b of the best bounds known — \(\mathrm{M_1} = \Omega(\mathrm{M_2}^{a})\) below and \(\mathrm{M_1} = O(\mathrm{M_2}^{b})\) above, so \(a = b\) means settled — or a glyph where no polynomial bound exists at all. These are derived, not just read off the exponent table, so they are present for pairs the table does not cover. A cell with no entry for a setting is one where the zoo has nothing at that setting, and a — one where the ordered pair is empty in all three; derived marks a direction with no hand-written relation record behind it, which is the common case and not a hole.
The 5 above are this entry’s hand-picked neighbours; the other 88 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| OR total | \(\Theta(\sqrt n)\) | CMP24 Section 1.1: the common √fbs lower bound and Grover √n ceiling meet. CMP24 |
| AND total | \(\Theta(\sqrt n)\) | CMP24 Section 1.1: the common √fbs lower bound and Grover √n ceiling meet. CMP24 |
| PARITY total | \(\Theta(\sqrt n)\) | CMP24 Section 1.1: the common √fbs lower bound and Grover √n ceiling meet. CMP24 |
| MAJORITY total | \(\Theta(\sqrt n)\) | CMP24 Section 1.1: the common √fbs lower bound and Grover √n ceiling meet. CMP24 |
| ADDRESS / multiplexer total | \(\Theta(k)\) | CMP24 Theorem 5.3 and Appendix B: all four sabotage variants equal Θ(k). The paper’s parameter n is the address length k used here. CMP24 |