Average-case quantum query complexity

DOI10.1088/0305-4470/34/35/302MaRDI QIDQ2766189zbMATH OpenOpenAlexFDO

Authors Andris Ambainis, Ronald de Wolf

Publication date 27 January 2002

Published in Journal of Physics A: Mathematical and General (Search for Journal in Brave)

Full work available at URL https://ir.cwi.nl/pub/1112

zbMATH Keywords

Boolean functionsclassical and quantum

Mathematics Subject Classification ID

Quantum computation (81P68) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 1500513
• Average case quantum lower bounds for computing the Boolean mean
• Quantum lower bounds by polynomials
• Understanding quantum algorithms via query complexity
• Quantum Query Complexity of Boolean Functions with Small On-Sets

Cited in

(10)

• scientific article; zbMATH DE number 2086398 (Why is no real title available?)
• Quantum algorithm for lexicographically minimal string rotation
• Average case quantum lower bounds for computing the Boolean mean
• Quantum algorithms for variants of average-case lattice problems via filtering
• Almost all decision trees do not allow significant quantum speed-up
• The quantum query complexity of approximating the median and related statistics
• Average-case deterministic query complexity of Boolean functions with fixed weight
• The quantum black-box complexity of majority
• Quantum-walk speedup of backtracking algorithms
• Understanding quantum algorithms via query complexity

This page was built for publication: Average-case quantum query complexity

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