troduced by Head, based on splicing (a combination of cut-and-paste operations achievable by enzymes), predates the experimental proof-of-principle of DNA computing by almost 10 years. Subsequently, studies on the computational power of such models proved that various subsets of bio-operations can achieve the computational power of a Turing machine, showing thus that molecular computers are in principle possible. ²⁷ Overall, molecular computing has created many novel theoretical questions, and has considerably enriched the theory of computation.

Quantum Computing is another paradigm that uses an alternative “ hardware” for performing computations. ¹⁹ Already in 1980 Benioff introduced simulations of classical Turing Machines on quantum mechanical systems. However the idea of a quantum computer that would run according to the laws of quantum physics and operate exponentially faster than a deterministic electronic computer to simulate physics, was first suggested by Feynman in 1982. Subsequently, Deutsch introduced a formal model of quantum computing using a Turing machine formalism, and described a universal quantum computer.

A quantum computer uses distinctively quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data stored as quantum bits (qubits). A qubit can hold a 1, a 0, or a quantum superposition of these. A quantum computer operates by manipulating those qubits with quantum logic gates. The notion of information is different when studied at the quantum level. For instance, quantum information cannot be measured reliably, and any attempt at measuring it entails an unavoidable and irreversible disturbance.

The 1980s saw an abundance of research in quantum information processing, such as applications to quantum cryptography which, unlike its classical counterpart, is not usually based on the complexity of computation but on the special properties of quantum information. Recently an open air experiment was reported in quantum cryptography (not involving optical cable) over a distance of 144km, conducted between two Canary islands.

it is indeed
believed that one
of the possible
contributions of
computer science
to biology could be
the development of
a suitable language
to accurately and
succinctly describe,
and reason about,
biological concepts
and phenomena.

The theoretical results that catapulted quantum computing to the forefront of computing research were Shor’s quantum algorithms for factoring integers and extracting discrete logarithms in polynomial time, obtained in 1994—the same year that saw the first DNA computing experiment by Adleman. A problem where quantum computers were shown to have a quadratic time advantage when compared to classical computers is quantum database search that can be solved by Grover’s algorithm. Possible applications of Shor’s algorithm include breaking RSA exponentially faster than an electronic computer. This joined other exciting applications, such as quantum teleportation (a technique that transfers a quantum state, but not matter or energy, to an arbitrarily distant location), in sustaining the general interest in quantum information processing.

So far, the theory of quantum computing has been far more developed than the practice. Practical quantum computations use a variety of implementation methods such as ion-traps, superconductors, nuclear magnetic resonance techniques, to name just a few. To date, the largest quantum computing experiment uses liquid state nuclear magnetic resonance quantum information processors that can operate on up to 12 qubits.

nature as computation

The preceding sections describe research on the theory, applications and experimental implementations of na-ture-inspired computational models and techniques. A dual direction of research in natural computing is one in which the main goal becomes understanding nature by viewing processes that take place in nature as information processing.

This dual aspect can be seen in systems biology, and especially in computational systems biology, wherein the adjective “computational” has two meanings. On one hand it means the use of quantitative algorithms for computations, or simulations that complement experiments in hypothesis generation and validation. On the other hand, it means a qualitative approach that investigates processes taking place in cells through the prism of communications and interactions, and thus of