Polynomial degree vs. quantum query complexity
From MaRDI portal
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; zbMATH DE number 5899233
- 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
Cites work
- A lower bound on the quantum query complexity of read-once functions
- Automata, Languages and Programming
- Automata, Languages and Programming
- Complexity measures and decision tree complexity: a survey.
- scientific article; zbMATH DE number 5899233 (Why is no real title available?)
- scientific article; zbMATH DE number 1256737 (Why is no real title available?)
- scientific article; zbMATH DE number 2038718 (Why is no real title available?)
- scientific article; zbMATH DE number 1775389 (Why is no real title available?)
- scientific article; zbMATH DE number 3258269 (Why is no real title available?)
- Lower bounds for local search by quantum arguments
- Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments
- Lower bounds on probabilistic linear decision trees
- On rank vs. communication complexity
- On the degree of Boolean functions as real polynomials
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum Algorithms for Element Distinctness
- Quantum algorithms for the triangle problem
- Quantum communication complexity of symmetric predicates
- Quantum complexities of ordered searching, sorting, and element distinctness
- Quantum lower bound for the collision problem with small range
- Quantum lower bounds by polynomials
- Quantum lower bounds by quantum arguments
- Quantum lower bounds for the collision and the element distinctness problems
- Strengths and Weaknesses of Quantum Computing
- The quantum query complexity of approximating the median and related statistics
Cited in
(32)- Nonadaptive quantum query complexity
- Evaluation of exact quantum query complexities by semidefinite programming
- Quantum algorithm for shortest path search in directed acyclic graph
- Superlinear advantage for exact quantum algorithms
- Ultrametric algorithms and automata
- scientific article; zbMATH DE number 5899233 (Why is no real title available?)
- The polynomial degree of recursive Fourier sampling
- On fractional block sensitivity
- Span-program-based quantum algorithm for evaluating unbalanced formulas
- A strong direct product theorem for quantum query complexity
- Forrelation: a problem that optimally separates quantum from classical computing
- Quantum query algorithms are completely bounded forms
- Low-sensitivity functions from unambiguous certificates
- How low can approximate degree and quantum query complexity be for total Boolean functions?
- Quantum query algorithms are completely bounded forms
- Approximate Degree in Classical and Quantum Computing
- Quantum distinguishing complexity, zero-error algorithms, and statistical zero knowledge
- New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity
- Exploring the limits of subadditive approaches: parallels between optimization and complexity theory
- Algorithmic Polynomials
- The polynomial method strikes back: tight quantum query bounds via dual polynomials
- Breaking the rectangle bound barrier against formula size lower bounds
- Quantum and classical query complexities of local search are polynomially related
- scientific article; zbMATH DE number 7716603 (Why is no real title available?)
- Quantum lower bounds by sample-to-query lifting
- Quantum counterfeit coin problems
- Sensitivity conjecture and signed hypercubes
- Quantum sabotage complexity
- 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
- Adversary lower bounds for nonadaptive quantum algorithms
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)
