A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs
From MaRDI portal
(Redirected from Publication:835643)
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.
Recommendations
- A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs
- A new quantum lower bound method, with an application to a strong direct product theorem for quantum search
- Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
- Quantum lower bounds by quantum arguments
- Quantum lower bounds by quantum arguments
Cites work
- scientific article; zbMATH DE number 1579275 (Why is no real title available?)
- scientific article; zbMATH DE number 5899272 (Why is no real title available?)
- scientific article; zbMATH DE number 5485488 (Why is no real title available?)
- scientific article; zbMATH DE number 48688 (Why is no real title available?)
- scientific article; zbMATH DE number 1256737 (Why is no real title available?)
- scientific article; zbMATH DE number 718142 (Why is no real title available?)
- scientific article; zbMATH DE number 2038718 (Why is no real title available?)
- scientific article; zbMATH DE number 2103524 (Why is no real title available?)
- A new quantum lower bound method, with an application to a strong direct product theorem for quantum search
- Any AND-OR formula of size \(N\) can be evaluated in time \(N^{1/2+o(1)}\) on a quantum computer
- Complexity limitations on quantum computation
- Complexity measures and decision tree complexity: a survey.
- Limitations of Quantum Advice and One-Way Communication
- On the Power of Quantum Computation
- On the degree of Boolean functions as real polynomials
- On the power of Ambainis lower bounds
- Polynomial degree vs. quantum query complexity
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum Algorithms for the Triangle Problem
- Quantum Complexity Theory
- Quantum Walk Algorithm for Element Distinctness
- Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
- Quantum communication complexity of symmetric predicates
- Quantum complexities of ordered searching, sorting, and element distinctness
- Quantum complexity of testing group commutativity
- Quantum lower bounds by polynomials
- Quantum lower bounds by quantum arguments
- Quantum lower bounds for the collision and the element distinctness problems
- Quantum verification of matrix products
- Rapid solution of problems by quantum computation
- The Growth of Polynomials Bounded at Equally Spaced Points
Cited in
(10)- A direct product theorem for two-party bounded-round public-coin communication complexity
- A strong direct product theorem for quantum query complexity
- Optimal direct sum results for deterministic and randomized decision tree complexity
- Quantum lower bounds by quantum arguments
- Improved direct product theorems for randomized query complexity
- The NISQ complexity of collision finding
- A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs
- Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
- A new quantum lower bound method, with an application to a strong direct product theorem for quantum search
- Evaluation of exact quantum query complexities by semidefinite programming
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)
