2026-07-24T03:33:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22208 2024-12-05T15:18:03Z ddc:004 open_access

Quantum Sabotage Complexity Cornelissen, Arjan Mande, Nikhil S. Patro, Subhasree Sabotage complexity quantum query complexity Boolean functions fractional block sensitivity 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^{-1}(0) and an input y ∈ f^{-1}(1), either all differing bits are replaced by a *, or all differing bits 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 the 𝖰(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 for all Boolean functions f : {0,1}ⁿ → {0,1}. - If we have additional query access to x and y, then 𝖰(f_sab) = O(min{𝖰(f),√n}). - If an algorithm is also required to output a differing index of a 0-input and a 1-input, then 𝖰(f_sab) = O(min{𝖰(f)^{1.5}, √n}). - 𝖰(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 𝖰(f_sab) is polynomially related to 𝖰(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, 𝖰(f_sab) = Θ(fbs(f)), ruling out the possibility that 𝖰(f_sab) = Θ(√{fbs(f)}) for all f. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Arjan Cornelissen and Nikhil S. Mande and Subhasree Patro 2024 Is Part Of LIPIcs, Volume 323, 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2024.19 urn:nbn:de:0030-drops-222082 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2024.19 eng https://creativecommons.org/licenses/by/4.0/legalcode