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^{2} steps rather than (n*2)^{n} 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).