2026-07-22T18:45:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20681 2024-08-26T09:43:29Z ddc:004 open_access

A Direct Reduction from the Polynomial to the Adversary Method Belovs, Aleksandrs Polynomials Quantum Adversary Bound 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aleksandrs Belovs 2024 Is Part Of LIPIcs, Volume 310, 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TQC.2024.11 urn:nbn:de:0030-drops-206814 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2024.11 eng https://creativecommons.org/licenses/by/4.0/legalcode