Grothendieck inequalities characterize converses to the polynomial
method
- URL: http://arxiv.org/abs/2212.08559v2
- Date: Sat, 30 Dec 2023 12:26:30 GMT
- Title: Grothendieck inequalities characterize converses to the polynomial
method
- Authors: Jop Bri\"et, Francisco Escudero Guti\'errez and Sander Gribling
- Abstract summary: A surprising 'converse to the method' of Aaronson et al.
(CCC16) shows that any bounded quadratic can be computed exactly by a 1-query up to a universal multiplicative factor related to the Grothendieck constant.
- Score: 1.024113475677323
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A surprising 'converse to the polynomial method' of Aaronson et al. (CCC'16)
shows that any bounded quadratic polynomial can be computed exactly in
expectation by a 1-query algorithm up to a universal multiplicative factor
related to the famous Grothendieck constant. Here we show that such a result
does not generalize to quartic polynomials and 2-query algorithms, even when we
allow for additive approximations. We also show that the additive approximation
implied by their result is tight for bounded bilinear forms, which gives a new
characterization of the Grothendieck constant in terms of 1-query quantum
algorithms. Along the way we provide reformulations of the completely bounded
norm of a form, and its dual norm.
Related papers
- Spectral quantization of discrete random walks on half-line, and
orthogonal polynomials on the unit circle [0.0]
We represent unitary evolution operator of the quantum walk in terms of Verbs on the unit circle.
We show that the both Markovs systems and their measures are connected by the classical SzegHo map.
arXiv Detail & Related papers (2023-06-21T13:41:51Z) - Sums of squares certificates for polynomial moment inequalities [1.6385815610837167]
This paper introduces and develops the framework of moment expressions, which are expressions in commuting variables and their formal mixed moments.
As an application, two open nonlinear Bell inequalities from quantum physics are settled.
arXiv Detail & Related papers (2023-06-09T08:55:26Z) - A Direct Reduction from the Polynomial to the Adversary Method [92.54311953850168]
We give a simple and direct reduction from the method (in the form of a dual) to the adversary method.
This shows that any lower bound in the form of a dual is an adversary lower bound of a specific form.
arXiv Detail & Related papers (2023-01-24T21:37:20Z) - An Exponential Separation Between Quantum Query Complexity and the
Polynomial Degree [79.43134049617873]
In this paper, we demonstrate an exponential separation between exact degree and approximate quantum query for a partial function.
For an alphabet size, we have a constant versus separation complexity.
arXiv Detail & Related papers (2023-01-22T22:08:28Z) - Posterior and Computational Uncertainty in Gaussian Processes [52.26904059556759]
Gaussian processes scale prohibitively with the size of the dataset.
Many approximation methods have been developed, which inevitably introduce approximation error.
This additional source of uncertainty, due to limited computation, is entirely ignored when using the approximate posterior.
We develop a new class of methods that provides consistent estimation of the combined uncertainty arising from both the finite number of data observed and the finite amount of computation expended.
arXiv Detail & Related papers (2022-05-30T22:16:25Z) - On converses to the polynomial method [0.0]
A surprising 'converse to the method' of Aaronson et al. shows that any bounded quadratic can be computed exactly up to a universal multiplicative factor related to the Grohendieck constant.
We show that the result still holds when we allow for a small additive error.
arXiv Detail & Related papers (2022-04-26T13:32:02Z) - Influence in Completely Bounded Block-multilinear Forms and Classical
Simulation of Quantum Algorithms [3.9156637371363874]
We prove the Aaronson-Ambainis conjecture (Theory of Computing '14)
In every completely bounded degree-$d$ block-multilinear form with constant variance, there always exists a variable with influence at least $1/mathrmpoly(d)$.
We obtain efficient classical almost-everywhere simulation for a particular class of quantum algorithms.
arXiv Detail & Related papers (2022-03-01T03:42:24Z) - Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
We study methods that use a collection of random observations to compute approximate solutions by searching over a known low-dimensional subspace of the Hilbert space.
We show how our results precisely characterize the error of a class of temporal difference learning methods for the policy evaluation problem with linear function approximation.
arXiv Detail & Related papers (2020-12-09T20:19:32Z) - Robustly Learning Mixtures of $k$ Arbitrary Gaussians [47.40835932474677]
We give a-time algorithm for the problem of robustly estimating a mixture of $k$ arbitrary Gaussians in $mathbbRd$, for any fixed $k$, in the presence of a constant fraction of arbitrary corruptions.
Our main tools are an efficient emphpartial clustering algorithm that relies on the sum-of-squares method, and a novel tensor decomposition algorithm that allows errors in both Frobenius norm and low-rank terms.
arXiv Detail & Related papers (2020-12-03T17:54:03Z) - A refinement of Reznick's Positivstellensatz with applications to
quantum information theory [72.8349503901712]
In Hilbert's 17th problem Artin showed that any positive definite in several variables can be written as the quotient of two sums of squares.
Reznick showed that the denominator in Artin's result can always be chosen as an $N$-th power of the squared norm of the variables.
arXiv Detail & Related papers (2019-09-04T11:46:26Z)
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.