Quantum Sabotage Complexity

Cornelissen, Arjan, Mande, Nikhil S ORCID: 0000-0002-9520-7340 and Patro, Subhasree (2024) Quantum Sabotage Complexity In: Foundations on Software Technology and Theoretical Computer Science (FSTTCS), 2024-12-16 - 2024-12-18, IIT Gandhinagar.

Text REF_CMP24.pdf - Author Accepted Manuscript Download (662kB) | Preview

Abstract

Given a Boolean function f : {0, 1}n → {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<inf>sab</inf>: 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<inf>sab</inf>. A natural follow-up question is to understand the Q(f<inf>sab</inf>), the quantum query complexity of f<inf>sab</inf>. 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 Q(f<inf>sab</inf>) = 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<inf>sab</inf>) = O(min {Q(f)^1.5, √n}). Q(f<inf>sab</inf>) = Ω(√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<inf>sab</inf>) 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<inf>sab</inf>) = Θ(fbs(f)), ruling out the possibility that Q(f<inf>sab</inf>) = Θ(√fbs(f)) for all f.

Item Type:	Conference Item (Unspecified)
Uncontrolled Keywords:	Sabotage complexity, quantum query complexity, Boolean functions, fractional block sensitivity
Divisions:	Faculty of Science & Engineering Faculty of Science & Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	18 Oct 2024 08:28
Last Modified:	23 May 2026 09:24
DOI:	10.4230/LIPIcs.FSTTCS.2024.19
Related Websites:	Author
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3185174
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.