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
- Optimal Estimator for Linear Regression with Shuffled Labels [17.99906229036223]
This paper considers the task of linear regression with shuffled labels.
$mathbf Y in mathbb Rntimes m, mathbf Pi in mathbb Rntimes p, mathbf B in mathbb Rptimes m$, and $mathbf Win mathbb Rntimes m$, respectively.
arXiv Detail & Related papers (2023-10-02T16:44:47Z) - 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) - Low-degree learning and the metric entropy of polynomials [49.1574468325115]
We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
arXiv Detail & Related papers (2022-03-17T23:52:08Z) - 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.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.