Unbounded-error quantum query complexity
From MaRDI portal
Publication:638526
DOI10.1016/j.tcs.2011.04.043zbMath1221.68091OpenAlexW2964304770WikidataQ58478291 ScholiaQ58478291MaRDI QIDQ638526
Harumichi Nishimura, Rudy Raymond, Ashley Montanaro
Publication date: 12 September 2011
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2011.04.043
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Quantum algorithms and complexity in the theory of computing (68Q12)
Related Items (3)
Quantum Query Algorithms are Completely Bounded Forms. ⋮ Quantum Query Algorithms Are Completely Bounded Forms ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables
- Probabilistic communication complexity
- Relations between communication complexity classes
- Halfspace matrices
- The expressive power of voting polynomials
- On the degree of Boolean functions as real polynomials
- Perceptrons, PP, and the polynomial hierarchy
- A note on quantum black-box complexity of almost all Boolean functions
- Complexity measures and decision tree complexity: a survey.
- A linear lower bound on the unbounded error probabilistic communication complexity.
- Schwankung von Polynomen zwischen Gitterpunkten. (Oscillations of polynomials between lattice points)
- Extremal properties of polynomial threshold functions
- On the Tightness of the Buhrman-Cleve-Wigderson Simulation
- Quantum Complexity Theory
- Quantum communication complexity of symmetric predicates
- Nondeterministic Quantum Query and Communication Complexities
- Unbounded-Error Classical and Quantum Communication Complexity
- Unbounded-Error One-Way Classical and Quantum Communication Complexity
- Quantum lower bounds by polynomials
- Lower Bounds for Quantum Communication Complexity
- A Comparison of Uniform Approximations on an Interval and a Finite Subset Thereof
- Quantum Weakly Nondeterministic Communication Complexity
This page was built for publication: Unbounded-error quantum query complexity
