Quantum Sabotage Complexity

Abstract

Given a Boolean function $f:\{0,1{\}}^n\to \{0,1\}$, the goal in the usual query model is to compute $f$ on an unknown input $x\in \{0,1{\}}^n$ while minimizing the number of queries to $x$. One can also consider a "distinguishing" problem denoted by $f_{\mathsf{sab}}$: given an input $x\in f^{-1}(0)$ and an input $y\in f^{-1}(1)$, either all differing locations are replaced by a $\ast$, or all differing locations are replaced by $†$, and an algorithm's goal is to identify which of these is the case while minimizing the number of queries. Ben-David and Kothari [ToC'18] introduced the notion of randomized sabotage complexity of a Boolean function to be the zero-error randomized query complexity of $f_{\mathsf{sab}}$. A natural follow-up question is to understand $\mathsf{Q}(f_{\mathsf{sab}})$, the quantum query complexity of $f_{\mathsf{sab}}$. In this paper, we initiate a systematic study of this. The following are our main results: $\bullet$ If we have additional query access to $x$ and $y$, then $\mathsf{Q}(f_{\mathsf{sab}})=O(\min \{\mathsf{Q}(f),\sqrt{n}\})$. $\bullet$ If an algorithm is also required to output a differing index of a 0-input and a 1-input, then $\mathsf{Q}(f_{\mathsf{sab}})=O(\min \{\mathsf{Q}(f{)}^{1.5},\sqrt{n}\})$. $\bullet$ $\mathsf{Q}(f_{\mathsf{sab}})=\hat{I}\text{c◯}(\sqrt{\mathsf{fbs}(f)})$, where $\mathsf{fbs}(f)$ denotes the fractional block sensitivity of $f$. By known results, along with the results in the previous bullets, this implies that $\mathsf{Q}(f_{\mathsf{sab}})$ is polynomially related to $\mathsf{Q}(f)$. $\bullet$ The bound above is easily seen to be tight for standard functions such as And, Or, Majority and Parity. We show that when $f$ is the Indexing function, $\mathsf{Q}(f_{\mathsf{sab}})=\hat{I}˜(\mathsf{fbs}(f))$, ruling out the possibility that $\mathsf{Q}(f_{\mathsf{sab}})=\hat{I}˜(\sqrt{\mathsf{fbs}(f)})$ for all $f$.

21 pages, 1 figure