Quantum Sabotage Complexity

• URL: http://arxiv.org/abs/2408.12595v1
• Date: Thu, 22 Aug 2024 17:57:58 GMT
• Title: Quantum Sabotage Complexity
• Authors: Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro,
• Abstract summary: We show $mathsfQ(f_mathsfsab)$, the quantum query complexity of $f_mathsfsab$. We show that when $f$ is the Indexing function, $mathsfQ(f_mathsfsab)=Theta(sqrtmathsfsab)$, ruling out the possibility that $mathsfQ(f_mathsfsab)=Theta(sqrtmathsf
• Score: 0.7812210699650152
• License: http://creativecommons.org/licenses/by/4.0/
• 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 $*$, or all differing locations are replaced by $\dagger$, 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}}) = \Omega(\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}})=\Theta(\mathsf{fbs}(f))$, ruling out the possibility that $\mathsf{Q}(f_{\mathsf{sab}})=\Theta(\sqrt{\mathsf{fbs}(f)})$ for all $f$.

Related papers

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• Efficient Continual Finite-Sum Minimization [52.5238287567572]
  We propose a key twist into the finite-sum minimization, dubbed as continual finite-sum minimization. Our approach significantly improves upon the $mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$ requires. We also prove that there is no natural first-order method with $mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$, establishing that the first-order complexity of our method is nearly tight.
  arXiv  Detail & Related papers  (2024-06-07T08:26:31Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  Multi-head attention layer is one of the key components of the transformer architecture that sets it apart from traditional feed-forward models. In this work, we initiate the study of provably learning a multi-head attention layer from random examples. We prove computational lower bounds showing that in the worst case, exponential dependence on $m$ is unavoidable.
  arXiv  Detail & Related papers  (2024-02-06T15:39:09Z)
• Quantum Oblivious LWE Sampling and Insecurity of Standard Model Lattice-Based SNARKs [4.130591018565202]
  The Learning Errors With Errors ($mathsfLWE$) problem asks to find $mathbfs$ from an input of the form $(mathbfAmathbfs+mathbfe$) We do not focus on solving $mathsfLWE$ but on the task of sampling instances. Our main result is a quantum-time algorithm that samples well-distributed $mathsfLWE$ instances while provably not knowing the solution.
  arXiv  Detail & Related papers  (2024-01-08T10:55:41Z)
• Noisy Computing of the $\mathsf{OR}$ and $\mathsf{MAX}$ Functions [22.847963422230155]
  We consider the problem of computing a function of $n$ variables using noisy queries. We show that an expected number of queries of [ (1 pm o(1)) fracnlog frac1deltaD_mathsfKL(p | 1-p) ] is both sufficient and necessary to compute both functions.
  arXiv  Detail & Related papers  (2023-09-07T19:37:52Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  We introduce efficient $(1+varepsilon)$-approximation algorithms for the binary matrix factorization (BMF) problem. The goal is to approximate $mathbfA$ as a product of low-rank factors. Our techniques generalize to other common variants of the BMF problem.
  arXiv  Detail & Related papers  (2023-06-02T18:55:27Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  We study the problem of PAC learning halfspaces on $mathbbRd$ with Massart noise under Gaussian marginals. Our results qualitatively characterize the complexity of learning halfspaces in the Massart model.
  arXiv  Detail & Related papers  (2021-08-19T16:16:48Z)
• On relating one-way classical and quantum communication complexities [6.316693022958221]
  Communication complexity is the amount of communication needed to compute a function when the function inputs are distributed over multiple parties. A fundamental question in quantum information is the relationship between one-way quantum and classical communication complexities.
  arXiv  Detail & Related papers  (2021-07-24T14:35:09Z)
• The planted matching problem: Sharp threshold and infinite-order phase transition [25.41713098167692]
  We study the problem of reconstructing a perfect matching $M*$ hidden in a randomly weighted $ntimes n$ bipartite graph. We show that if $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ for an arbitrarily small constant $epsilon>0$, the reconstruction error for any estimator is shown to be bounded away from $0$.
  arXiv  Detail & Related papers  (2021-03-17T00:59:33Z)
• Linear Bandits on Uniformly Convex Sets [88.3673525964507]
  Linear bandit algorithms yield $tildemathcalO(nsqrtT)$ pseudo-regret bounds on compact convex action sets. Two types of structural assumptions lead to better pseudo-regret bounds.
  arXiv  Detail & Related papers  (2021-03-10T07:33:03Z)
• StoqMA meets distribution testing [0.0]
  We provide a novel connection between $mathsfStoqMA$ and distribution testing via reversible circuits. We show that both variants of $mathsfStoqMA$ that without any ancillary random bit and with perfect soundness are contained in $mathsfNP$. Our results make a step towards collapsing the hierarchy $mathsfMA subseteq mathsfStoqMA subseteq mathsfSBP$ [BBT06], in which all classes are contained in $
  arXiv  Detail & Related papers  (2020-11-11T12:30:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.