Improved quantum algorithms for the ordered search problem via semidefinite programming

Details Improved quantum algorithms for the ordered search problem via semidefinite programming Improved quantum algorithms for the ordered search problem via semidefinite programming

2006-08-21

arxiv.org/abs/quant-ph/0608161v1

Phys. Rev. A 75, 032335 (2007)

Physics

Quantum Physics

8 pages, 4 figures

Scientific paper

10.1103/PhysRevA.75.032335

One of the most basic computational problems is the task of finding a desired item in an ordered list of N items. While the best classical algorithm for this problem uses log_2 N queries to the list, a quantum computer can solve the problem using a constant factor fewer queries. However, the precise value of this constant is unknown. By characterizing a class of quantum query algorithms for ordered search in terms of a semidefinite program, we find new quantum algorithms for small instances of the ordered search problem. Extending these algorithms to arbitrarily large instances using recursion, we show that there is an exact quantum ordered search algorithm using 4 log_{605} N \approx 0.433 log_2 N queries, which improves upon the previously best known exact algorithm.

Affiliated with

Also associated with

No associations

Rating

Improved quantum algorithms for the ordered search problem via semidefinite programming does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Improved quantum algorithms for the ordered search problem via semidefinite programming, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved quantum algorithms for the ordered search problem via semidefinite programming will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-572270