Polynomial degree vs. quantum query complexity
From MaRDI portal
Publication:2490260
DOI10.1016/J.JCSS.2005.06.006zbMATH Open1095.68034OpenAlexW2126323053MaRDI QIDQ2490260FDOQ2490260
Authors: Andris Ambainis 
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
Recommendations
- Polynomials, quantum query complexity, and Grothendieck's inequality
- The quantum query complexity of learning multilinear polynomials
- BQP and the polynomial hierarchy
- The polynomial method strikes back: tight quantum query bounds via dual polynomials
- The polynomial method strikes back: tight quantum query bounds via dual polynomials
- scientific article
- Complexity and polynomially solvable special cases of QUBO
- On exact quantum query complexity
- On the quantum complexity of evaluating the Tutte polynomial
- Quantum and classical query complexities of local search are polynomially related
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68)
Cites Work
- The quantum query complexity of approximating the median and related statistics
- Title not available (Why is that?)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Title not available (Why is that?)
- Strengths and Weaknesses of Quantum Computing
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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 lower bounds by quantum arguments
- On rank vs. communication complexity
- Lower bounds for local search by quantum arguments
- Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments
- Quantum complexities of ordered searching, sorting, and element distinctness
- A lower bound on the quantum query complexity of read-once functions
- Title not available (Why is that?)
- Automata, Languages and Programming
- Quantum algorithms for the triangle problem
- Lower bounds on probabilistic linear decision trees
- Quantum Algorithms for Element Distinctness
- Automata, Languages and Programming
- Quantum lower bound for the collision problem with small range
Cited In (29)
- On fractional block sensitivity
- Algorithmic Polynomials
- Quantum and classical query complexities of local search are polynomially related
- On the black-box complexity of Sperner's Lemma
- Ultrametric algorithms and automata
- Title not available (Why is that?)
- Adversary lower bounds for nonadaptive quantum algorithms
- Quantum counterfeit coin problems
- On the quantum query complexity of local search in two and three dimensions
- Evaluation of exact quantum query complexities by semidefinite programming
- Forrelation: a problem that optimally separates quantum from classical computing
- Low-sensitivity functions from unambiguous certificates
- Quantum query algorithms are completely bounded forms
- Nonadaptive quantum query complexity
- Title not available (Why is that?)
- The polynomial method strikes back: tight quantum query bounds via dual polynomials
- A strong direct product theorem for quantum query complexity
- New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity
- Superlinear advantage for exact quantum algorithms
- How low can approximate degree and quantum query complexity be for total Boolean functions?
- Breaking the rectangle bound barrier against formula size lower bounds
- Quantum query algorithms are completely bounded forms
- Exploring the limits of subadditive approaches: parallels between optimization and complexity theory
- Quantum distinguishing complexity, zero-error algorithms, and statistical zero knowledge
- Span-program-based quantum algorithm for evaluating unbalanced formulas
- A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs
- Approximate Degree in Classical and Quantum Computing
- The polynomial degree of recursive Fourier sampling
- Quantum algorithm for shortest path search in directed acyclic graph
This page was built for publication: Polynomial degree vs. quantum query complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2490260)
