Ensemble Algorithm for the Selection Problem by NMR Ensemble Quantum Computers

Details Ensemble Algorithm for the Selection Problem by NMR Ensemble Quantum Computers Ensemble Algorithm for the Selection Problem by NMR Ensemble Quantum Computers

2004-07-15

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

Physics

Quantum Physics

16 pages, 1 figure

Scientific paper

In this paper, we present an ensemble algorithm for selection problem to find the k-th smallest element in the unsorted database. We will search the k-th smallest element by using "divide-and-conquer" strategy. We first divide D, the domain of the database, into two parts, determine which of the two parts the object element sought belongs to, and then concentrate on that part. We repeat divide that part until object element is found. The determination of which part depends on the output of ensemble counting scheme, which outputs the number of assignments satisfying the value of the oracle query function is set to one. Our algorithm modifies the ensemble counting scheme by constructing a new oracle query function g_y(j). We set g_y(j) to one if the j-th element is less than or equal to y. At first, we set y to the middle value of D and perform the ensemble counting scheme with the oracle query function g_y(.) to compute the number C, the number of j satisfying g_y(j)=1. If C>k, the object element lies in the first half of D. If C<=k, then it must be in the second half of D. We recursively apply this method by adapting y until the object element is found. Our algorithm thus requires O(ln|D|) oracle queries for adequate measure accuracy to find the k-th smallest element, where |D| denotes the size of D.

Affiliated with

Also associated with

No associations

Rating

Ensemble Algorithm for the Selection Problem by NMR Ensemble Quantum Computers 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 Ensemble Algorithm for the Selection Problem by NMR Ensemble Quantum Computers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Ensemble Algorithm for the Selection Problem by NMR Ensemble Quantum Computers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-570809