On the Quantum Black-Box Complexity of Majority
| dc.creator | Hayes, Thomas | |
| dc.creator | Kutin, Samuel | |
| dc.creator | van Melkebeek, Dieter | |
| dc.date | 2001-09-20 | |
| dc.date | 2002-10-30 | |
| dc.date.accessioned | 2026-07-07T06:02:43Z | |
| dc.date.available | 2026-07-07T06:02:43Z | |
| dc.description | 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. | |
| dc.description | 22 pages, to appear in Algorithmica, v3: tail laws in appendix proved in a more elegant way than in the journal version | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0109101 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0109101 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/89712 | |
| dc.subject | Quantum Physics | |
| dc.title | On the Quantum Black-Box Complexity of Majority | |
| dc.type | text |