A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs

DOI10.1007/S00453-007-9022-9zbMATH Open1191.68314arXivquant-ph/0511200OpenAlexW2068911609MaRDI QIDQ835643FDOQ835643

Andris Ambainis, Ronald de Wolf, Robert Špalek

Publication date: 31 August 2009

Published in: Algorithmica (Search for Journal in Brave)

Abstract: We give a new version of the adversary method for proving lower bounds on quantum query algorithms. The new method is based on analyzing the eigenspace structure of the problem at hand. We use it to prove a new and optimal strong direct product theorem for 2-sided error quantum algorithms computing k independent instances of a symmetric Boolean function: if the algorithm uses significantly less than k times the number of queries needed for one instance of the function, then its success probability is exponentially small in k. We also use the polynomial method to prove a direct product theorem for 1-sided error algorithms for k threshold functions with a stronger bound on the success probability. Finally, we present a quantum algorithm for evaluating solutions to systems of linear inequalities, and use our direct product theorems to show that the time-space tradeoff of this algorithm is close to optimal.

Full work available at URL: https://arxiv.org/abs/quant-ph/0511200

zbMATH Keywords

quantum algorithmsquantum computingBoolean functionstime-space tradeoffsquantum lower bounds

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum complexity of testing group commutativity
• Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer
• Quantum verification of matrix products
• On the Power of Quantum Computation
• Quantum Complexity Theory
• Quantum Algorithms for the Triangle Problem
• Quantum Walk Algorithm for Element Distinctness
• Rapid solution of problems by quantum computation
• On the degree of Boolean functions as real polynomials
• Quantum communication complexity of symmetric predicates
• Complexity measures and decision tree complexity: a survey.
• Quantum lower bounds for the collision and the element distinctness problems
• Quantum lower bounds by polynomials
• Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
• Polynomial degree vs. quantum query complexity
• Quantum lower bounds by quantum arguments
• The Growth of Polynomials Bounded at Equally Spaced Points
• Complexity limitations on quantum computation
• Limitations of Quantum Advice and One-Way Communication
• On the power of Ambainis lower bounds
• Quantum complexities of ordered searching, sorting, and element distinctness

Cited In (6)

• Optimal direct sum results for deterministic and randomized decision tree complexity
• Evaluation of exact quantum query complexities by semidefinite programming
• The NISQ complexity of collision finding
• A direct product theorem for two-party bounded-round public-coin communication complexity
• A strong direct product theorem for quantum query complexity
• Improved direct product theorems for randomized query complexity

This page was built for publication: A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q835643)