The quantum black-box complexity of majority

DOI10.1007/S00453-002-0981-6MaRDI QIDQ1871636zbMATH OpenOpenAlexFDO

Authors Thomas P. Hayes, Samuel Kutin, Dieter Van Melkebeek

Publication date 4 May 2003

Published in Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

query complexitymajority functionquantum computingLas Vegas algorithms

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68)

Abstract: We describe a quantum black-box network computing the majority of N bits with zero-sided error eps using only 2N/3 + O(sqrt{N (log log N + log 1/eps)}) queries: the algorithm returns the correct answer with probability at least 1 - eps, and "I don't know" otherwise. Our algorithm is given as a randomized "XOR decision tree" for which the number of queries on any input is strongly concentrated around a value of at most 2N/3. We provide a nearly matching lower bound of 2N/3 - O(sqrt(N)) on the expected number of queries on a worst-case input in the randomized XOR decision tree model with zero-sided error o(1). Any classical randomized decision tree computing the majority on N bits with zero-sided error 1/2 has cost N.

Recommendations

• On randomized algorithms for the majority problem
• Quantum lower bounds by polynomials
• Randomized algorithms for the majority problem
• scientific article; zbMATH DE number 1500513
• Average-case quantum query complexity

Cited in

(9)

• Revisiting Deutsch-Jozsa algorithm
• Adaptive majority problems for restricted query graphs and for weighted sets
• Improved bounds for the randomized decision tree complexity of recursive majority
• On exact quantum query complexity
• Finding a majority ball with majority answers
• Almost all decision trees do not allow significant quantum speed-up
• Adaptive majority problems for restricted query graphs and for weighted sets
• Finding a non-minority ball with majority answers
• Post-quantum simulatable extraction with minimal assumptions: black-box and constant-round

This page was built for publication: The quantum black-box complexity of majority

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