Quantum Boolean Summation with Repetitions in the Worst-Average Setting

2003/11/06 by Stefan Heinrich, Marek Kwas, Heinrich, Stefan +4
Computer Science · Mathematics · Physics and Astronomy · #Boolean function #Discrete mathematics #FOS: Physical sciences #Function (biology) #Machine Learning and Algorithms #Mathematics #Norm (philosophy) #Optimization and Search Problems #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Quantum mechanics #quant-ph

paper · pdf · doi:10.48550/arxiv.quant-ph/0311036

16 pages

arxiv created 2003/11/06 · openalex publication_date 2003/11/06 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

We study the quantum summation QS algorithm of Brassard, Hoyer, Mosca and Tapp, which approximates the arithmetic mean of a Boolean function defined on N elements. We present sharp error bounds of the QS algorithm in the worst-average setting with the average performance measured in the L_q norm, q ∈ [1,∞]. We prove that the QS algorithm with M quantum queries, M

Related

• Sharp Error Bounds on Quantum Boolean Summation in Various Settings
• Average case quantum lower bounds for computing the boolean mean
• Quantum Non-Identical Mean Estimation: Efficient Algorithms and Fundamental Limits
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems
• On a Problem in Quantum Summation