A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs
From MaRDI portal
Publication:835643
DOI10.1007/S00453-007-9022-9zbMath1191.68314arXivquant-ph/0511200OpenAlexW2068911609MaRDI QIDQ835643
Andris Ambainis, Ronald de Wolf, Robert Špalek
Publication date: 31 August 2009
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/quant-ph/0511200
Nonnumerical algorithms (68W05) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68)
Related Items (4)
A direct product theorem for two-party bounded-round public-coin communication complexity ⋮ Optimal direct sum results for deterministic and randomized decision tree complexity ⋮ Improved direct product theorems for randomized query complexity ⋮ Evaluation of exact quantum query complexities by semidefinite programming
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the power of Ambainis lower bounds
- On the degree of Boolean functions as real polynomials
- Complexity measures and decision tree complexity: a survey.
- Quantum complexities of ordered searching, sorting, and element distinctness
- Complexity limitations on quantum computation
- Polynomial degree vs. quantum query complexity
- Quantum complexity of testing group commutativity
- Limitations of Quantum Advice and One-Way Communication
- Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer
- Quantum lower bounds for the collision and the element distinctness problems
- Quantum verification of matrix products
- The Growth of Polynomials Bounded at Equally Spaced Points
- Rapid solution of problems by quantum computation
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- On the Power of Quantum Computation
- Quantum Complexity Theory
- Quantum communication complexity of symmetric predicates
- Quantum Algorithms for the Triangle Problem
- Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
- Quantum lower bounds by polynomials
- Quantum Walk Algorithm for Element Distinctness
- Quantum lower bounds by quantum arguments
This page was built for publication: A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs
