Average-case quantum query complexity

DOI10.1007/3-540-46541-3_11MaRDI QIDQ4501528zbMATH OpenFDO

Authors Andris Ambainis, Ronald de Wolf

Publication date 4 September 2000

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

quantum query complexitiestotal Boolean functions

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum computation (81P68)

Recommendations

• Average-case quantum query complexity
• 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

(13)

• Complexity measures and decision tree complexity: a survey.
• Almost-everywhere superiority for quantum polynomial time
• The quantum black-box complexity of majority
• Average case quantum lower bounds for computing the Boolean mean
• Beyond quadratic speedups in quantum attacks on symmetric schemes
• Quantum algorithms for variants of average-case lattice problems via filtering
• Average-case quantum query complexity
• The quantum query complexity of approximating the median and related statistics
• Quantum Queries on Permutations with a Promise
• Quantum Algorithms for Classical Probability Distributions
• Understanding quantum algorithms via query complexity
• Almost all decision trees do not allow significant quantum speed-up
• Quantum queries on permutations

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 Q4501528)