A note about claw function with a small range

• URL: http://arxiv.org/abs/2103.16390v1
• Date: Tue, 30 Mar 2021 14:30:35 GMT
• Title: A note about claw function with a small range
• Abstract summary: We show that the quantum query complexity of this problem is between $Omegaleft(n1/2k1/6right)$ and $Oleft(n1/2+varepsilonk1/4right)$ when $2leq kn$.
• Score: 1.2246649738388389
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In the claw detection problem we are given two functions $f:D\rightarrow R$ and $g:D\rightarrow R$ ($|D|=n$, $|R|=k$), and we have to determine if there is exist $x,y\in D$ such that $f(x)=g(y)$. We show that the quantum query complexity of this problem is between $\Omega\left(n^{1/2}k^{1/6}\right)$ and $O\left(n^{1/2+\varepsilon}k^{1/4}\right)$ when $2\leq k<n$.

Related papers

• On the Capacity Region of Individual Key Rates in Vector Linear Secure Aggregation [55.126702858312456]
  We show that it is not necessary for every user to hold a key, thereby strictly enlarging the best-known achievable region in the literature.<n>Our results uncover the novel fact that it is not necessary for every user to hold a key, thereby strictly enlarging the best-known achievable region in the literature.
  arXiv  Detail & Related papers  (2026-01-06T18:34:07Z)
• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  We show that any efficient Statistical Query algorithm for this task requires VSTAT complexity at least $tildeOmega(d1/2/alpha2)$.
  arXiv  Detail & Related papers  (2025-10-12T15:42:44Z)
• 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)
• Approximate Degrees of Multisymmetric Properties with Application to Quantum Claw Detection [0.0]
  The optimal quantum complexity of the problem is known to be $Omegaleft(sqrtG+(FG)1/6M1/6right)$ for input functions $fcolon [F]to Z$ and $gcolon [G]to Z$. The current paper proves the lower bound holds even for every smaller range $Z$ with $|Z|=Omega(FG)$.
  arXiv  Detail & Related papers  (2024-10-03T06:32:34Z)
• Tight Lower Bounds under Asymmetric High-Order Hölder Smoothness and Uniform Convexity [6.972653925522813]
  We provide tight lower bounds for the oracle complexity of minimizing high-order H"older smooth and uniformly convex functions. Our analysis generalizes previous lower bounds for functions under first- and second-order smoothness as well as those for uniformly convex functions.
  arXiv  Detail & Related papers  (2024-09-16T23:17:33Z)
• On the quantum Guerra-Morato Action Functional [0.0]
  Given a smooth potential $W:mathrmTn to mathbbR$ on the torus, the Quantum Guerra-Morato action functional is given by smallskip. We show that the expression for the second variation of a critical solution is given by smallskip.
  arXiv  Detail & Related papers  (2024-03-09T10:30:21Z)
• Dimension Independent Disentanglers from Unentanglement and Applications [55.86191108738564]
  We construct a dimension-independent k-partite disentangler (like) channel from bipartite unentangled input. We show that to capture NEXP, it suffices to have unentangled proofs of the form $| psi rangle = sqrta | sqrt1-a | psi_+ rangle where $| psi_+ rangle has non-negative amplitudes.
  arXiv  Detail & Related papers  (2024-02-23T12:22:03Z)
• Matrix concentration inequalities and efficiency of random universal sets of quantum gates [0.0]
  For a random set $mathcalS subset U(d)$ of quantum gates we provide bounds on the probability that $mathcalS$ forms a $delta$-approximate $t$-design. We show that for $mathcalS$ drawn from an exact $t$-design the probability that it forms a $delta$-approximate $t$-design satisfies the inequality $mathbbPleft(delta geq x right)leq 2D_t
  arXiv  Detail & Related papers  (2022-02-10T23:44:09Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten-$p$ norm. Our main result is an algorithm that uses only $tildeO(k/sqrtepsilon)$ matrix-vector products.
  arXiv  Detail & Related papers  (2022-02-10T16:10:41Z)
• Learning low-degree functions from a logarithmic number of random queries [77.34726150561087]
  We prove that for any integer $ninmathbbN$, $din1,ldots,n$ and any $varepsilon,deltain(0,1)$, a bounded function $f:-1,1nto[-1,1]$ of degree at most $d$ can be learned.
  arXiv  Detail & Related papers  (2021-09-21T13:19:04Z)
• Approximate Maximum Halfspace Discrepancy [6.35821487778241]
  We consider the range space $(X, mathcalH_d)$ where $X subset mathbbRd$ and $mathcalH_d$ is the set of ranges defined by $d$ halfspaces. For each halfspace $h in mathcalH_d$ define a function $Phi(h)$ that measures the "difference" between the fraction of red and fraction of blue points which fall in the range $h$.
  arXiv  Detail & Related papers  (2021-06-25T19:14:45Z)
• Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithm [46.36534144138337]
  In this paper, we investigate the sample complexity of policy evaluation in offline reinforcement learning. Under the low distribution shift assumption, we show that there is an algorithm that needs at most $Oleft(maxleft fracleftVert thetapirightVert _24varepsilon4logfracddelta,frac1varepsilon2left(d+logfrac1deltaright)right right)$ samples to approximate the
  arXiv  Detail & Related papers  (2021-03-17T18:18:57Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  We study the problem of agnostic $Q$-learning with function approximation in deterministic systems. We show that if $delta = Oleft(rho/sqrtdim_Eright)$, then one can find the optimal policy using $Oleft(dim_Eright)$.
  arXiv  Detail & Related papers  (2020-02-17T18:41:49Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  We prove tight lower bounds for the following variant of the counting problem considered by Aaronson, Kothari, Kretschmer, and Thaler ( 2020) The task is to distinguish whether an input set $xsubseteq [n]$ has size either $k$ or $k'=(1+varepsilon)k$.
  arXiv  Detail & Related papers  (2020-02-17T10:53:50Z)

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.