Bounds on quantum ordered searching
| dc.creator | Hoyer, Peter | |
| dc.creator | Neerbek, Jan | |
| dc.date | 2000-09-08 | |
| dc.date | 2001-04-27 | |
| dc.date.accessioned | 2026-07-07T06:00:47Z | |
| dc.date.available | 2026-07-07T06:00:47Z | |
| dc.description | We prove that any exact quantum algorithm searching an ordered list of N elements requires more than \frac{1}π(\ln(N)-1) queries to the list. This improves upon the previously best known lower bound of {1/12}\log_2(N) - O(1). Our proof is based on a weighted all-pairs inner product argument, and it generalizes to bounded-error quantum algorithms. The currently best known upper bound for exact searching is roughly 0.526 \log_2(N). We give an exact quantum algorithm that uses \log_3(N) + O(1) queries, which is roughly 0.631 \log_2(N). The main principles in our algorithm are an quantum parallel use of the classical binary search algorithm and a method that allows basis states in superpositions to communicate. | |
| dc.description | This paper has been merged with another paper. See quant-ph/0102078. Except for this comment v2 is unchanged compared to v1. 12 pages, 1 figure | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0009032 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0009032 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/89065 | |
| dc.subject | Quantum Physics | |
| dc.title | Bounds on quantum ordered searching | |
| dc.type | text |