Unbounded-error quantum query complexity

DOI10.1016/J.TCS.2011.04.043MaRDI QIDQ638526zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Ashley Montanaro, Harumichi Nishimura, Rudy Raymond

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

zbMATH Keywords

query complexityquantum computingcommunication complexity

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Unbounded-Error Quantum Query Complexity
• Unbounded-Error Classical and Quantum Communication Complexity
• Unbounded-Error One-Way Classical and Quantum Communication Complexity
• Optimal quantum query bounds for almost all Boolean functions
• On exact quantum query complexity

Cites work

• scientific article; zbMATH DE number 46318 (Why is no real title available?)
• scientific article; zbMATH DE number 1775389 (Why is no real title available?)
• scientific article; zbMATH DE number 2086394 (Why is no real title available?)
• A Comparison of Uniform Approximations on an Interval and a Finite Subset Thereof
• A linear lower bound on the unbounded error probabilistic communication complexity.
• A note on quantum black-box complexity of almost all Boolean functions
• Complexity measures and decision tree complexity: a survey.
• Extremal properties of polynomial threshold functions
• Halfspace matrices
• Lower Bounds for Quantum Communication Complexity
• Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables
• Nondeterministic Quantum Query and Communication Complexities
• On the degree of Boolean functions as real polynomials
• On the tightness of the Buhrman-Cleve-Wigderson simulation
• Perceptrons, PP, and the polynomial hierarchy
• Probabilistic communication complexity
• Quantum Complexity Theory
• Quantum Weakly Nondeterministic Communication Complexity
• Quantum communication complexity of symmetric predicates
• Quantum lower bounds by polynomials
• Quantum search of spatial regions
• Relations between communication complexity classes
• Schwankung von Polynomen zwischen Gitterpunkten. (Oscillations of polynomials between lattice points)
• The expressive power of voting polynomials
• The probabilistic method
• Unbounded-Error Classical and Quantum Communication Complexity
• Unbounded-Error One-Way Classical and Quantum Communication Complexity

Cited in

(14)

• Unbounded-Error Quantum Query Complexity
• Unbounded-Error Classical and Quantum Communication Complexity
• Quantum query algorithms are completely bounded forms
• scientific article; zbMATH DE number 2086398 (Why is no real title available?)
• scientific article; zbMATH DE number 7561760 (Why is no real title available?)
• Quantum query algorithms are completely bounded forms
• Quantum distinguishing complexity, zero-error algorithms, and statistical zero knowledge
• Unbounded-Error One-Way Classical and Quantum Communication Complexity
• Weak parity
• scientific article; zbMATH DE number 6667586 (Why is no real title available?)
• scientific article; zbMATH DE number 7716601 (Why is no real title available?)
• Union bound for quantum information processing
• Unbounded-error quantum computation with small space bounds
• (Un)decidable Problems about Reachability of Quantum Systems

This page was built for publication: Unbounded-error quantum query complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q638526)