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.
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.
Abstract Brüschweiler's Ensemble algorithm requires n = log N queries to discover the wanted object from the database of the size N. In this paper, we use a new oracle query function g(.) to improve Brüschweiler's algorithm such that only one query is needed for searching the single object. Our algorithm extends from one ancillary qubit to n ancillary qubits. We then construct the oracle query function g(.) satisfying g(x) = 0 for all input x, except for one, say x = z, where g(z) = z. We first prepare 2n qubits, including n qubits for representing the elements and n ancillary qubits for storing the result of the oracle query function. After one query, we obtain z by measuring these ancillary qubits. Our algorithm can efficiently discover the wanted object if N ≤ 230 according to current NMR spectrometer technology.
In this paper, we improve Bruschweiler's algorithm such that only one query is needed for searching the single object z from N=2^n unsorted elements. Our algorithm construct the new oracle query function g(.) satisfying g(x)=0 for all input x, except for one, say x=z, where g(z)=z. To store z, our algorithm extends from one ancillary qubit to n ancillary qubits. We then measure these ancillary qubits to discover z. We further use our ensemble search algorithm to attack classical public key cryptosystems. Given the ciphertext C=Ek(m, r) which is generated by the encryption function Ek(), a public key k, a message m, and a random number r, we can construct an oracle query function h(.) satisfying h(m', r')=0 if Ek(m', r')!=C and h(m', r')= (m', r') if Ek(m', r')=C. There is only one object, say (m, r), can be discovered in decryption of C. By preparing the input with all possible states of (m', r'), we can thus use our ensemble search algorithm to find the wanted object (m, r). Obviously, we break the classical public key cryptosystems under the ciphertext attack by performing the oracle query function only one time.
We consider the problem of finding one or more desired items out of an unsorted database. Patel has shown that if the database permits quantum queries, then mere digitization is sufficient for efficient search for one desired item. The algorithm, called factorized quantum search algorithm, presented by him can locate the desired item in an unsorted database using O(log4N) queries to factorized oracles. But the algorithm requires that all the property values must be distinct from each other. In this paper, we discuss how to make a database satisfy the requirements, and present a quantum search engine based on the algorithm. Our goal is achieved by introducing auxiliary files for the property values that are not distinct, and converting every complex query request into a sequence of calls to factorized quantum search algorithm. The query complexity of our algorithm is O(P∗Q∗M∗log4N), where P is the number of the potential simple query requests in the complex query request, Q is the maximum number of calls to the factorized quantum search algorithm of the simple queries, M is the number of the auxiliary files for the property on which our algorithm are searching for desired items. This implies that to manage an unsorted database on an actual quantum computer is possible and efficient.
The speedup of an unsorted database search has always been a challenging problem not only in classical computation but also in quantum computation. We propose a fetching algorithm for a Liouville space nuclear magnetic resonance (NMR) ensemble computing to fetch a marked item from an unsorted database directly. This algorithm achieves the absolute optimum in an unsorted database search problem: a single query. In fact, this algorithm also works well for fetching several unknown numbers of marked items. The computer simulation realization of the algorithm in a three-qubit homonuclear spin system is also presented. In addition, a compromised version of the algorithm, which reduces the demand on the structure of the molecules for the NMR experiment, is also devised.
The quantum search algorithm of Chen and Diao, which finds with certainty a single target item in an unsorted database, is modified so as to be capable of searching for an arbitrary specified number of target items. If the number of targets, nu_0, is a power of four, the new algorithm will with certainty find one of the targets in a database of n items using (1/2)(3(N/nu_0)^{log_base_4(3)}-1) \approx (1/2)(3(N/nu_0)^{0.7925}-1) oracle calls, where N is the smallest power of four greater than or equal to n. If nu_0 is not a power of four, the algorithm will, with a probability of at least one-half, find one of the targets using no more than (1/2)(9(N/nu)^{log_base_4(3)}-1) calls, where nu is the smallest power of four greater than or equal to nu_0.
IntroductionFor a search problem associated with a unsorted database, the remarkable Grover's quantum algorithm (1) provides a quadratic speedup over its classical counterpart.The search problem can be described as follows: for a given function f , there exists one unknown element in the set {0, 1, ..., N -1} that satisfies f (x)=-1, say x = τ, whereas the other N -1o n e sg i v e f (x)=1.How many times of evaluations of f are required to determine the element τ for f (τ)=-1?Through a conventional algorithm, one needs O(N) trials to achieve this aim.How about the utility of quantum algorithm for the search?For the scenario in the quantum world, the search problem can be rephrased in the quantum mechanical language: for a given unitary operator I τ , that is sometimes called the oracle operator, and a set of state vectors (orthonormal basis): s = {|0 , |1 , ..., |N -1 }, I τ |x = |x for all states in the set except I τ |x = -|x for x = τ.H owma n yqueriesofI τ are required to determine |τ ?By Grover's algorithm, one needs only O( √ N) quantum mechanical steps to find the marked state |τ out.It has been shown that Grover's algorithm is optimal since it needs minimal oracle calls to perform a quantum search (2).The quantum searching process will be briefly reviewed as follows.The first step of Grover's algorithm is to prepare a superposition state of all elements with uniform probability amplitude:Then apply the Grover kernel G = -I η I τ to |s ,w h er eI η is a unitary operator and contains no bias against the marked state.For large N,a f t e ra b o u tm = π √ N/4 repetitions of G operations, the probability to observe |τ is close to one, i.e., G m |s ∼ |τ .( 2 ) Since every single G involves one query of I τ ,onlyO( √ N) searching steps are required for a quantum search task.In what follows, we will first investigate on the general SU(2) formulation for the kernel of Grover's searching operator G.The discussions of quantum searching certainty, robustness, and the analog analogue version of the Grover's algorithm will be given afterwards.