The Quantum Black-Box Complexity of Majority |
| |
| Authors: | Hayes Kutin and van Melkebeek |
| |
| Affiliation: | (1) Department of Mathematics, University of Chicago, 5734 S. University Avenue, Chicago, IL 60637, USA. hayest@math.uchicago.edu., US;(2) Department of Computer Science, University of Chicago, 1100 E. 58th Street, Chicago, IL 60637, USA. kutin@cs.uchicago.edu., US;(3) Computer Sciences Department, University of Wisconsin, 1210 W. Dayton Street, Madison, WI 53706, USA. dieter@cs.wisc.edu., US |
| |
| Abstract: |
Abstract. We describe a quantum black-box network computing the majority of N bits with zero-sided error ɛ using only queries: the algorithm returns the correct answer with probability at least 1 - ɛ , 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 2/3N . We provide a nearly matching lower bound of 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 . |
| |
| Keywords: | , Majority function, Quantum computing, Query complexity, Las Vegas algorithms, |
| 本文献已被 SpringerLink 等数据库收录！ |
|
