A Direct Reduction from the Polynomial to the Adversary Method

• URL: http://arxiv.org/abs/2301.10317v1
• Date: Tue, 24 Jan 2023 21:37:20 GMT
• Title: A Direct Reduction from the Polynomial to the Adversary Method
• Authors: Aleksandrs Belovs
• Abstract summary: 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.
• Score: 92.54311953850168
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The polynomial and the adversary methods are the two main tools for proving lower bounds on query complexity of quantum algorithms. Both methods have found a large number of applications, some problems more suitable for one method, some for the other. It is known though that the adversary method, in its general negative-weighted version, is tight for bounded-error quantum algorithms, whereas the polynomial method is not. By the tightness of the former, for any polynomial lower bound, there ought to exist a corresponding adversary lower bound. However, direct reduction was not known. In this paper, we give a simple and direct reduction from the polynomial method (in the form of a dual polynomial) to the adversary method. This shows that any lower bound in the form of a dual polynomial is actually an adversary lower bound of a specific form.

Related papers

• Complementary polynomials in quantum signal processing [0.0]
  To implement a given $P$, one must first construct a corresponding complementary $Q$. Existing approaches to this problem employ numerical methods that are not amenable to explicit error analysis. We present a new approach to complementarys using complex analysis.
  arXiv  Detail & Related papers  (2024-06-06T16:47:11Z)
• Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
  We show that policies under study avoid strict saddle points / submanifolds with probability 1. This result provides an important sanity check as it shows that, almost always, the limit state of an algorithm can only be a local minimizer.
  arXiv  Detail & Related papers  (2023-11-04T11:12:24Z)
• A degree reduction method for an efficient QUBO formulation for the graph coloring problem [0.32985979395737774]
  We introduce a new degree reduction method for homogeneous symmetrics on binary variables that generalizes the conventional degree reduction methods introduced by Freedman and Ishikawa. We also design an degree reduction algorithm for generals on binary variables, simulated on a graph coloring problem for random graphs and compared the results with the conventional methods.
  arXiv  Detail & Related papers  (2023-06-21T07:56:56Z)
• Sparse resultant based minimal solvers in computer vision and their connection with the action matrix [17.31412310131552]
  We show that for some camera geometry problems our extra-based method leads to smaller and more stable solvers than the state-of-the-art Grobner basis-based solvers. It provides a competitive alternative to popularner basis-based methods for minimal problems in computer vision.
  arXiv  Detail & Related papers  (2023-01-16T14:25:19Z)
• Grothendieck inequalities characterize converses to the polynomial method [1.024113475677323]
  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.
  arXiv  Detail & Related papers  (2022-12-16T16:26:04Z)
• 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)
• l1-Norm Minimization with Regula Falsi Type Root Finding Methods [81.55197998207593]
  We develop an efficient approach for non likelihoods using Regula Falsi root-finding techniques. Practical performance is illustrated using l1-regularized classes t.
  arXiv  Detail & Related papers  (2021-05-01T13:24:38Z)
• Computational Barriers to Estimation from Low-Degree Polynomials [81.67886161671379]
  We study the power of low-degrees for the task of detecting the presence of hidden structures. For a large class of "signal plus noise" problems, we give a user-friendly lower bound for the best possible mean squared error achievable by any degree. As applications, we give a tight characterization of the low-degree minimum mean squared error for the planted submatrix and planted dense subgraph problems.
  arXiv  Detail & Related papers  (2020-08-05T17:52:10Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  We propose two novel conditional gradient-based methods for solving structured convex optimization problems. The most important feature of our framework is that only a subset of the constraints is processed at each iteration. Our algorithms rely on variance reduction and smoothing used in conjunction with conditional gradient steps, and are accompanied by rigorous convergence guarantees.
  arXiv  Detail & Related papers  (2020-07-07T21:26:35Z)
• SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  SURF is an algorithm for approximating distributions by piecewises. It outperforms state-of-the-art algorithms in experiments.
  arXiv  Detail & Related papers  (2020-02-22T01:03:33Z)

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.