Database Searching in Quantum and Natural Computing

M.A. Heather, University of Northumbria at Newcastle NE1 8ST m.heather@unn.ac.uk

B.N. Rossiter, School of Computing and Mathematics, University of Northumbria at Newcastle NE1 8ST, UK Tele: ++44 191 227 4662 nick.rossiter@unn.ac.uk

Keywords: natural computing, quantum databases, search algorithms.

Databases store, organise and search collections of real-world data. The new developing areas of quantum computation, bio- and molecular-computing exploit real-world processing in contrast to traditional computers which are effectively examples of the universal Turing Machine [Heather and Rossiter, 2002]. Because of the gap between the real-world and its simulation, database constructors continually wrestle with problems of representing the inherent structure of real-world data. They have to rely on some theoretical schema in the form of separate metadata which is not 1:1 with the internal structure of the data. Natural computing on the other hand does not rely on any model. Data can be input neat without any reductionist pre-processing. We are therefor entering a new era in databases which is very appropriate for applications of current interest like biological and medical data, environmental and geophysical data, image and moving picture data, etc. Already molecular computers have been constructed [Adleman, 1996] although there is still a tendency to resort to models like the sticker-based model [Roweis et al, 1998].

Nevertheless most progress to date seems to be with quantum information systems. The concept of the quantum computer was realised during the last two decades of the twentieth century and drew heavily on standard quantum theory and computational theory of the time to postulate an analogous Church-Turing hypothesis. However realising the concept of a quantum computer is not the same as realising a quantum computer. The literature on the quantum computer is mainly bottom-up replicating the path of the classical computer in the last half-century. The qubit corresponds to the bit and quantum logic to propositional logic; quantum algorithms like those of Shor [1996], Grover [1996] and Deutsch-Jozsa [1992] are alternatives to NP methods [Nielsen and Chuang, 2000].

Maurer et al [2001] have used conventional computers to calculate how quantum computers would cope with a well-chosen portfolio of programs for solving NP-complete problems. They found that quantum parallelism could at least double the speed or be up to ten times faster with a single program. In another study by Chuang [1998] employing nuclear magnetic resonance to carbon-13 in chloroform molecules dissolved in acetone, it was estimated that a quantum computer on average required one evaluation for a function compared to 2.25 for a classical computer. Deutsch and Jozsa [1992] applied a quantum algorithm to determine whether an unknown mathematical function is constant or balanced (for instance as many 1s as 0s). Shor and Deutsch-Jozsa algorithms are a quantum version of the fast Fourier transform requiring only n² steps rather than (n*2)ⁿ steps.

In databases Grover's transform method of 1996 flips a matrix in such a way that the odd record out (the one sought) is identified through amplitude amplification. The method of Grover has been extended for multiple occurrences but the number of occurrences needs to be known in advance [Boyer et al, 1998]. An ordinary computer can be programmed to model the operation of a quantum computer with Grover's algorithms [Grover, 2000] but only as a weak classical model of quantum processing and therefore very inefficiently. As pointed out in the review by Aharonov [1998] the Grover iteration can be understood as a product of two reflections. In this way Bhattacharya et al [2002] have implemented a quantum search algorithm showing that classical waves can search a N-item database just as efficiently. It is claimed that although the lack of quantum entanglement limits the database size, entanglement is neither necessary for the algorithm itself, nor for its efficiency.

The full significance of quantum theory for the construction of future information systems and the role of quantum algorithms in databases needs to be fully addressed. There is the question of the structure inherent in information. A database scheme utilises this inherent structure in the construction and storage of the data. Tree constructions with lexicographical ordering may typically give the order of log N comparisons. So some elementary structuring (B-trees) can give faster conventional systems [Comer, 1979] than by the use of Grover's algorithm. B-tree searching enables one record in one million to be retrieved in five disk accesses.

If quantum algorithms are to be realisable on physical machines, we need to re-examine the various interpretations of the physics to be found in quantum theory to check that they can be converted into constructible systems. In a recent experimental realization of quantum games on a nuclear magnetic resonance quantum computer, Jiangfeng et al [2002] have generalised the quantum prisoner's dilemma by the use of non-maximally entangled states. It is still to be shown whether the published algorithms really exhibit the non-local operability of true quantum processing.

References

[Adleman, 1996] Adleman, L, On constructing a molecular computer, DNA based computers, Lipton, R, and Baum, E, (edd), DIMACS, American Mathematical Society 1-21 (1996).

[Aharonov, 1998] Aharonov, D, Quantum computation -- a review, in: Stauffer, D, (ed), Ann Rev Computational Physics VI World Scientific, Singapore (1998).

[Bhattacharya et al, 2002] Bhattacharya, N, van den Heuvell, H B, and Spreeuw, R J C, Implementation of quantum search algorithm using classical Fourier optics, Phys Rev Lett 88 137901 (2002).

[Boyer et al, 1998] Boyer, M, Brassard, G, Hyer, P, and Tapp, A, Tight bounds on quantum searching, Fortsch Phys Prog Phys 46(4-5) 493-505 (1998).

[Chuang et al, 1998] Chuang, I L, Gershenfeld, N, and Kubinec, M, Experimental implementation of fast quantum searching, Phys Rev Lett 18 3408-3411 (1998).

[Comer, 1979] Comer, D, The ubiquitous B-tree, ACM Computing Surveys 11 121-137 (1979).

[Deutsch and Jozsa, 1992] Deutsch, D, and Jozsa, R, Rapid solution of problems by quantum computation, Proc Roy Soc Lond A 439 553-558 (1992).

[Grover, 1996] Grover, L K, A fast quantum mechanical algorithm for database search, Proc 28th Ann ACM Symp Theory of Computing 212-219 (1996).

[Grover, 2000] Grover, L K, Rapid sampling through quantum computing, Proc 32nd Ann ACM Symp Theory of Computing 618-626 (2000).

[Heather and Rossiter, 2002] Heather, M A, and Rossiter, B N, The anticipatory and systemic adjointness of E-science computation on the grid, Proc Amer Inst Physics (in press).

[Jiangfeng et al, 2002] Jiangfeng, D, Hui, L, Xiaodong, X, Mingjun, S, Jihui, W, Xianyi, Z, and Rongdian, H, Experimental realisation of quantum games, Phys Rev Lett 88 137902 (2002).

[Maurer et al, 2001] Maurer, S M, Hogg, T, and Huberman, B A, Portfolios of quantum algorithms, Phys Rev Lett 87 257901 (2001).

[Nielsen and Chuang, 2000] Nielsen, M A, and Chuang, I L, Quantum Computation and Quantum Information, Cambridge (2000).

[Roweis et al, 1998] Roweis, S, Winfree, E, Burgoyne, R, Chelyapov, N V, Goodman, M F, Adleman, L M, and Rothemund, P W K, A sticker-based model for DNA computation, J Comp Biol 5(4) 615-629 (1998).

[Shor, 1996] Shor, P, Fault-tolerant quantum computation, Proc. 37th Ann Symp Found Com Sci, IEEE (1996).