Abstract
Given a Boolean function f:{0,1}ⁿ→{0,1}, the goal in the usual query model is to compute f on an unknown input x ∈ {0,1}ⁿ while minimizing the number of queries to x. One can also consider a "distinguishing" problem denoted by f_sab: given an input x ∈ f⁻¹(0) and an input y ∈ f⁻¹(1), either all differing locations are replaced by a *, 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_sab. A natural follow-up question is to understand Q(f_sab), the quantum query complexity of f_sab. In this paper, we initiate a systematic study of this. The following are our main results: If we have additional query access to x and y, then Q(f_sab)=O(min{Q(f),√n}). If an algorithm is also required to output a differing index of a 0-input and a 1-input, then Q(f_sab)=O(min{Q(f)^1.5,√n}). Q(f_sab) = Ω(√fbs(f)), where fbs(f) denotes the fractional block sensitivity of f. By known results, along with the results in the previous bullets, this implies that Q(f_sab) is polynomially related to Q(f). 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, Q(f_sab)=Θ(fbs(f)), ruling out the possibility that Q(f_sab)=Θ(√fbs(f)) for all f.