A lower bound on the quantum query complexity of read-once functions

DOI10.1016/j.jcss.2004.02.002zbMath1083.68045arXivquant-ph/0201007OpenAlexW1987152249WikidataQ62117306 ScholiaQ62117306MaRDI QIDQ1880783

Howard Barnum, Michael E. Saks

Publication date: 1 October 2004

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

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

zbMATH Keywords

Quantum query complexityLower boundsQuantum computationQuery complexityDecision tree complexityRead-once functions

Mathematics Subject Classification ID

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

Related Items

Span-Program-Based Quantum Algorithm for Evaluating Unbalanced Formulas ⋮ Quantum algorithm for lexicographically minimal string rotation ⋮ Quantum search with variable times ⋮ Polynomial degree vs. quantum query complexity ⋮ On the power of Ambainis lower bounds ⋮ Quantum Random Walks – New Method for Designing Quantum Algorithms ⋮ Quantum Algorithms for Evaluating Min-Max Trees

Cites Work

• Unnamed Item
• Unnamed Item
• On the degree of Boolean functions as real polynomials
• Complexity measures and decision tree complexity: a survey.
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• On the Power of Quantum Computation
• Strengths and Weaknesses of Quantum Computing
• Quantum lower bounds by quantum arguments