Project Summary

MULTI replaces the familiar sequential model of computation that uses Boolean variables and combinational gates by logic operations that are executed in parallel on devices that have a built-in many state memory and whose inputs and outputs are multivalued. MULTI seeks to design, simulate and experimentally implement proof of principle devices on the atomic and molecular scale.

refers to the unique novel characteristics of the proposed schemes. We use MULTI-level logic variables as opposed to two valued Boolean variables. We use MULTI-variate circuits that act in parallel so that more than one logic function is evaluated at every stage of the computation thereby aiming for parallel circuits. We use MULTI-state inbuilt memories. New functionalities and ground-breaking characteristics of information processing are provided by the radically post-Boolean MULTI approach. As a final thrust, MULTI will explore a post-Turing model of computation by using continuous variables.

In MULTI a single atom, molecule or a supra(bio)molecular assembly acts as a logic element. We aim for proof of concept of fresh modalities and new foundational principles that can be brought to a level of laboratory experiments. MULTI plans to take advantage of internal degrees of freedom of atoms or molecules to implement logic operations by electrical addressing in the solid state and/or by optical addressing in solution. The dynamics offers time-resolved response and thereby enables parallelism that can be massive because of the many resolvable states. Internal states of different molecules can be made to communicate thereby providing for concatenation. The other route of MULTI is (bio)chemical recognition that offers exquisite control for implementing many state, optically readable finite state machines.

Benefits of MULTI approach are higher information rates for inputs and outputs, enhanced rates of processing due to parallelism and computing in memory and exploration of continuous logic.


Work Programm

1.1 Concept and objectives

1.1.1 Concepts

Current computing machines are designed on the basis of a Boolean algebraic model where a variable, an input or an output, is two-valued. The logic is performed by combinational gates that provide an output that depends only on the input. Towards a new approach to logic and computing taking advantage of the atomic and molecular scales MULTI makes a radical departure from this prevailing Boolean paradigm.
MULTI proposes a physically motivated approach to computing at the nanoscale that gives up the notion of a Boolean gate implemented as a circuit of switches as well as the design of such gates connected sequentially to one another. In order to lay the foundations of physically motivated novel ways to compute at the molecular scale, the basic questions that MULTI aims to answer is ‘what is a natural and efficient way for a molecular or a supra(bio)molecular logic device to physically operate’ and ‘how do we input different instructions to such a device’ and ‘how does the inherent time evolution of the device deliver different outputs for different inputs’, ‘what are the physics features required for programming a device at the molecular scales’. Taking into account the inherent physical properties of the atomic and molecular scale devices, MULTI can naturally address the questions of ‘can we simultaneously deliver more than one output for a given input’ and ‘can the device remember what it previously went through so that the next outputs depend not only on the present inputs but also on the current state of the device’ and ‘can one use physical variables represented as real numbers for computing’. MULTI proposes that this physically motivated approach to ‘what is computing’ is a way to make breakthroughs and deliver novel capabilities for implementing logic at the nanoscale and physically realize

  • massively parallel computations,
  •  multivalued computations up to and including continuous logic,
  •  inbuilt memory, including acquired memory,
  • reconfigurable/programmable logic machines .

The logics proposed above is post the von Neuman and Turing models.
MULTI proposes to implement these unconventional logic operations up to the proof of concepts on three different kinds of molecular systems that possess many states that can be selectively addressed and undergo time-dependent transitions, opening the way to multivalued and parallel logics and programmability:

  • optically addressed multichromophoric supramolecular complexes
  • electrically addressed artificial atoms or molecules in the solid state
  • chemically addressed DNA machines and devices

The dynamics of these systems will be followed in time by state of the art experimental techniques : 2D photo echo spectroscopy for multichromophoric systems, pulsed gate voltages for dopant atoms and artificial molecules and time-resolved fluorescence for DNA assemblies. The unconventional logic design will be implemented at the hardware level, based on the physics of the complex time evolution of these multi-state systems.

