Anticipation in constructing and interrogating Natural Information Systems: from Classical through Nano to Quantum Computing

B. Nick Rossiter, Informatics, Northumbria University, Newcastle upon Tyne, UK, NE1 8ST, nick.rossiter@unn.ac.uk

M. A. Heather, Sutherland Building,
Northumbria University, NE1 8ST, m.heather@unn.ac.uk

**Keywords:** quantum databases, natural
computing, nano-computing, search
algorithms.

Information
systems anticipate the real world. Databases store, organise and search
collections of real-world data. The conceptual organisation of data according
to its inherent logical structure as a database was early recognised in
computing as an efficient method for the storage and retrieval of information. In terms of anticipatory systems,
information systems as databases constructed using classical methods are weak
anticipatory. This is because of the reductionism and normalisation needed to
operate databases on the familiar but idealised machines with von Neumann architectures
consisting of fixed instructions between bit cells. The new developing
areas are quantum computation, exploiting quantum mechanics principles in
physics, nanoscale chemistry, bio- and molecular-computing processing as in
genetics [1]. Natural computing is real-world
processing and does not rely on any model. Data can be input neat without any
reductionist pre-processing. The
corresponding information system or database using natural computing should therefore
be strong anticipatory.

Databases
have traditionally employed the multilevel ANSI/SPARC architecture. Three
layers and the mappings between them are typically defined by the internal
schema addressing the layout of data on disk, the conceptual schema describing
the data in terms of types and the external schema describing views derived for
end-users from the conceptual schema. The mappings between schemas are algebraic
or calculus expressions. Relationships are often performed in a separate
process such as Entity-Relationship Modelling or Unified Modelling. Normalisation
is needed to verify schema design, particularly to relate key and non-key
attributes. The levels, mappings and relationships all have to be integrated in
a consistent database design.

Formally a
database design is a topos and representable as a Dolittle diagram subsuming
the pullback/pushout relationships as:

Here f* is
essentially an examination and re-indexing functor. It organises the data into a
key for storage and applies a query for interrogation of the database. In ANSI/SPARC it puts together a key by
concatenation as in the relational model. For retrieval f* looks up information
by inspecting the key. In quantum theory the key is entanglement, in genetics
it is a DNA strand. In terms of the Dolittle diagram therefore f* is the same
operation in classical and natural computation. What then corresponds to the
database schema in natural computing?

There is a
need to re-examine the various interpretations found in quantum theory to build
an operational system. The Dolittle diagram relates binary categorial limits
(X) and colimits (+) for types and includes Heyting implication in intuitionistic
logic. The pullback functor (f*) looks for a particular sub-limit to represent
a relationship, thus emulating the join operation of databases (*). Other
arrows represent projection Õ, existential $ and
universal " quantification and at a higher
level even originality and style with respectively the unit h and
counit e of adjunction. The Dolittle diagram is the universal relation with
all possible relationships in parallel [3,4].

Recently
Grover [2] has developed the idea of using quantum algorithms for faster
searching of databases and Selinger [5] has produced a collection of operations
at such a level that they could form the basis of a quantum programming
language. Both offer potential for the development of quantum databases.
However, databases in general require this conceptual level for the
representation, querying and updating of data. The present approach is not yet
at the f* conceptual level but relies on low-level operations analogous to
classical methods like the CNOT gate (controlled NOT gate) where two input qubits, control and target, are
xor'd and stored in a target qubit *B *+
*A*. As a kind of f*, Grover
makes use of the 'oracle', treated as a black box and used for collapsing the
wave function, that is to determine when a solution has been derived. However, this
is to treat the oracle as a local set-theoretic module lacking the non-locality
properties required of quantum computation.

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

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

[3] Heather, M A, & Rossiter, B N, Locality, Weak or
Strong Anticipation and Quantum Computing I. Non-locality in Quantum Theory,
International Journal Computing Anticipatory Systems **13** 307-326 (2002).

[4] Heather, M A, & Rossiter, B N, Locality, Weak or
Strong Anticipation and Quantum Computing. II. Constructivism with Category
Theory, International Journal Computing Anticipatory Systems **13** 327-339 (2002).

[5]
Selinger, P, Towards a Quantum Programming Language, 42pp, http://quasar.mathstat.uottawa.ca/~selinger/papers.html#qpl
(2002).