publication . Preprint . 2000

Bounds on quantum ordered searching

Hoyer, Peter; Neerbek, Jan;
Open Access English
  • Published: 08 Sep 2000
We prove that any exact quantum algorithm searching an ordered list of N elements requires more than \frac{1}{\pi}(\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 all...
free text keywords: Quantum Physics
Download from

[1] Ambainis, A., “A better lower bound for quantum algorithms searching an ordered list”, Proc. of 40th FOCS, 1999, pp. 352-357. [OpenAIRE]

[2] Ambainis, A., “Quantum lower bounds by quantum arguments”, Proc. of 32nd STOC, 2000, pp. 636-643. [OpenAIRE]

[3] Beals, R., H. Buhrman, R. Cleve, M. Mosca and R. de Wolf, “Quantum lower bounds by polynomials”, Proc. of 39th FOCS, 1998, pp. 352-361.

[4] Bennett, C. H., E. Bernstein, G. Brassard and U. Vazirani, “Strengths and weaknesses of quantum computation”, SIAM J. Comp., 26:1510-1523, 1997.

[5] Berthiaume, A., “Quantum computation”. In Complexity Theory Retrospective II, chap. 2, pp. 23-50. Springer-Verlag, 1997.

[6] Buhrman, H. and R. de Wolf, “A lower bound for quantum search of an ordered list”, Inform. Process. Lett., 70:205-209, 1999. [OpenAIRE]

[7] Choi, M.-D., “Tricks or treats with the Hilbert matrix”, Amer. Math. Monthly, 90:301-312, 1983.

[8] Ettinger, M., Personal Communication, 1998-2000.

[9] Farhi, E., J. Goldstone, S. Gutmann and M. Sipser, “A limit on the speed of quantum computation for insertion into an ordered list”. quant-ph/9812057, December 1998. [OpenAIRE]

[10] Farhi, E., J. Goldstone, S. Gutmann and M. Sipser, “Invariant quantum algorithms for insertion into an ordered list”, quant-ph/9901059, January 1999. [OpenAIRE]

[11] Farhi, E., J. Goldstone, S. Gutmann and M. Sipser, “Upper bound for the number of functions that can be distinguished with k quantum queries”, Phys. Rev. A, 60:4331-4333, 1999. [OpenAIRE]

[12] Grover, L. K., “Quantum mechanics helps in searching for a needle in a haystack”, Phys. Rev. Lett. 79:325-328, 1997.

[13] Jozsa, R. and J. Schlienz, “Distinguishability of states and von Neumann entropy”, quant-ph/9911009, November 1999.

[14] Vazirani, U., “On the power of quantum computation”, Philos. Trans. Roy. Soc. London Ser. A, 356:1759-1768, 1998.

[15] Zalka, Ch., “Grover's quantum searching algorithm is optimal”, Phys. Rev. A, 60:2746-2751 (1999). [OpenAIRE]

Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue