Polynomial degree vs. quantum query complexity
From MaRDI portal
Publication:2490260
DOI10.1016/j.jcss.2005.06.006zbMath1095.68034OpenAlexW2126323053MaRDI QIDQ2490260
Publication date: 28 April 2006
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: http://cds.cern.ch/record/615418
Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs ⋮ On the quantum query complexity of local search in two and three dimensions ⋮ On the black-box complexity of Sperner's Lemma ⋮ Low-Sensitivity Functions from Unambiguous Certificates. ⋮ Span-Program-Based Quantum Algorithm for Evaluating Unbalanced Formulas ⋮ Approximate Degree in Classical and Quantum Computing ⋮ A strong direct product theorem for quantum query complexity ⋮ Forrelation: A Problem That Optimally Separates Quantum from Classical Computing ⋮ Nonadaptive quantum query complexity ⋮ Ultrametric Algorithms and Automata ⋮ Unnamed Item ⋮ Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory ⋮ Quantum Query Algorithms are Completely Bounded Forms. ⋮ Algorithmic Polynomials ⋮ Quantum Query Algorithms Are Completely Bounded Forms ⋮ How low can approximate degree and quantum query complexity be for total Boolean functions? ⋮ Quantum and classical query complexities of local search are polynomially related ⋮ BREAKING THE RECTANGLE BOUND BARRIER AGAINST FORMULA SIZE LOWER BOUNDS ⋮ Adversary lower bounds for nonadaptive quantum algorithms ⋮ Quantum counterfeit coin problems ⋮ Unnamed Item ⋮ Superlinear Advantage for Exact Quantum Algorithms ⋮ Unnamed Item ⋮ New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity ⋮ Quantum algorithm for shortest path search in directed acyclic graph ⋮ Unnamed Item ⋮ 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
- Lower bounds on probabilistic linear decision trees
- 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
- A lower bound on the quantum query complexity of read-once functions
- On rank vs. communication complexity
- The quantum query complexity of approximating the median and related statistics
- Quantum lower bounds for the collision and the element distinctness problems
- Lower bounds for local search by quantum arguments
- Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Strengths and Weaknesses of Quantum Computing
- Quantum communication complexity of symmetric predicates
- Quantum Algorithms for Element Distinctness
- Quantum lower bounds by polynomials
- Automata, Languages and Programming
- Automata, Languages and Programming
- Quantum lower bounds by quantum arguments
