Related papers: The quantum query complexity of composition with a relation

The quantum query complexity of composition with a relation

URL: http://arxiv.org/abs/2004.06439v1
Date: Tue, 14 Apr 2020 12:07:20 GMT
Title: The quantum query complexity of composition with a relation
Authors: Aleksandrs Belovs and Troy Lee
Abstract summary: Belovs gave a modified version of the negative weight adversary method, $mathrmADV_relpm(f)$. A relation is efficiently verifiable if $mathrmADVpm(f_a) = o(mathrmADV_relpm(f))$ for every $a in [K]$.
Score: 78.55044112903148
License: http://creativecommons.org/licenses/by/4.0/
Abstract: The negative weight adversary method, $\mathrm{ADV}^\pm(g)$, is known to characterize the bounded-error quantum query complexity of any Boolean function $g$, and also obeys a perfect composition theorem $\mathrm{ADV}^\pm(f \circ g^n) = \mathrm{ADV}^\pm(f) \mathrm{ADV}^\pm(g)$. Belovs gave a modified version of the negative weight adversary method, $\mathrm{ADV}_{rel}^\pm(f)$, that characterizes the bounded-error quantum query complexity of a relation $f \subseteq \{0,1\}^n \times [K]$, provided the relation is efficiently verifiable. A relation is efficiently verifiable if $\mathrm{ADV}^\pm(f_a) = o(\mathrm{ADV}_{rel}^\pm(f))$ for every $a \in [K]$, where $f_a$ is the Boolean function defined as $f_a(x) = 1$ if and only if $(x,a) \in f$. In this note we show a perfect composition theorem for the composition of a relation $f$ with a Boolean function $g$ \[ \mathrm{ADV}_{rel}^\pm(f \circ g^n) = \mathrm{ADV}_{rel}^\pm(f) \mathrm{ADV}^\pm(g) \enspace . \] For an efficiently verifiable relation $f$ this means $Q(f \circ g^n) = \Theta( \mathrm{ADV}_{rel}^\pm(f) \mathrm{ADV}^\pm(g) )$.

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)
Fast Attention Requires Bounded Entries [19.17278873525312]
inner product attention computation is a fundamental task for training large language models such as Transformer, GPT-1, BERT, GPT-2, GPT-3 and ChatGPT. We investigate whether faster algorithms are possible by implicitly making use of the matrix $A$. This gives a theoretical explanation for the phenomenon observed in practice that attention computation is much more efficient when the input matrices have smaller entries.
arXiv Detail & Related papers (2023-02-26T02:42:39Z)
Matching upper bounds on symmetric predicates in quantum communication complexity [0.0]
We focus on the quantum communication complexity of functions of the form $f circ G = f(G)mathrmQCC_mathrmE(G)) when the parties are allowed to use shared entanglement. We show that the same statement holds emphwithout shared entanglement, which generalizes their result.
arXiv Detail & Related papers (2023-01-01T08:30:35Z)
$\mathcal{P}\mathcal{T}$-symmetric $-g\varphi^4$ theory [0.0]
Hermitian theory is proposed: $log ZmathcalPmathcalT(g)=textstylefrac12 log Z_rm Herm(-g+rm i 0+rm i 0+$. A new conjectural relation between the Euclidean partition functions $ZmathcalPmathcalT$-symmetric theory and $Z_rm Herm(lambda)$ of the $lambda varphi4$ is presented.
arXiv Detail & Related papers (2022-09-16T12:44:00Z)
The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
For every $delta>0,$ we construct CNF and formulas of size with approximate degree $Omega(n1-delta),$ essentially matching the trivial upper bound of $n. We show that for every $delta>0$, these models require $Omega(n1-delta)$, $Omega(n/4kk2)1-delta$, and $Omega(n/4kk2)1-delta$, respectively.
arXiv Detail & Related papers (2022-09-04T10:01:39Z)
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)
Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem [4.549831511476248]
We show that for any total Boolean function $f$, $bullet quad mathrmdeg(f) = O(widetildemathrmdeg(f)2)$: The degree of $f$ is at mosttrivial quadratic in the approximate degree of $f$. We show that if $f$ is a non monotone graph property of an $n$-vertex graph specified by its adjacency matrix, then $mathrmQ(f)=Omega(n)$, which is also optimal.
arXiv Detail & Related papers (2020-10-23T19:21:28Z)
The Average-Case Time Complexity of Certifying the Restricted Isometry Property [66.65353643599899]
In compressed sensing, the restricted isometry property (RIP) on $M times N$ sensing matrices guarantees efficient reconstruction of sparse vectors. We investigate the exact average-case time complexity of certifying the RIP property for $Mtimes N$ matrices with i.i.d. $mathcalN(0,1/M)$ entries.
arXiv Detail & Related papers (2020-05-22T16:55:01Z)
On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
We exploit the finite noise structure of finite sums to derive a matching $O(n2)$-upper bound under the global oracle model. Following a similar approach, we propose a novel adaptation of SVRG which is both emphcompatible with oracles, and achieves complexity bounds of $tildeO(n2+nsqrtL/mu)log (1/epsilon)$ and $O(nsqrtL/epsilon)$, for $mu>0$ and $mu=0$
arXiv Detail & Related papers (2020-02-09T03:39:46Z)

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