Zone de texte:   Figure 1. A schematic representation of a finite state machine. MULTI will implement multivalued parallel FSM, optically, electrically and chemically addressed. An atom or a molecule or a nano-dot can perform a logic much more complex than a single switch. This is made possible by evolving the internal states via a not low order perturbations which means that several computations can be carried by the system at the same time. To realize this parallelism we do not have to rely on coherence for the encoding of information as in quantum computing and this reduces the sensitivity to noise. When there are many internal states that can be accessed the parallelism can be massive. If we use observables, see below, we can achieve parallelism on a scale that is doubly massive. Furthermore, internal states of different molecules can be made to communicate thereby providing for the cascading of information from one logic unit to another. The second point is that a variable is not restricted to the values of 0 or 1 and so one can perform multi-valued logic all the way to continuous logic where variables are real numbers. The third essential implication of miniaturization at the atomic and molecular level is that the (quasi) stationary internal states can store intermediate results of the logic operations. Thereby we can realize a logic circuit where the response depends on the initial state of the molecule and the output depends not only on the input but also on the initial state of the device. This is the key characteristic of a finite state machine (FSM) (see figure 1) that allows computing in memory. We can address such machines optically, electrically or chemically.
MULTI aims to achieve laboratory proofs of concept of these novel capabilities for two kinds of molecular degrees of freedom.

  • The first kind of logic machines that will be implemented takes advantage of the physical degrees of freedom of atoms or molecules, which are internal and quantized and therefore discrete. Their addressing opens the way to parallel and to multivalued and continuous logic schemes. Lastly, as was recognized by Heisenberg, an atom or molecule has more variables that can be observed than the number of quantum states. Therefore a particularly rich logic is made possible by using observables. Designing how to do so and then implementing this promising theoretical potential as an experimental proof of principle is one of the challenges of MULTI.

Two different ways of inputting the information to physical degrees of freedom will be implemented in MULTI. Both are well suited to address the multilevel structure. The first one is 2D optical addressing of multichromophoric bio inspired molecular complexes in solution. Compared to conventional 1D techniques, 2D electronic spectroscopy gives access to a significantly larger number of observables and thus represents a powerful tool to experimentally demonstrate the potential of molecular systems for implementing complex logic. Moreover, the possibility of sampling a considerable number of initial conditions (fields polarizations, pulse sequences, …) allows providing different sets of input instructions and simultaneously probing the different answers of the system in a time resolved manner. This ultrafast way of addressing offers a method of processing information that is significantly faster than electrical addressing and very rich in the multilevel structure of variables and in the number of computations that can be performed in parallel. It is particularly well suited for computing by observables as discussed in section 1.4 (WP1) below. We consider that a proof of concept demonstrating many parallel computations will be available by the end of the second project year. Next is electrical addressing. Electrical addressing of single atoms and molecules is more complex and slower than optical addressing. However, it offers a clear pathway towards circuits and scalable solutions that interface with conventional electronics. MULTI aims to implement the functionality of molecular computation in a solid-state environment to utilize a large set of internal degrees of freedom in a robust manner. The systems investigated will be dopant atoms and molecules deterministically engineered in Si and electrically addressed by pulsed gate voltages. As discussed in the supplements of WP1 and WP3 this enables us to achieve parallelism also by electrical addressing using a CMOS compatible technology.

    Zone de texte:   Figure 2 a) Building blocks of DNA machines. The machine shown in b is built of three tweezers where a tweezer is shown in the middle panel of a. We plan to cascade the building blocks using DNA strands. b) A machine that has 32 different states and transitions between them. The key point is that the output of a finite state machine depends both on the input and on the state of the machine. Therefore this machine has a rich repertoire of computations that it can execute.[ref 10  below, P1,P2 and P5].
  • The second level of machines relies upon the biochemical degrees of freedom or, as we prefer to call it, chemical instruction and recognition. It is a slower method because atoms move far more slowly than electrons. So it is necessarily slower than even current computational devices. But the selectivity is tremendous. For intelligent sensing, whether environmental or biological and for nanomedicine and in situ response the chemical degrees of freedom are the approach of choice. In addition, biosystems offer a clear example of acquired memory. It is part of the MULTI effort to better characterize this response and to explore how to transfer this concept to physical degrees of freedom. It is also in bio systems that the potential for really large number of states, in the hundreds to tens of thousand are made available for the development of high throughput data acquisition and the theory partners of MULTI have experience in analysing those from an information processing perspective. In MULTI, we will more specifically use DNA machines as building blocks as shown in figure 2a to construct cascades of devices exhibiting time-dependent multistate dynamics and selective response to chemical addressing as shown in figure 2b. These systems will allow the implementation of cascaded multivalued parallel finite states devices.

All the schemes described above can implement continuous logic. The reason is that they are not Boolean. So it is not the case that a state of the machine is either on or off. It can be that the machine is in a given state with a 21% probability. In a Boolean context we will either call this ‘off’ or we can say that it is a ‘don’t know’. But in the case of continuous logic we will say that the probability of the state is 0.21 and regards the probability as a logic value. We do this following Cox who showed that probabilities satisfy the axioms of Boolean algebra.
MULTI gathers internationally recognized experts in information theory, molecular logic, molecular dynamics, time-resolved 2D optical spectroscopy of electronic states in supramolecular assemblies, time-resolved electrical characterization of molecules in the solid state and kinetics of chemically addressed DNA machines, see Table 2.3 and section 2.3 for more details.
At the heart of our vision for the establishment of radically new paradigms for computing at the molecular scale is a MULTIdisciplinary approach, that is made possible by the complementarity of the partners of the project. This MULTIdisciplinarity is essential because it allows to identify the physical characteristics for implementing new computational logic schemes and to transfer concepts and designs of logic machines from one way of system to another, as some of the MULTI partners have successfully demonstrated in the past in the FET proactive NANO-ICT MOLOC and FET open MOLDYNLOGIC projects.

