Q The Query Complexity Zoo
\(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}(f)\)

Strong quantum sabotage index complexity

Find a sabotaged coordinate with quantum access to both completions and the sabotaged string.

Definition

In the strong oracle model of \(\mathrm{QS}_{\mathrm{str}}(f)\), output an index $i$ with $x_i\ne y_i$ (equivalently $z_i\in\{\ast,\dagger\}$), with probability at least $2/3$.

Basic facts

  • $\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}=O(\mathrm{Q}^{3/2})$, even for partial functions [CMP24, Theorem 1.2]. The proof actually uses quantum distinguishing complexity in place of $\mathrm{Q}$.
  • Whether the exponent can be reduced to $1$ is open [CMP24].
  • 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{ind}}_{\mathrm{str}}(f)\). “\(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}(f)\) in terms of it” is the pair with \(\mathrm{QS}^{\mathrm{ind}}_{\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.

Other measure \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}(f)\) in terms of it It in terms of \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}(f)\)
\(\mathrm{QS}_{\mathrm{str}}(f)\) Strong quantum sabotage complexity total1,6 partial1,? derived open pair → total1,1 partial1,1 open pair →
\(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}}(f)\) Weak quantum sabotage index complexity total1,1 partial1,1 open pair → total1,6 partial1,? derived open pair →
\(\mathrm{QS}_{\mathrm{weak}}(f)\) Weak quantum sabotage complexity total1,6 partial1,? derived open pair → total1,6 partial1,? derived open pair →
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity total1,1.5 partial1,1.5 open pair → total2,6 partial2,? open pair →
\(\mathrm{QC}(f)\) Quantum certificate complexity total2,6 partial2,? derived open pair → total1,1 partial1,1 open pair →

The 5 above are this entry’s hand-picked neighbours; the other 88 are everything else in the zoo, by category.

Known values

FunctionValueNotes
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