Average case quantum lower bounds for computing the Boolean mean

DOI10.1016/J.JCO.2003.08.005MaRDI QIDQ1888378zbMATH OpenOpenAlexFDO

Authors A. Papageorgiou

Publication date 23 November 2004

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/0311007

zbMATH Keywords

quantum algorithms

Mathematics Subject Classification ID

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

Abstract: We study the average case approximation of the Boolean mean by quantum algorithms. We prove general query lower bounds for classes of probability measures on the set of inputs. We pay special attention to two probabilities, where we show specific query and error lower bounds and the algorithms that achieve them. We also study the worst expected error and the average expected error of quantum algorithms and show the respective query lower bounds. Our results extend the optimality of the algorithm of Brassard et al.

Recommendations

• Sharp error bounds on quantum Boolean summation in various settings
• scientific article; zbMATH DE number 1500513
• Average-case quantum query complexity
• scientific article; zbMATH DE number 2051219
• Quantum lower bounds by polynomials

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 46318 (Why is no real title available?)
• scientific article; zbMATH DE number 2051219 (Why is no real title available?)
• scientific article; zbMATH DE number 2103524 (Why is no real title available?)
• Quantum summation with an application to integration.
• The quantum query complexity of approximating the median and related statistics

Cited in

(4)

• Sharp error bounds on quantum Boolean summation in various settings
• Average-case quantum query complexity
• The quantum setting with randomized queries for continuous problems
• scientific article; zbMATH DE number 2051219 (Why is no real title available?)

This page was built for publication: Average case quantum lower bounds for computing the Boolean mean

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