1.1.2 S&T objectives

MULTI offers a new vision of computation based on the unconventional paradigms of multivalued and continuous logic. Its vision is to use the discrete level structure of molecules and finite number of chemical degrees of freedom towards a non-Boolean parallel processing with higher speed of processing input, throughput and output.
Zone de texte: (i)	Identifying the key characteristics of physical systems that allow to go beyond the von Neuman and Turing models for computation. a)	 non-Boolean (multivalued or continuous) parallel processing by controlling the dynamics of instructed atomic, molecular and biochemical systems.  b)	reconfigurable/programmable logic (ii)	Nanoscale engineering and characterizing theoretically, optically, electrically and biochemically physical systems that possess the identified key characteristics for implementing new logic functions. (iii)	Designing new logic schemes and implementing those optically, electrically and by chemical addressing at the level of proof of concepts. MULTI three main S&T objectives towards the development of radically new paradigms for information processing at the molecular scale are
These S&T are closely reflected in the list of milestones in Table 1.4c below. To realize its objectives, MULTI is organized into four closely interacting workpackages : a theory WP and three experimental WP’s in which the logic will be implemented using optical(WP2), electrical (WP3), and biochemical (WP4) instruction and readout. The interdependencies between the WP’s are shown in Figure 3 below.
WP1 : Design of Finite State Machines, Parallel Processing, and Non Boolean and Continuous Logic Devices, a theory WP that gathers R. D. Levine (P2-HUJI, workpackage leader) and F. Remacle (P1-ULg) that is in charge of establishing the new physically motivated vision of computation and translate it into realistic designs and demonstrations by simulations.
WP2 : Beyond conventional optical addressing: 2D electronic spectroscopy techniques is led by E. Collini (P3-UNIPD). The main aim of WP2 is to apply the recently developed 2D electronic techniques to optically address molecular logic machines. The key points in this context will be (i) the possibility of processing information in the ultrafast regime (fs to ps) and (ii) the access to a considerably greater number of input conditions and output observables with respect to conventional optical techniques.
WP3 : Electrical addressing of molecular systems in the solid state, led by S. Rogge (P4-UNSW) is an experimental WP that investigates molecular computation schemes in the solid state. Strong focus will be on the physical implementation of multi-valued parallel logic on a single molecule using pulsed experiments.
WP4 : DNA based Machines as programmable multivalued finite state parallel devices led by I. Willner (P5-HUJI) represents an experimental effort to construct different multi-valued finite-state devices based on DNA machines, such as rotors, multi-ring catenanes, rotaxanes and cranes using the dynamical features of the DNA machines, and the time-dependent optical parameters accompanying the transitions between the states of the devices.
The logic machines that will be physically implemented by MULTI are by increasing level of complexity:

  • simple finite state machines, with an internal memory of few states with emphasis on acquired memory,
  • cascade of finite state machines, where the output of one can serve as the input of the next,
  • massively parallel finite state machines with emphasis on computing by observables.
  • Zone de texte:   Figure 3 : Interdependencies between the WP’s and the objectives of MULTI
     reconfigurable/programmable devices.

Logic operations, such as search, factorization, polynomial decomposition, transform calculus, pattern recognition that are not efficiently implemented by conventional Boolean von Neumann architectures will be particularly targeted. We will furthermore seek to use variables that are continuous rather than discrete to implement continuous logic Concentrations, probabilities (e.g., a level that is only partially populated), etc are typically represented in an experimental setting as continuous and this is so even when the atomic structure of matter means that strictly speaking such variables as concentrations are discrete.
Two fields of expertise common to all the MULTI partners are crucial for delivering the objectives of the project. The first one is their expertise in following the time evolution of nanosystems upon receiving an input, both by developing the appropriate model for simulating theoretically the response and by physically measuring this evolution by optical or electrical means. While the time scale of the response vary (from fs to ps for 2D two photon echo spectroscopy to ps to ns for electrical addressing and min to hours for biochemical inputs), the prerequisite for the physical implementation of a parallel logic scheme is the same: the system must change in time in a non trivial manner upon receiving inputs because of the complex internal dynamics made possible by its internal states. This brings us to the second feature common to partner expertise, that is, the ability to model and characterize systems with a dense set of states. Again the nature, energy spacings and number of available states differ significantly depending if one considers the vibronic level structure of a protein or a polymer as in WP2, the ladder of states of engineered dopant molecules in a transistor or a solid state environment in WP3 or the biological degrees of freedom as in WP4.

