×

Constant-time solution to database searching by NMR ensemble computing. (English) Zbl 1108.81011

Summary: 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(^{\cdot})\) 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(^{\cdot})\) 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 \leq 2^{30}\) according to current NMR spectrometer technology.

MSC:

81P68 Quantum computation
68P15 Database theory
Full Text: DOI

References:

[1] Brüschweiler, Phys. Rev. Lett. 85(22) pp 4815– (2000)
[2] Cory, Proc. Natl. Acad. Sci. 94 pp 1634– (1997)
[3] D’Helon, J. Phys. A, Math. Gen. 35 (2002)
[4] A Fast Quantum Mechanical Algorithm for Database Search, Proc. 28th Annual ACM Symposium on the Theory of Computing, pp. 212–219, 1996.
[5] Long, J. Chem. Phys 119 pp 8473– (2003)
[6] Mádi, J. Chem. Phys. 109 pp 10603– (1998)
[7] Protopopescu, J. Phys. A, Math. Gen. 36 (2003)
[8] Xiao, J. Chem. Phys. 117 pp 3310– (2002)
[9] Xiao, Phys. Rev. A 66 pp 052320– (2002)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.