On the quantum complexity of majority
| Author(s) : | Dieter Van Melkebeek Samuel Kutin Thomas P. Hayes, |
| Publisher : | N/A |
| Publication Date : | 1998 |
| ISSN : | N/A |
| Abstract : | We construct a quantum black-box algorithm that computes the majority of N bits exactly using N + 1 \Gamma w(N) queries, where w(N) denotes the number of ones in the binary expansion of N. We establish a matching lower bound in a generalized classical decision tree model in which the equivalent of our quantum algorithm is optimal. We also provide an exact quantum algorithm that almost surely makes no more than N, |