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.
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.
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.
A constant-time solution of the continuous global optimization problem (GOP) is obtained by using an ensemble algorithm. We show that under certain assumptions, the solution can be guaranteed by mapping the GOP onto a discrete unsorted search problem, whereupon Brüschweiler's ensemble search algorithm is applied. For adequate sensitivities of the measurement technique, the query complexity of the ensemble search algorithm depends linearly on the size of the function's domain. Advantages and limitations of an eventual NMR implementation are discussed.
Br\"uschweiler's database search in a spin Liouville space can be efficiently simulated on a conventional computer without error as long as the simulation cost of the internal circuit of an oracle function is polynomial, unlike the fact that in true NMR experiments, it suffers from an exponential decrease in the variation of a signal intensity. With the simulation method using the matrix-product-state proposed by Vidal [G. Vidal, Phys. Rev. Lett. 91, 147902 (2003)], we perform such a simulation. We also show the extensions of the algorithm without utilizing the J-coupling or DD-coupling splitting of frequency peaks in observation: searching can be completed with a single query in polynomial postoracle circuit complexities in an extension; multiple solutions of an oracle can be found in another extension whose query complexity is linear in the key length and in the number of solutions (this extension is to find all of marked keys). These extended algorithms are also simulated with the same simulation method.
An exponentially fast solution of the continuous Global Optimization Problem (GOP) is obtained by using an ensemble algorithm. We show that under certain assumptions, one can map the GOP onto a discrete unsorted search problem, whereupon Bruschweiler's ensemble search algorithm [Phys. Rev. Lett. 85 4815 (2000)] is applied. For adequate sensitivities of the measurement techniques, the query complexity of the ensemble search algorithm depends linearly - as opposed to exponentially - on the size of the function's domain. Opportunities and limitations of an eventual NMR implementation are discussed.
In recent years, quantum computing research has made big progress, which exploit quantum mechanical laws, such as interference, superposition and parallelism, to perform computing tasks. The most inducing thing is that the quantum computing can provide large rise to the speedup in quantum algorithm. Quantum computing can solve some problems, which are impossible or difficult for the classical computing. The problem of searching for a specific item in an unsorted database can be solved with certain quantum algorithm, for example, Grover quantum algorithm and Bruschweiler quantum algorithm. The former gives a quadratic speedup, and the latter gives an exponential speedup comparing with the corresponding classical algorithm. In Bruschweiler quantum searching algorithm, the data qubit and the read-out qubit (the ancilla qubit) are different qubits. We have studied Bruschweiler algorithm and proposed a modified version, in which no ancilla qubit is needed to reach exponential speedup in the searching, the data and the read-out qubit are the same qubits. The modified Bruschweiler algorithm can be easier to design and realize. We also demonstrate the modified Bruschweiler algorithm in a 3-qubit molecular system by Nuclear Magnetic Resonance (NMR) experiment.