What is common to all the partners is the ability to address selectively several (up to hundreds in DNA based systems) distinct states and resolve their time evolution. Monitoring the response of dense sets of states in time is the essential physical characteristic that is needed for implementing multi-valued parallel processing. Because of this shared expertise, we expect fruitful transfers of concepts for implementing logic between the optical, electrical and chemical addressing.

Most of the partners in MULTI have successfully collaborated before in the framework of the MOLOC project. The partners of MULTI have preliminary theory results and experimental substantiation that their vision of MULTIvariate computation with MULTI valued logic using MULTI state memories can be implemented. Both experiments and theory show that this is robust and remains so even when perturbation by the environment is significant. They use complementary approaches to address the systems at the molecular level. Therefore, the objectives should be realistically achievable within the three-year project period.
Relevance of the project
MULTI directly addresses the objectives set out in ICT-20011.9.6: Unconventional computing by proposing a physical theory for parallel multivalued computing and physical implementations of the new logic schemes on three kinds of systems : in WP2 proteins and supramolecular complexes optically addressed by 2D photon echo spectroscopy, in WP3 molecular structures embedded in solid state electrically addressed and in WP4 chemically addressed DNA based supramolecular assemblies. These three systems have in common a dense set of resolvable states that can be followed in time. They are thus systems of choice to physically realize multi-valued parallel logic schemes which represent a radical departure from conventional Boolean paradigm and the von Neumann and Turing models for computation. MULTI will implement reconfigurable logic at the hardware level, thereby breaking the layer approach in computer architecture. The three systems are also well suited to investigate appropriate interfacing with conventional IT devices. In particular, devices that use single atoms or molecules in the solid state are fully CMOS compatible. Therefore the new unconventional logic schemes that MULTI will develop could be efficiently integrated as specific units in existing CMOS architectures. The chemically addressed DNA based supramolecular assemblies can be used for implementing in vivo complex computations and have direct applications for nanomedicine. Optical addressing schemes can be integrated in all-optical circuits and photonic devices performing photonic logic at molecular level.
MULTI will do the foundational science necessary for the design and the physical implementation of logic devices with fundamentally and qualitatively novel functionalities that take advantaged of the multi state structure of matter at the molecular and nanoscale.
MULTI aims to take the foundational physical theory that it develops up to a proof-of-concept level for the design and experimental demonstration of logic devices that harvest the complexity of matter at the microscopic scale. These devices processing parallel multi-valued logic will possess fundamentally and qualitatively superior functionalities, from post-Boolean to efficient concatenation schemes, parallelism and reconfigurable/programmable devices.
The objectives of MULTI in terms of the experimental realization of efficient cascade of gates by electrical, optical and electrochemical addressing, of Non Boolean logic devices, of parallel computing by time-resolved optical or electrical addressing and of reconfigurable/programmable devices are significant steps up in the capabilities of molecular scale logic devices and circuits. In doing so, MULTI builds upon the achievements, but clearly goes well beyond the objectives of the MOLOC project of the FET-Proactive - ICT- 2007-8.1 Nano-scale Devices - New Functionalities call in which some of the MULTI partners took part. The significant potential contribution of MULTI to progress in science and technology of the physical theory of information processing systems is discussed in section 1.3 below.
One of the partners of MULTI, Sven Rogge (P4) is presently affiliated to the University of New South Wales (UNSW), Sydney, Australia. Sven Rogge, a partner of the MOLOC project previously at TU-Delft, possesses a unique expertise in accessing orbital degrees of freedom of molecular dopant assemblies in the solid state which was recently augmented with time resolution using pulsed gate voltages. MULTI will highly benefit from the Rogge group due to their single atom transistors and STM manufactured dopant molecules. The essential reason for his move to Australia was the uniqueness of the Australian Research Councils Centre of Excellence for Quantum Computation and Communication at UNSW to fabricate dopant assemblies in Silicon with atomic precision. We further discuss the benefits of including Sven Rogge as a partner in section 2.3.2 below.
By keeping tight collaborative links with Australia, MULTI will contribute to make Europe an essential partner in the effort to develop unconventional computation device compatible with the CMOS environment and contributes to global international cooperation as listed in the expected impacts of the UCOMP call. As indicated by the letter of the school of physics of UNSW, UNSW fully support the participation of P4 to the project and will grant MULTI full access to its fabrication facilities. UNSW also states in unequivocal terms that it strives to strengthen its collaboration with Europe.
The ways in which MULTI will meet the technical objectives of this call are discussed more fully in the workplan in section 1.4 and then in section 3.2, where the impact of achieving these scientific and technical objectives is also discussed in more detail.