Weak quantum sabotage index complexity
Find a sabotaged coordinate with quantum access to the sabotaged string alone.
Definition
In the weak oracle model of \(\mathrm{QS}_{\mathrm{weak}}(f)\), output a coordinate $i$ with $z_i\in\{\ast,\dagger\}$, with probability at least $2/3$. Reading that coordinate once more also reveals the sabotage symbol. The classical versions of the decision and index tasks are equivalent up to constants; equivalence remains open for quantum algorithms [CMP24].
Basic facts
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}}(f)\). “\(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}}(f)\) in terms of it” is the pair with \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}}(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 |