Grothendieck inequalities characterize converses to the polynomial method

• URL: http://arxiv.org/abs/2212.08559v3
• Date: Tue, 12 Nov 2024 14:04:20 GMT
• Title: Grothendieck inequalities characterize converses to the polynomial method
• Authors: Jop Briët, Francisco Escudero Gutiérrez, 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.137457877869062
• License:
• 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

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Revisiting Tropical Polynomial Division: Theory, Algorithms and Application to Neural Networks [40.137069931650444]
  Tropical geometry has recently found several applications in the analysis of neural networks with piecewise linear activation functions. This paper presents a new look at the problem of tropical division and its application to the simplification of neural networks.
  arXiv  Detail & Related papers  (2023-06-27T02:26:07Z)
• 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)
• 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)
• 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.