DIRD Quantum Computing and Utilizing Organic Molecules in Automation Technology

Quantum Computing and Utilizing Organic Molecules in Automation Technology

Defense Intelligence Reference Document, Defense Futures. DIA-08-1102-005, 10 December 2010 (ICOD: 10 December 2010).

Prepared by the Defense Intelligence Agency. This product is one in a series of advanced technology reports produced in FY 2010 under the Defense Intelligence Agency Advanced Aerospace Weapon System Applications (AAWSA) Program.

Copyright warning: further dissemination of the photographs in the original publication is not authorized.

Summary

Powerful onboard computing hardware is a desired option for future space travel. Without large data processing capability, the copious amounts of data acquired during flight from astronomical sensors as well as crew and vehicle sensors will need to be sent back to earthbound machines for processing, introducing delays measured in hours for routine calculations. Current commercial computer hardware trajectories in silicon substrate semiconductors are not likely to produce a radiation-hard or small and portable supercomputer without significant mission-specific alteration. Alternatives to traditional computing technology include computers based on entangled quantum states and molecular computing hardware based on DNA molecules.

Included in this review is significant introduction to the necessary elements of quantum computing and a summary of the state-of-the-art technologies. Following is background on DNA and production of engineered DNA chains. Finally, DNA logic gates are presented along with a treatment of nanomachines that will repair DNA circuitry. Forecasts of technology development in the 10-20 and 40-year horizons are included along the way, as well as summary discussion and a conclusion.

The first operating quantum computers capable of solving real-world problems will commence within 10 years and be based on ion trap technology. This is entirely based on the amount of research resources dedicated to the problem and the fact that there appear to only be engineering challenges remaining. Atomic and ion traps require very substantial cryogenic and electromagnetic shielding systems and are not practical for space travel.

Pure photonic technologies available today have difficulty with both miniaturization and scalability. However, the amount of active work in the field makes a disruptive advance likely in the 10-year timeframe. Optical computers will likely be realized in the 20-year horizon; however, the very powerful promise of quantum computing will still have issues with photon loss in any solid state device. The 40-year horizon will see photon technologies play an essential but supporting role in distributed quantum computing. Realized all-optical non-quantum systems will have radiation tolerance advantages over current semiconductor technology and are likely to augment or even replace general-purpose computing devices for space travel.

Hybrid designs utilizing arrays of quantum dots and photon communication channels will be an option for space travel supercomputing on the 40-year timescale. These systems operate at attainable temperatures without cryonics, and require no more shielding than humans. It is likely that spintronics will be an essential ingredient.

Simple organic computing based on DNA tiles will be realized in the next 20 years. On the 40-year time horizon useful DNA-based devices will be essential space exploration tools. These could take the form of orbital-delivered wireless sensors searching planetary or asteroid features or for essential compounds such as high concentrations of water. DNA computers will also be realized on the 40-year timeline. Their advantage over solid state devices will be the ability to repair nanoscale elements damaged in normal use or by cosmic radiation. These will not be the fastest systems in the astro-arsenal, but self-repair may make them the most robust.

Introduction

Computers today are not what they used to be. In the 17th century, a computer was merely a person who performs computations. In this sense, the first computers were universally programmable and were ultimately utilizing organic — DNA — hardware architecture. The modern sense of a computer as a machine that manipulates input to produce deterministic output emerged from the work of Turing in the 1930s. A Turing machine consists of four parts: tape containing cells of symbols, read head, action table, and state register. In operation, the state register is initialized, the first cell of the tape is read by the head, the table translates the symbol into an action in the state register, and the tape is advanced to read the next symbol. The read, action, advance tape loop is repeated until the program ends. Any calculation a modern digital computer can perform can be accomplished using a Turing machine.

Modern digital processing hardware, first used in the ENIAC in the 1950s, is based on logic gates. All functions of a computer consist of the basic logic elements AND, OR, NOT, and so on. These are accomplished electronically by producing logic gates, combinations of transistors that perform the logic function on input data. A common exercise in didactic digital logic pedagogy is to design all of the basic logic gates using only NAND or NOR gates; thus, any hardware element that can execute the NAND function can build a complete computer. Optimum designs are regularly more elegant than combining a single two-input gate, but it is sufficient as proof of principle for any architecture to be able to produce an inverter and a simple logic gate.

The quest for faster computing can be accomplished by making current hardware architecture faster, or by designing new hardware based on different architecture that solves the calculation in fewer steps. The current treatise concentrates on the latter, dramatically changing the architecture of modern computers to perform calculations in a different manner. Two methods are explored: that of creating logic gates, and that of creating a general Turing machine. The second of these is explored in the context of quantum computing with an emphasis on organic molecules as a core technology. Designs of logic gates utilizing DNA are covered. Background on all these areas of research is included first. Finally, DNA machines that can assemble and repair DNA technology are outlined.

Ultrafast Computing Power in Aerospace Applications

The history of manned spaceflight does not include powerful computers as integrated companions; space-borne supercomputers have so far been reserved to the world of science fiction. The main issue on space stations has been radiation hardness, while the main issue on vehicles such as the space shuttle has been safety. The amount of testing required for a microprocessor to be certified for space precludes the most current technology from becoming astro-worthy. Indeed, the most powerful general purpose computers riding in the shuttle are the laptops the astronauts bring with them.

The first challenge to overcome in supercomputing in space is radiation causing temporary and permanent errors in calculation. The current approach is to make the solid state components radiation-hard, a time-consuming and costly process. An alternate approach is to use multiple commercial-off-the-shelf components in parallel architecture. George’s group at the University of Florida pursued this approach with earthbound success. A good question arises: if 50 years of space travel hasn’t required one onboard supercomputer, why start now? It seems NASA asked this question as well and, after years of preparation, cancelled the space test of the technology in late 2009.

Regardless of the need for current missions, one can imagine many future applications where it would be more convenient to data process on long space missions without downloading data to Earth-based systems and uploading the results. This is especially true for long-duration spaceflight where communication delays could be minutes to hours — Mars about 13 minutes, Jupiter about 45 minutes, and Neptune about 4 hours. Spacecraft active in the 40-year horizon will require supercomputing technology onboard to process all of the data to be acquired during flight. This includes astronomical data as well as ship and crew data. Example missions include Mars with a goal to analyze the planet using thousands of semi-autonomous sensors or millions of independent, wirelessly communicating nanomachines, so-called magic dust. In such scenarios, it is not necessarily numbers that need lots of crunching, but algorithms that need to be run on powerful systems that could be non-traditional in their design; for example, massively parallel.

Making Digital Circuits Faster

In consideration of the underlying physics in the electrodynamics of transistor operation, the scale of the constituent elements dominates the type of analyses required. In the macroscopic regime, constituents are measured in microns or larger, properties are dominated by well-defined statistical averages in bulk matter, and non-classical effects due to the underlying fact that all particles involved in the interactions are really fluctuations within a relativistic quantum field can safely be ignored.

(Two paragraphs here trace the switch from emitter coupled logic, which reached sub-nanosecond switching at the cost of large standing current and hard cooling, to the saturating CMOS families that are the present state of the art at 32 nm production and 22 nm demonstrated pitch — against atomic diameters of 0.1 to 0.5 nm. They are omitted for length; the complete text is at the source.)

As circuit elements decrease in size, the number of atoms making up the bulk materials decreases and ignoring individual quantum effects becomes problematic. This is the mesoscopic scale. At this size, quantum effects can introduce noise into the circuit as the unpredictable nature of the underlying wave functions. Once the circuit size shrinks to only a few atoms, quantum effects will emerge from the noise domain to dominate the electrical behavior. It is thought that exploiting rather than avoiding quantum phenomena may prove useful in this regime for inorganic technologies.

Following Moore’s law, in less than 10 years inorganic circuit elements will be less than five by five molecules in two-dimensional extent. Shrinking traditional silicon-based general-processing technology to this microscopic scale is one motivation for developing new types of machines based on quantum phenomena, but it is not the only one. Smaller circuit elements decreased the settling time of transistors and thus gates on CPUs, allowing increasing clock speed. CPUs today get most of their performance with parallel architecture, executing several instructions at once in different pipelines. Using smaller circuitry in general consumes less power, and this allows more parallel elements to be packed into a reasonable wattage package. The march toward smaller circuitry is continuing unabated, so planning for the eventual quantum-dominant characteristics is essential.

It is common to use the analogy of the laser to elucidate the application developments possible with quantum computing. In one sense, the laser is just another hardware technology that makes light. Earlier light technologies include organic-fueled fire, incandescent bulbs and fluorescent chambers. The light source to utilize is not governed by the highness of the technology, but by requirements of the application. One can read by laser light, but older and cheaper incandescent light will provide superior perceptible illumination to a page. Traditional semiconductor-based computing is cheap and plenty powerful for controlling navigation or driving ship status displays.

The laser analogy is further revealing in that it is quantum effects producing a special kind of light that is coherent. Coherent light is single wavelength with all photons travelling in the same direction. This coherence is a natural consequence of conservation of momentum in the absorption and emission process. Coherent light is very useful for some applications that require low dispersion; for example, bouncing a beam off of a mirror on the moon, or the more pedestrian pinpoint highlight of a projected presentation.

The practical uses of the laser are not universally bigger or smaller, faster or slower, or more or less energy efficient than the other hardware technologies that produce light — they are just different. Similarly, when we think of what hardware and applications will arise for quantum computing, they too are not necessarily bigger, smaller, or faster than traditional methods; they are just different, and many could not be accomplished with traditional technologies.

Applications of Quantum Computers

Although smaller circuitry and supercomputing is a motivator, the driving application behind quantum computing is cryptography. First, there is cracking cipher codes. The vast majority of secured communications utilize a method known as public-key cryptography. In this method, the code is based on the prime number factors of a very large integer which is publicly available. The private key is one of the integer factors and this allows the receiver of information to decipher the code easily. The strength of this technique is that traditional computer algorithms will take a long time to guess the correct factors of the public key, on the order of months. Traditional brute force methods require a number of steps that increase as an exponential function of the size of the public key.

However, in 1994 Shor presented a quantum algorithm that would only require a polynomial number of steps, thus dramatically decreasing the required time to factor, assuming a quantum computer would ever be physically realized. This speedup is primarily due to the nature of quantum waves; specifically, they can follow several parallel paths instead of the usual stepwise procedural execution of instructions. This acceleration by superposition concept is more easily understood in a random search of data. Consider an algorithm that has a 50 percent probability to locate a specific phone number in a database of N phone numbers by a random search. The procedural algorithm on average will require 0.5 N inquiries to locate the correct number. A quantum algorithm on the other hand can be devised that accumulates information by examining multiple numbers with each step. Such a scheme has been shown to reduce the number of examinations required to the square root of N. The superposition of states allows examination and processing of several tape cells simultaneously in a Turing-inspired machine.

Second, there is quantum communication. Once public key encryption is easily broken by the quantum computer, a new cipher needs to replace it. The canonical quantum communication experiment defines a sender, Bob, and a receiver, Alice. In most scenarios Alice and Bob communicate over a distance using entangled particles and a traditional open line. The open line relays information about measurement settings, but is useless to an observer without access to the entangled wave function. The other advantage of this setup is that almost any disturbance in the communication line between Alice and Bob would destroy entanglement and thus the information would be lost instead of intercepted. Additional archetypical participants in a communications scenario follow the English alphabet: Charlie, or Chuck if his intent is malicious, Dave, Eve, and so on. Quantum communication is thus an application replacing one performed by a general purpose computing machine; the classical and quantum systems do not operate in similar fashion other than the function of securely transmitting information. Additionally, quantum communication has been suggested as a method to connect isolated quantum systems without disturbing closed box requirements like classical interventions would.

Beyond cryptography is a third application, quantum metrology, where time or distance are measured to an extremely high accuracy. A fourth obvious application is simulation of quantum systems.

The Closed Box and Fault Tolerance

In traditional silicon transistor circuits, once a bit is set to 1 or 0 by a gate or other device locking the output voltage, that value is expected to remain through subsequent clock cycles until deterministically changed. Additionally, traditional circuits behave by the same rules for each clock cycle; that is, as more information is processed, repeated gate operation does not deteriorate the bit latching mechanism. This behavior is achieved by constantly providing energy to the circuits. Any interruption in this constant need for power from the outside and the integrity of the information in the computing circuit is lost.

A fundamental principle of quantum mechanics is that any external influence on a system necessarily disturbs the state of that system. This influence could be external disruption or internal leakage — either interaction will change the internal quantum state. This destructive process is known as decoherence. External influences will disturb the system and thus the circuits need to be isolated from the rest of the universe, also known as the closed box requirement.

Trial to trial variations in a quantum circuit produce an increasing deviation from an initial phase as the wave function evolves. This trial-to-trial deviation causes decoherence on a timescale termed T2 star. Although a single trial in a quantum circuit could retain coherence longer than T2 star, absent external influence the isolated internal circuit components must eventually come to thermal equilibrium through random processes: this occurs on timescale T1. Moreover, the closed box cannot be perfect since a useful device requires some kind of input and output, thus some small interaction with the external environment is necessary. Random interactions with the environment from this isolation leakage will dephase internal signals on timescale T2. These three time constants that describe the internal signal decays are very similar to the same named quantities in nuclear magnetic resonance. Nuclear magnetic resonance is indeed a technology path under development for quantum circuits. Each technology and hardware design will be characterized in its isolation from external and internal influences by T2 star for stable repeatability, T1 for resistance to entropy, and T2 for isolation from the rest of the universe.

No design can be completely free of decoherence and the next consideration is how much decoherence is acceptable, or more precisely, what is the fault tolerance threshold for successful operation? Fault tolerance isn’t much of a consideration in traditional processing architecture, although it is a major consideration in storage and communication of information. To illustrate fault tolerance, consider a scheme of hard disk storage configuration where each 8-bit byte is written across 9 disks in a stripe-set configuration, one bit per disk, read in parallel. The extra disk holds parity information about the byte. Consecutive bytes shift the location of all bits one disk so the parity information isn’t all stored on the same disk. In the event one disk fails, each byte can be reconstructed from the other 8 disks using a software algorithm that automatically starts when the disk failure is detected. The broken hardware can be replaced and the data reconstructed while the system is operating in this slower limp mode. This storage system is said to be fault tolerant. The drive failure detection and algorithm takeover in the readout phase is the error correction scheme.

In a quantum system the error correction is accomplished in a similar manner; that is, the state of a qubit is defined across multiple subspaces of the logic space and then several measurements are performed on the subspace that do not disturb the state itself. The original state can be reconstructed by the partial measurement. As an illustrative example consider the one-qubit space defined by an electron spin-up or spin-down. First, redefine this one-dimensional state in an oblique three-dimensional system such that spin-up is in the plus-x, plus-y, plus-z octant, and spin down is thus in the minus-x, minus-y, minus-z octant. If one measures x as positive the original state was up; measuring x and y both positive provides additional assurance the state was actually up. Measuring x and y different allows z as a tie-breaker. In this example system, 33 percent error rates are allowed. Of course realizable systems are more complex and only tolerate error rates in the 3 percent range. This difference is mainly due to the need to disturb the system as little as possible in what is known as a quantum non-demolition measurement. In summary, fault tolerance is possible if a quantum non-demolition mechanism to measure qubits can be demonstrated.

Scalability

Once a closed box has been constructed, the next consideration in successful quantum information processing technology is whether circuit elements are scalable. That is, whether elements shown to perform as quantum bits can be combined into larger circuits at a reasonable cost of resources — computation time, decoherence time, physical space, or required power. The exact nature of the required engineering scale-up is specific to each technology.

The unit of quantum information processing is the qubit. Different from digital logic, quantum mechanics increases the information content in N qubits through superposition. That is, quantum waves can travel through several paths and contain a superposition of states, increasing the amount of information in each channel. Furthermore, any system of N qubits can have degrees of entanglement. This entanglement makes one simple example state different from another depending on which of the qubits are entangled with which. When there are 4 qubits, entanglement can occur with 2, 3 or all 4 bits, as well as 2 with 2. The logic space quickly grows to Bunyanesque proportions and is easily outside of the realm of simulation or even representation by N or even N squared classical bits. Considering that one could start with qupits or qudits — using p and d states rather than only two-level systems — it is quickly obvious that quantum computers have enormous computational potential when scalable.

Universal Logic

The very large number of possible states of a quantum computer spans what is known in mathematics as a Hilbert space, a generalized version of Euclidean space with arbitrary, finite or infinite, dimension. The concept of a universal logic requires that this large Hilbert space be accessible with a finite set of control operations. For most designs these control operations are small in number and are the quantum analogues of digital gates performing operations on qubits.

Two special schemes that operate differently than digital analogues of gate-based technology are adiabatic and cluster-state quantum computation. In an adiabatic design, the answer is the ground state of a complex network of interactions and the interactions are slowly turned on to evolve qubits from the initial state to the final ground state. In the cluster-state scheme, the system is placed in a particular state through use of a small set of control gates and the output is repeatedly measured using arbitrary basis, which is the fault-tolerance mechanism. In the adiabatic case, the computation is programmed in the setup of interactions. In the cluster-state case, the calculation produces a superposition of states that need several measurements to ensure correct interpretation. Both schemes have been shown to be equivalent to gate-based circuit technologies.

Initialization and Measurement

Implied in the discussions above is the ability to set the quantum computer into a known initial state, measure various states during computation if needed, and output the final state. These processes can be tricky while maintaining isolation and low entropy. The initialization and measurement techniques are discussed with each technology.

The Quantum Dot Approach

A major obstacle in the quest to design and construct a radically new kind of inorganic quantum computer has been finding a way to manipulate the single electrons that are likely to constitute the new machines’ qubits. The ability to manipulate and alter a single electron without disturbing the trillions of electrons in the immediate surroundings has become a research focus for many studies. A candidate is to utilize properties of the intrinsic spin of the electron. In 1925, Austrian physicist Wolfgang Pauli proposed that an electron in a quantum state can assume only one of two states, spin-up or spin-down. One approach to manipulate spin state and electrical charge independently for use in quantum computing has arisen in the quantum dot.

Quantum dots are tiny islands within a solid state lattice where electrons experience charging effects as well as quantum confinement, like an electron in an energy level around a nucleus. Besides fundamental insights into matter, these artificial atoms can also work as building blocks for the control of electronics at the single electron level. The so-called single-electron transistors are able to switch on and off electron transport through a dot by means of electrical gates using the effect of Coulomb blockade.

Conversely, one can use spin rather than charge to control electrical conduction in mesoscopic-scale electronics; such spin-controlled electronic devices, and their development and study, are termed spintronics. Exploiting the spin degree of freedom, a quantum dot can act as a spin filter or as a spin-blockade device. Quantum dots have been proposed as host for an electron-spin qubit. Arrays of such quantum dots with tunable tunnel-couplings between them would work as a universal quantum computer. Recent progress in this field using gallium arsenide based two-dimensional electron gases is impressive, though decoherence can arise from spin-orbit and hyperfine interaction with the nuclear spins of the host material. These decoherence effects can be reduced by using a lattice structure with low magnetic moment. Carbon has near zero magnetic moment due to the six each paired protons and neutrons in carbon isotope 12; a small net magnetic moment comes from the natural 1 percent contamination of carbon 13.

Electrostatic Quantum Dots in Graphene

The graphene form of carbon, a hexagonal sheet array a single atom thick, is a candidate substrate for quantum dots. However, two fundamental challenges need to be overcome before graphene can be used to form and operate spin qubits. First, it is difficult to create a tunable quantum dot in graphene because of the absence of an energy gap in the band spectrum. Electrons in such low energy gap materials exhibit Klein tunneling, complicating efforts to confine particles. Second, due to the valley degeneracy that exists in graphene, it is non-trivial to form two-qubit gates using Heisenberg exchange coupling for spins in tunnel-coupled dots.

Attempts have been made to solve the first problem, such as to use suitable transverse states in graphene ribbons to confine electrons, to combine single and bilayer regions of graphene, or to achieve confinement by using inhomogeneous magnetic fields. The second problem has only been realized recently, and scientists have created a method to confine the electrons in a unique valley through suitable transverse states in a ribbon of graphene which appears to overcome these limitations. The approach as used in gallium arsenide quantum dots is not possible due to Klein tunneling.

Figure 1 shows the hexagonal structure of graphene.

Several ways are possible to induce a gap in bulk graphene. In general, quantum confinement can lead to the opening of a gap in ribbons. Within the tight-binding approximation of graphene, armchair boundary conditions can lead to an insulator and gate-tunable quantum dots.

Another promising direction is to start with bulk graphene and induce a gap via the interaction with a substrate. Three quantum dot architectures that allow for bound states tunable by electrostatic fields are: graphene nanoribbons with armchair-terminated boundaries; discs in single-layer graphene; and discs in bilayer graphene. Special emphasis is given on the ability to controllably break the valley degeneracy, a prerequisite for two-qubit spintronic gates in graphene.

(Three subsections here — Quantum Dots in Graphene Nanoribbons, Graphene Disc in Single-Layer Graphene and Graphene Disc in Bilayer Graphene — set out the three gate-tunable dot architectures in detail, including the tight-binding treatment of ribbon edges, the quasi-bound states of a massless Dirac particle in an electrostatic well, the Bernal-stacked bilayer whose gap opens in proportion to the interlayer voltage, and the confinement-deconfinement transition that offers a solid-state test of the Klein paradox. Figures 2 to 6 belong to them. They are omitted for length; the complete text is at the source.)

Manipulation of Spin Qubits in Graphene Quantum Dots Relative to Gallium Arsenide

For universal quantum computing, single-qubit and two-qubit manipulations are necessary. Single-qubit rotations of spin qubits are naturally done by electron spin resonance and by electric-dipole-induced spin resonance. The Rabi frequency at which the qubit rotates in the electron spin resonance experiment is proportional to the electron spin g-factor, the Bohr magneton and the external oscillating magnetic field used to rotate the spin. Notably, the electron spin g-factor differs for different materials. In gallium arsenide quantum dots, it has been measured to be less than 0.43, whereas in graphene quantum dots it has been determined to be close to 2. Thus, it is possible to rotate the electron spin in graphene quantum dots using electron spin resonance about five times faster than in gallium arsenide quantum dots using the same field strength of the external oscillating magnetic field. This is an important gain because all qubit manipulations need to be done fast to avoid decoherence and implement fault-tolerant quantum computing.

Another important advantage of graphene spin qubits is related to the small band gap in graphene nanoribbons. For a ribbon width of about 30 nm, the band gap can be estimated to be of the order of 60 meV. This fact yields additional flexibility for two-qubit operations. Two-qubit operations are usually done via the Heisenberg exchange interaction. The tunneling matrix element can, however, be easily tuned by increasing or decreasing the overlap of the wave functions of the electrons in the two quantum dots. In graphene or any small band gap semiconductor, this manipulation can be done in two distinct ways: either through tunneling via conduction band states, that is normal tunneling, or through tunneling via valence band states, that is Klein tunneling. This has been predicted for graphene nanoribbons and experimentally realized in carbon nanotube quantum dots.

The most important physical consequence of this additional flexibility is the appearance of a new type of long-distance coupling between graphene spin qubits. By means of Klein tunneling, two distant qubits can be strongly coupled without touching the states of intermediate qubits that might be located between the two. Thus, a ribbon of graphene hosting many spin qubits in a line can be viewed as a qubit piano where any two of them can be entangled while leaving the states of the others unchanged. Interestingly, this feature — the availability of non-local interactions — is important for quantum error correction since it raises the threshold for fault-tolerant quantum computing.

Figure 7 illustrates the qubit piano: many spin qubits in a line hosted within a graphene nanoribbon, quantum dots drawn as red bars and barrier regions as blue bars, with strongly coupled spin qubits marked in the same colour. Figure 8 shows long distance coupling of three graphene qubits.

Spin Relaxation and De-phasing in Graphene Quantum Dots

Why can we expect stable spin qubits in graphene quantum dots? There is hope that spin relaxation and dephasing will be very weak in graphene for the following reasons.

Carbon is a light element with atomic number 6. Hence, its atomic spin-orbit interaction is weak as compared to heavier elements. However, such a statement should be taken with care because, in the solid state, spin-orbit coupling is oftentimes dominated by bulk inversion or structure inversion asymmetry. Therefore, crystal structures of light elements can, under certain circumstances, exhibit rather strong spin-orbit coupling. Prime examples are carbon nanotubes where theory predicted a substantial spin-orbit coupling of a few hundred microelectronvolts due to the curvature of the tube, which has been nicely confirmed in recent transport experiments on carbon nanotube quantum dots. Since the surface of graphene is less curved than that of carbon nanotubes, the spin-orbit coupling in graphene, due to ripples, should still be rather weak — roughly ten times less than the spin-orbit coupling due to curvature in carbon nanotubes.

Carbon has two stable isotopes: carbon 12 and carbon 13. The natural abundance is 99 percent carbon 12 and 1 percent carbon 13. Since carbon 12 has nuclear spin 0 and carbon 13 has nuclear spin one half, the electron spin of the qubit can only interact with 1 percent of the nuclei via hyperfine interaction. This ratio can even be further decreased because it is possible to artificially make carbon-12-enriched graphene.

(A subsection on spin relaxation due to spin-orbit interaction — the Elliot-Yafet and Dyakonov-Perel mechanisms, ripple-induced gauge fields, and the Princeton demonstration of nanosecond spin rotations driven by local gate-voltage pulses rather than gigahertz magnetic fields — is omitted for length; the complete text is at the source.)

Research with Graphene Quantum Dots

Graphene is an ideal candidate for spin qubits due to its low intrinsic spin-orbit coupling and the sparse amount of nuclear spins. We discussed bound states in gate-tunable graphene quantum dots realized in both graphene nanoribbons and gapped single-layer and bilayer graphene. In contrast to quantum dots realized in edged graphene flakes, gate-tunable quantum dots are defined electrostatically rather than by the physical edge of a graphene sample. This allows one to controllably break the valley degeneracy, a prerequisite for spin-based quantum computing, for example by using a magnetic field. We have also discussed quantum manipulation of spin qubits in such dots, as well as recent theoretical studies on the consequences of spin-orbit interaction and hyperfine interaction with nuclei for spin relaxation and spin decoherence.

Both theoretical and experimental efforts have focused on single-layer graphene quantum dots. The next major area is likely to be bilayer graphene. Bilayer graphene is potentially superior to single-layer graphene due to the creation of a tunable bandgap by electric fields which allows for an all electrical control of graphene quantum dots.

These new capabilities may be a boon for spintronic quantum information processing. Single-qubit gates based on single-spin electron spin resonance have achieved significant breakthroughs. Fast two-qubit operation, of about 200 picoseconds, has been demonstrated, but single-qubit operations on a similar time scale still remain a challenge. A proposed new configuration of two-spin encoding of the qubit, where a singlet and a triplet state play the role of the 0 and 1, shows promise. With this type of qubit, the interferometer demonstrated by the Princeton researchers could be used for single-qubit gates on a nanosecond time scale. Alternatively, fast qubit rotations in a slightly different singlet-triplet qubit can be obtained by aligning nuclear spins to create different nuclear polarizations in the two dots. Fast single-qubit and two-qubit gates available in the same system allow for efficient quantum error correction and could provide an important head start in the battle against decoherence. However, no two-qubit gates for this type of qubit, which would involve four spins, have yet been demonstrated. Utilizing graphene as a structural basis for quantum computing, coupled with other carbon based materials such as self-assembling DNA motifs, may lead the revolutionary development in quantum computing.

Summary of Additional Inorganic Technologies

The advancement of quantum computing schemes is the subject of significant investment and development over the past two decades. Recently, Ladd reviewed inorganic technologies. Ladd proposes that ion traps are the most probable technology based on their long T2, but then concludes that a comparison between the technologies is incomplete without further development on all fronts. The current treatise concentrates on organic technology but summarizes here the work of Ladd and others for completeness.

Photon Technologies

Using the polarization state of a photon is an appealing approach to store, communicate, and manipulate qubits. Photons do not require a vacuum or very low temperature for fairly good isolation from thermodynamic interactions. They do require special, non-linear media for robust, reliably predictable manipulation. A major advance in 2001, known as the KLM scheme, showed that scalable quantum computing was possible using linear optics and single-photon detectors and sources. The major hurdle, according to Ladd, is photon loss within waveguides, and is equivalent to decoherence time in other quantum hardware. The size of quantum gates is currently on the order of centimetres; this hurdle becomes less as gate size decreases. It is finally concluded that photons will likely be used in a hybrid technology with another quantum element serving as the basis for gates and other interactions. This scheme is known as distributed quantum computing, where elements can be separated by significant distance. This distance is either large by comparison with gate or gate array size, or actually large — kilometres — in a communications network.

Photonic technologies are a very active development area: the raw number of publications found for photon computers or photon computing shows more entries for 2009 than for 2008 and 2007 combined. Furthermore, many devices operate at or near room temperature and most do not require expensive cryogenic systems, making them inexpensive to research versus other technologies. These objective measures make breakthroughs more likely, and in 10 years all-optical computing should be addressing problems that cannot be accomplished via classical systems. In 40 years, manufacturing engineering will decrease the cost of these devices and they will be an option for many computing tasks in the space environment.

Ion and Atomic Trap Technologies

Individual atomic ions can be trapped in free space by nanoscale electrodes, while atoms can be trapped in an optical lattice created by lasers. In the ion systems, manipulation of electrode voltages moves ions around the lattice and interacts them with each other. In atomic systems, modulation of the optical lattice or external optical interference is used to manipulate the atoms. Ladd concludes that scaling is the primary hurdle in trap-based technologies.

More detail of such hurdles in trap technologies is revealed in a year-earlier, much longer, review by Haffner. Ion-trap-based gate operations are shown to have arbitrarily high fidelity, or higher fidelity than required for fault-tolerant computation. The current bottleneck in trap technology versus classical systems is the trapping frequency of a few hundred microseconds, even though massive parallel operations are possible. Haffner concludes that there are no fundamental barriers to scaling trap-based computing, but the technology is challenging and will progress as evolution rather than revolution. This is encouraging given that 40 years ago 20-nm transistors seemed challenging, but without fundamental operational barriers.

Nuclear Magnetic Resonance Technologies

Nuclear magnetic resonance storage and manipulation has been shown in liquid media up to a dozen qubits. Liquids are preferred because of their longer T2. However, thermal motion in the liquid state made scalability an issue. Moving to solid state nuclear magnetic resonance to address thermodynamic issues dramatically decreases T2. Ladd concludes that these technologies are a good testing ground for fault-tolerant algorithm development, but of little practical use for quantum computing.

Superconducting Technologies

Superconductivity is the flow of electricity without resistive losses. Similar to the laser, this macroscopic phenomenon has quantum mechanical origins. When cooled below a critical temperature, some materials form a lattice that allows electrons to pair and flow as a bosonic charged particle of charge two e. The components of superconducting circuits can be fabricated with current technology; however, decoherence times are limited to several microseconds maximum due to the large size — 100 micrometres — of the circuit elements and thus the large number of charge carriers in a qubit device, about 10¹⁰. Additionally, the current qubit device designs only operate at the scale of tens of millikelvin. Superconducting elements, specifically Josephson junctions, may play a role in hybrid designs such as the distributed ion traps of Haffner, but are currently not seen as a stand-alone technology for quantum computation.

DNA-based Designs for Molecular Computers

While traditional silicon-based circuits reach their fundamental atomic limitation, researchers search for alternative mediums for computation. The most logical solution to overcome this restriction in silicon-based integrated circuit architectures resides within our own bodies: deoxyribonucleic acid. Living organisms also carry out complex physical processes under the direction of digital information. Biochemical reactions and ultimately an entire organism’s operation are ruled by instructions stored in its genome, encoded in sequences of nucleic acids. When the workings of biomolecular machines inside cells that process DNA and RNA are compared to Turing’s machine, striking similarities emerge: both systems process information stored in a string of symbols taken from a fixed alphabet, and both operate by moving step by step along those strings, modifying or adding symbols according to a given set of rules.

Figure 9 shows a DNA nanomachine driven by repeated sequential addition of DNA control strands, opening and closing between a set strand and an unset strand.

DNA Background

Watson and Crick may have never realized the full potential of the double helical structure they identified nearly 60 years ago, for little was known about this amazing molecule that harnesses life. Biochemists in the late nineteenth century had found that these nucleic acids, long-chain polymers of nucleotides, were made up of sugar, phosphoric acid, and several nitrogen-containing bases. By the late 1940s the scientific community widely accepted DNA as the carrier of genetic information. But it wasn’t until 1977 that Fred Sanger developed the first dideoxynucleotide chain termination bottom-up assembly method for DNA. This technique would later usher in a new age of nucleic acid research and open the door for the modern era of biotechnology. With the advent of the polymerase chain reaction technology a virtual treasure trove of capabilities now exists for genetic and biochemical engineers to create customized DNA strands. This revolutionary process has created a multidisciplinary field of work within nanotechnology that intersects at the crossroads of computer science, biochemistry, material science, and engineering. This section on DNA-based nanosystems and computing will introduce several state of the art research applications and concepts currently being employed to produce DNA-based devices.

It is crucial to formulate a basic understanding of the structure and chemical principles of the DNA molecule to fully grasp its potential as a building material for DNA-based nanosystems. For the lay reader we have constructed a simplistic outline to illustrate the general principles of the DNA molecule that hold true to their biochemical properties as they apply to bottom-up nanostructure assemblies.

1. DNA consists of two long polymers made of simple units called nucleotides, with backbones made of sugars and phosphate groups joined by ester bonds. These two strands run in opposite directions to each other and are therefore anti-parallel. The double strands of DNA form a double helical structure.
2. The information in DNA is stored as a code made up of four chemical bases: adenine, guanine, cytosine, and thymine. The order, or sequence, of these bases determines the information available for building and maintaining an organism. These nucleotides bind through a chemical bonding process known as Watson and Crick base pairing. Adenine bonds with thymine, and guanine bonds with cytosine — a given sequence of such nucleotides will always bond with the complementary sequence.
3. In its double helical configuration, DNA is a relatively rigid molecule. This rigidity can be further enhanced by bundling several double helixes to form DNA lattices and tiles to form synthesized nanoarchitectures.
4. The Watson and Crick base-pairing principles have created predictable binding affinities in bench top applications. This knowledge of the intra- and inter-molecular physical properties of the DNA molecule enables the programming of desired interactions within the sequences to produce a customized sequence of DNA.
5. The ease in sequencing DNA based on the Sanger technique, which today has evolved into advanced automated processes, has made designer DNA strands readily available. Customized strand lengths or oligonucleotides — strands typically 100 to 200 base pairs long — can be easily ordered from various sequencing services or produced within the lab at relatively low costs with high throughput and quality.
6. Today biotechnologists can employ a library of unique restriction enzymes that can cut the DNA strand between specific nucleotides, leaving sticky ends or single stranded overhangs at the end of the double helix. These fragments can be exploited to create a recombinant molecule of DNA by inserting or removing a specific sequence of DNA, attaching a fluorescent molecular beacon, or amplifying the sequence through the polymerase chain reaction process.
7. By carefully using the recombinant tools and technologies available to genetic engineers, one can properly program a customized Watson-Crick base-paired DNA motif that will self-assemble in solution. This method of self-assembly is preferred on small scale applications due to the difficulties experienced when assembling nanoscale objects through the traditional top-down method. Assembly of DNA motifs with the aid of various branched DNA strands with sticky ends can be directed by the geometry and connectivity of the varying motifs. Once the structure is assembled a range of DNA lattices can be produced.
8. Another widely accepted bottom-up method to construct DNA nanosystems is through a process known as strand displacement or branched migration. This assembly method displaces one DNA strand and selectively replaces it with a strong complementary strand which usually consists of more Watson-Crick base pairs. This method can be utilized to correct sequence errors made during strand synthesis and DNA tile assembly, in complex logic gates, and for controlling DNA motors.

Figure 10 shows a recombinant DNA molecule with restriction enzyme cleavage and sticky end ligation. Figure 11 shows two symmetric DNA nanomotifs and the crystals grown using them — a symmetric cross motif and a three-point-star motif, with atomic force micrographs of the crystal structure and fluorescence microscopy images of two-dimensional DNA crystals assembled from the motifs.

In 1996, Winfree devised a theoretical proposal that addressed how crystal morphology and patterning can be programmed by tile design in an inherently asynchronous assembly process, addressed by the abstract Tile Assembly Model. Winfree explored how physical parameters, such as tile concentration and temperature, affect crystal growth and influence error rates, based on reversible tile association and dissociation rates. This work was built on previous efforts by Wang’s embedding of computation in geometrical tiles, showing that two-dimensional self-assembly of DNA can perform Turing-universal computation. This implies that any algorithm can in principle be embedded in, and guide, a potentially aperiodic crystallization process. In this algorithmic self-assembly paradigm, a set of molecular Wang tiles is viewed as the program for a particular computation or molecular fabrication task.

Later collaboration between Winfree and Seeman resulted in the first successful fabrication of a two-dimensional DNA lattice structure that utilized the mathematical principle of tiling. The self-named DX, or double crossover, molecule has two double helical motifs that are rigidly bound together by several single strands that are organized in a double crossover pattern forming a rigid structure of DNA. These DNA strands are oriented in a parallel direction. This method allows for the production of DNA based lattices by exploiting the use of sticky ends at four ends. These ends can then be further constructed to build up a scaffold of DNA based on the complementary binding of the Watson-Crick base pairs that correspond to each sticky end. In this way, a lattice structure can be built upon the base structure by synthesizing additional DX motifs to construct what is known as a DNA tile. These tiles can be further utilized as a scaffold for additional molecular structures.

In order to envision the tiling process, it is easy to picture various tiles with different numbers written on the sides, indicating matching rules where two tiles would stick only if their contacts matched. Additional matching interactions can be arranged in a manner that adjacent tiles can strongly hold the next one in place, but a single interaction creates a weak bond. An instantiation of the algorithmic self-assembly process uses sets of four species tiles that represent the exclusive-OR function to create a Sierpinski triangle pattern. The so-called seed structure is used to input the initial values that commence the algorithmic self-assembly process. However, it must be noted that random nucleation events may occur. Nevertheless, algorithmic self-assembly has created a means to emulate cellular automata.

Figure 12 shows the exclusive-OR cellular automaton and its implementation by tile-based self-assembly, together with atomic force microscope images of algorithmic self-assembly of Sierpinski triangle crystals.

In theory, this process allows scientists the ability to build a computer from nanoscale material with DNA tiles. The experimental success of this trial demonstrated that two-dimensional algorithmic self-assembly offers new capabilities for computation and construction, as well as a new range of physical phenomena and experimental challenges.

Error Suppression Mechanisms in DNA Self-Assembly

Molecular self-assembly is an emerging technology that will ultimately enable the fabrication of great quantities of complex nanoscale objects such as computer circuits at very low costs. Because the DNA-tile-based bottom-up assembly technique relies on the logic of programming self-assembly, it requires a situation where sticky-end binding specificity is infallible. Realistically, however, correctness of matching between tiles cannot be guaranteed due to the thermodynamics and kinetics of DNA tile self-assembly. This process alone results in occasional erroneous assembly steps. The number of assembly errors increases with the number of tile types, and accruing errors render large scale complex computation practically infeasible.

Assembly errors can be classified into three types: growth errors, facet errors, and nucleation errors. Growth and facet errors are the errors that occur on the growth front of an existing assembly, while nucleation errors deal with the spurious initiation of assemblies. A growth error occurs when a DNA tile with one or more mismatched sticky ends is embedded in the assembly. A facet error occurs on the flat surface of the aggregate when two DNA tiles attach on a growth front side by side, and thus stabilize each other’s binding. This is considered an error because the identity of these tiles may not be correct with respect to the computation being performed. Nucleation errors are similar to facet errors in that a number of tiles spontaneously assemble a cluster by stabilizing each other through binding. This then seeds ordinary, but meaningless, computation. Growth errors, facet errors, and nucleation errors all occur because of tiles that make only weak contacts with the assembly. These erroneous tiles must fall off in order for correct growth to proceed. One approach is to design the lattice such that each tile is first stabilized by the arrival of another tile before it secures itself in place.

Prior analysis predicted that the error rates of tile assembly can be reduced by optimizing physical parameters such as tile concentrations and temperature. In order to suppress different types of errors, several methods have been proposed based on the idea of increasing the amount of time required to lock in erroneously assembled tiles. Unfortunately, some of these methods cannot effectively suppress all types of errors. For example, the tile proofreading model first proposed by Winfree and Bekbolatov can correct errors in growth if an incorrect tile attaches in the next position. This error correction technique uses redundancy to correct errors. In this method, each tile is replaced in the system with four tiles, arranged in a two by two block. The compact resilient tile model as proposed by Reif attempts to reduce the increase in scale of the final pattern produced by self-assembly. While both of these methods are effective in reducing errors, they are only limited to those errors produced by growth.

However, the error suppression models Protected Tile Mechanism and Layered Tile Mechanism proposed by Fujibayashi and Murata can suppress all three error types. The functional method of suppression in these models is the control of sticky end hybridization. In these mechanisms the implementation of the DNA tiles is altered by the introduction of a structural motif protection strand and protection tiles. In this technique, the protection strand is a single oligomer that covers the input side of the tile. Each sticky end remains uncovered and it works as the toehold for initiating a branch migration process that removes the protection strand. The combination of a tile and a protection strand is called a protected tile, and foundation tile refers to the unprotected foundation tile. The output sides of all tiles are unprotected, thus the growth front always displays unprotected sticky ends. The protected tiles associate to the growth front by the exposed three-nucleotide sticky ends first, then branch migration results in strand displacement on each of the matching input arms; if both arms are matched, the protection strand is completely displaced, and it dissociates. This method undergoes Monte Carlo simulation to evaluate its suppressive properties. Surprisingly, it was discovered that the Protected Tile and Layered Tile suppression methods can prevent nucleation errors as well as growth and facet errors.

Figure 13 shows error suppression with the Protected Tile Mechanism; Figure 14 shows simulation results of growth in the original, protected and layered tile mechanisms; Figure 15 shows the three types of error in DNA tile self-assembly — growth, facet and nucleation — with mismatched sides marked in red.

(A subsection on self-assembly with DNA-based microfluidic devices — anchoring pre-assembled lattices in a microchannel so that monomer tiles arrive at constant concentration in a constant flow, rather than annealing every tile species in one pot — is omitted for length, with Figures 16 and 17; the complete text is at the source.)

DNA Origami

The idea of holding helical domains in a parallel arrangement via the juxtaposition of antiparallel crossovers has become a general principle in DNA nanotechnology, used in at least a dozen constructions. For example, it has been extended to molecules with three parallel helixes and it has been used to attach triangles rigidly to a nanomechanical device. However, these techniques do not create a generalized multi-crossover molecule with parallel helices due to the inability to have the ratio of the component short strands exactly equal.

Single-stranded origami such as William Shih’s octahedron cannot, by definition, suffer from this problem. Scaffolded origami sidesteps the problem of equalizing strand ratios by allowing an excess of helpers to be used. As long as each scaffold strand gets one of each helper, all scaffolds may fold correctly, though some might get trapped in misfolding. Because origami are easily differentiable from the helpers, separating them is not difficult — large origami stick much more strongly to mica surfaces than do tiny helpers, so excess helpers can be washed away. Single-stranded origami and scaffolded origami thus seem the best candidates for the creation of large complex structures. As Shih has observed, the geometry used for the octahedron should generalize and allow the creation of arbitrary polygonal networks.

Generalization of the parallel helical geometry introduced by double-crossover molecules is simple using scaffolded DNA origami; Rothemund has recently demonstrated the technique for the creation of six arbitrary shapes and six arbitrary patterns. Shapes are approximated by laying down a series of parallel helical domains inside of the shape. Helices are cut to fit the shape, in a series of sequential pairs from top to bottom, so that the resulting geometry approximates the shape within one DNA turn, about 3.6 nm, in the x-direction and two helical widths, about 6 nm including an inter-helix gap, in the y-direction. To make a molecular design, a scaffold is run exactly once through each helix; performed in a raster-fill manner, this creates a folding path. To hold the scaffold in this shape, helper strands are added to create a regular pattern of antiparallel crossovers.

The versatility of shapes-programmed DNA origami is achieved with a high yield in excess of 70 percent. Each shape uses 7,000-base long scaffolds requiring more than 200 DNA strands for a final molecular weight of 15,000 nucleotides. Thus, the DNA origami structure has a molecular weight that is 100 times that of the original DX model and nearly 6 times larger in geometric construction, where 50 billion copies of the pattern are created at once. With this technique, a device has been created that has the molecular weight of the component of cells that can synthesize proteins and amino acids — the ribosome. For the first time, we are now capable of self-assembling structures whose size and complexity rival that of Nature’s most complex self-assembled machines.

Figure 18 shows the design of DNA origami and Figure 19 several DNA origami folding paths.

Engineering DNA-Based Logic Gates

This branch of nanotechnology employs DNA enzymology to induce molecular behavior in solution that responds to an appropriate nucleic acid input. The goal is to make reliable DNA-based logic gates that can be used to assemble complicated logic circuits, which in turn can be used to control complex molecular devices. Strictly speaking the silicomimetic solution-phase approaches are not connected to traditional DNA nanotechnology, or Adleman’s model of DNA computing. However, there is some overlap of concepts, and all these approaches can be integrated in order to achieve complex functional behaviors.

There are two primary requirements that a DNA-based logical device has to fulfill: first, the device should have the ability to integrate the presence or absence of several inputs into a single output. Second, a device has to be designed in such a way that a limited number of simple devices can be combined into a variety of complex circuitries. This usually means that one device can communicate with other components through some kind of information transfer. Furthermore, devices that could communicate with sensors, and produce outputs for autonomous therapeutic and diagnostic devices, are of our interest, because they may one day function as silicon-free expert systems.

DNA-based logic gates are intended to perform as traditional binary logic gates, which turn ones and zeros of input into ones and zeros of output, which form the central processing units in digital computers. Recently, Seeman and colleagues at New York University have found a clever new way to tease DNA strands into mimicking exclusive-OR logic gates. In the case of an exclusive-OR gate, the rule is simple: when the same two digits enter the gate a zero comes out; two different entering digits return a one. In this latest case of DNA computing, inputs are replaced by single-stranded molecules, and how they bind with each other, base pair to base pair, dictates the operations. In essence, the collection of input molecules that are used set up the problem; once that’s done, the answer self-assembles in a single step. The near term goal is to build DNA-based computing modules and to develop nanoscopic machines that could exist in living organisms, sensing conditions and making decisions based on what they sense, then responding with actions such as releasing medicine or killing specific cells.

Logic Operation by Deoxyribozymes

This biocomputing approach is based on two libraries of nucleic acids, one consisting of an allosterically modified deoxyribozyme — nucleic acid catalysts made of DNA — and the second, its substrates. A DNAzyme is associated with gene replication only, and they exist only in the laboratory. Nevertheless, they are very powerful tools for building DNA-based nanosystems. The functions of these molecular units are essential for molecular logic gates and the seamless integration into DNA-based computing devices. These constructs are capable of carrying out simple arithmetic operations and have the capability to arrange several gates around a common substrate.

These devices have oligonucleotides — short single-stranded DNA — as both inputs and outputs. Phosphodiesterase deoxyribozymes cleave other oligonucleotides, producing shorter strands as outputs. The stem-loop of a YES molecule inhibits the catalytic module through the overlap of the stem with the substrate recognition region. Hybridization of the input to the complementary loop opens the stem to allow substrate binding to proceed. The YES gate behaves as a two-state switch, with the active state in the presence of input.

Generalized approaches have three-input gates, including NOT, AND, AND-NOT and AND-AND-NOT gates, based on the deoxyribozyme logic. These gates are generic and modular, in the sense that other deoxyribozymes could be combined in parallel into similar constructs, with the expectation of similar behavior. That means, in principle, we can construct enzymatic networks that perform Boolean calculations of any complexity. At this moment, serial connections are prohibitively slow to be used in practical devices, thus reported circuits are limited to implicit OR connectivity between individual elements.

Figure 20 gives the functional design of a DNA based logic gate and Figure 21 a simplistic rendering of one.

Deoxyribozyme-based Boolean Automata

The deoxyribozyme logic gates were applied to the construction of the first DNA-based Boolean automata capable of autonomously responding to human inputs: MAYA automata playing a game of tic-tac-toe against a human player. In tic-tac-toe there are a maximum of 4 moves by the human player when MAYA has the first move. The initial MAYA automaton played a simplified game, always claiming the center first, and the first human move is symmetry-restricted to one corner or one side move. These simplifications led to a representation of the game as a series of Boolean formulae that compute the automaton’s output in each well, based on the human inputs present in all wells. These formulae were mapped to 23 deoxyribozyme-based logic gates by arranging gates in the individual wells around a common substrate. These hard-wired automata give the human no chance to win. One, two and three input deoxyribozyme-based logic gates are allosterically modulated by 32 human-operated input oligonucleotides: 97 logic gates distributed across 9 wells which calculate automaton moves, and 32 gates display human moves by implementation of a two-color fluorogenic output system. Even though this mechanism is simplistic in nature, it has performed flawless Boolean calculations.

Figure 22 shows the basic gate structures derived from the allosterically regulated deoxyribozyme E6 for playing tic-tac-toe against a human opponent, with truth tables sufficient to ensure the human player cannot win. Figure 23 shows the first generation MAYA I DNA-based logic circuit that plays tic-tac-toe.

Robotic Bases: The DNA Robot

Illustrated thus far are various structures that can be built by DNA-based approaches, and such components can be combined into even more complex systems at a nanoscale. As an example of the integration of different DNA components, we present here an approach that will eventually lead to the design of DNA robots. In order to make such robots, we must integrate three, up to now separate, molecular functions into either the molecule itself, or into the interactions between the molecule and the environment it traverses. These three functions are sensing, information processing, and movement. In principle, DNA provides us with all these functions, and we should be able to build functional units that could be justifiably called molecular robots solely out of nucleic acids. We hope that DNA robots will enable us to approach, on a molecular scale, the important issues in the field of ordinary robotics such as evolution, learning, multi-robot interaction, self-replication, and self-repair.

Sensing devices are necessary to extract information from the environment such as existence of a specific molecular species in the solution and shape and properties of the landscapes traversed by molecules. The capability for computation is also needed to analyze these data and, in many applications, some rudimentary processing units such as the logic gate networks shown in the previous section would be enough to achieve useful functionalities.

To exhibit these capabilities, a team of scientists from Columbia University, Arizona State University, the University of Michigan and the California Institute of Technology have programmed an autonomous molecular robot made out of DNA to start, move, turn, and stop while following a DNA track. This development could ultimately lead to molecular systems that might one day be used for medical therapeutic devices and molecular-scale reconfigurable robots — robots made of many simple units that can reposition or even rebuild themselves to accomplish different tasks. The researchers constructed a trail of molecular bread crumbs on the DNA origami track by stringing additional single-stranded DNA molecules off the ends of the staples. These represent the cues that tell the molecular robots what to do — start, walk, turn left, turn right, or stop — akin to the commands given to traditional robots. It is this third function, the controlled movement of molecules through the aid of nanomotors, that will be discussed next.

DNA Nanomotors

Molecular-size motors have evolved in nature, where they are used in virtually every important biological process. In contrast, the development of synthetic nanomotors that mimic the function of these amazing natural systems and that could be used in man-made nanodevices is in its infancy. Building nanoscale motors is not just an exercise in scaling down the design of a macroworld engine to nanoscale dimensions. Many factors such as friction, heat dissipation and many other mechanical behaviors are just very different at this scale — everything is constantly moving, under kinetic energy supplied by the heat of the surroundings, and being buffeted by other atoms and molecules in Brownian motion. The concept of a single DNA molecule nanomotor was already introduced in early 2002. DNA nanomotors are synthetic biochemical devices whose motion can be controlled at the molecular scale.

DNA molecular motors will be indispensable parts for the construction of molecular robots. The motion of a robot should be well controlled by means of some molecular input, or it should be driven autonomously by cues from the environment. First approaches to encode molecular motion in DNA structures were based on reversible and input-sensitive conformational changes. For example, the first reported use of a DNA motor was a nanomechanical device which generated twisting motion along the helix axis based on the B-to-Z transition controlled by ionic strength of a solution. Then, the first molecular tweezers were driven by successive reversible branch migrations of DNA strands, and these strands were called fuel and anti-fuel. The next level in complexity were remotely controlled walkers introduced by Seeman and Pierce, based on a series of successive unidirectional conformational changes driven by strand displacement. These sequential conformational changes were microscopic analogs of macroscopic commands such as lift the first leg, drop the first leg to the next available position, lift the second leg, drop the second leg to the next available position — with a cumulative result of a translational movement of a molecule along a track. One drawback of these systems was that they were not autonomous, and that each conformational change had to be triggered separately, while one advantage was that they could have been monitored easily in bulk with fluorescence measurements. The first autonomous systems were based on nucleic acid enzymes, for example deoxyribozymes, and performed either solution phase conformational changes, or were proposed to move autonomously along a linear track over up to four steps.

A paper published in the journal Nano Letters details how researchers created the first light-powered nanomotor out of a photoreactive chemical and a short length — only 31 base pairs — of DNA. The motor looks a bit like a pair of tweezers. When ultraviolet light hits it, the photoreactive chemical causes the DNA to bend, which acts as the power stroke of the motor, opening the tweezers. Light in the visible spectrum, in turn, resets the chemical, closing the tweezers. The team from the University of Florida built a new type of molecular nanomotor driven only by photons. While it is not the first photon-driven nanomotor, the almost infinitesimal device is the first built entirely with a single molecule of DNA, offering a simplicity that increases its potential for development, manufacture and real-world applications in areas ranging from medicine to manufacturing. In the coming years, nanomotors could become a component of microscopic devices that repair individual cells or fight viruses or bacteria. Although in the conceptual stage, those devices, like much larger ones, will require a power source to function. Because it is made of DNA, the nanomotor is biocompatible. Unlike traditional energy systems, the nanomotor also produces no waste when it converts light energy into motion.

Figure 24 shows a single molecule DNA-based nanomotor driven by photons, with an azobenzene group and the stem and loop regions marked.

Nanomotors can be daisy-chained together, so that small movements on the microscopic scale add up to large movements at the macroscopic scale. In biology, muscle contraction and plant movement both result from small motors working together to create big changes. Scientists are attempting to mimic the many molecular motors that have been proven in nature. Today, biology is acting as a blueprint for the development of many DNA-based devices. One such biologically based mechanism is the spider-like-inspired nanowalker.

The Nano Walker: a Spider-like Approach

A simple cargo carrying robot was demonstrated by Gu. Spiders follow a designated path placed on a surface, picking up gold atoms as they pass over them. Such a device could be used to collect samples from asteroid or planetary surfaces. On a massive scale, they could collect mission critical materials from an exploration site.

Figure 25 is an atomic force microscope scan of walkers as they follow a track pattern placed on the surface. Each can take up to 50 steps; the body of each walker is visible as they carry cargo — gold atoms — along the designed path, with a 50 nm scale bar.

In a different approach, a nanoscale molecular proto-robot with a potential for integration with computing and sensing was introduced by Stojanovic. This design starts with a consideration of the following situation: a surface covered with substrates in a scaffold configuration is exposed to a single deoxyribozyme that will bind to its substrate, cleave it, release both products, and then bind again to another substrate, repeating the cycle, for as long as there are substrates available on the scaffold. This deoxyribozyme would move over the surface with the process called self-repelling random walk, being attracted more by substrates than by the residual product on the surface. But every loss of the contact with the surface could lead to the removal of the deoxyribozyme into the bulk solution, with experimentally determined processivity — cleaving substrates without leaving into bulk solution — in single digits.

However, combining the concepts of self-repelling walk of deoxyribozymes and multivalency led to testing assemblies with two to six deoxyribozyme legs displayed on inert bodies, that is, spiders, and the processivity was increased to up to several thousands. Essentially, the cumulative binding of multiple catalysts to substrates would attach the spider tightly to the matrix, whereas individual catalysts would still be able to rapidly cleave substrates, release products, and bind new substrates through the process of dissociation and rebinding. If density of substrates and size of legs are adjusted well, the assembly is continuously moving to new substrate-covered areas. Due to residual binding of deoxyribozymes to products, even if the spiders were surrounded by product-covered areas, they would be able to move over them by ordinary random walk, until they would find substrates again.

Importantly, directional movement of spiders can be accomplished by aligning substrates in directional paths, for example by displaying them on self-assembled structures, including origami. Further, simple computing can be introduced by logic gates as legs. The nano walker could be hybridized to repair DNA based machinery, including DNA computers, when they are being assembled, or when they are damaged from cosmic rays, for example.

Figure 26 shows the nano walker made at Columbia University: a protein molecule decorated with three legs of single-stranded DNAzymes, synthetic DNA molecules that act as enzymes and catalyze a reaction. Figure 27 shows a deoxyribozyme-based molecular walker and origami prescriptive landscape — a spider consisting of a streptavidin core with a 20-base single-stranded DNA that positions it at the start and three deoxyribozyme legs; the 8-17 deoxyribozyme cleaving its substrate at an RNA base into two shorter products so that dissociation allows legs to associate with the next substrate; the spider following the substrate track after release by a 27-base trigger strand; and a schematic origami landscape with start, track, stop and control sites and a topographical imaging marker.

Discussion

The first operating quantum computers capable of solving real-world problems will commence within 10 years and be based on ion-trap technology. This is entirely based on the amount of research resources dedicated to the problem and the fact that there appear to only be engineering challenges remaining. Atomic and ion traps require very substantial cryogenic and electromagnetic shielding systems and are not practical for space travel.

Pure photonic technologies available today have difficulty with both miniaturization and scalability. However, the amount of active work in the field makes a disruptive advance likely in the 10-year timeframe. Optical computers will likely be realized in the 20-year horizon; however, the very powerful promise of quantum computing will still have issues with photon loss in any solid state device. The 40-year horizon will see photon technologies play an essential but supporting role in distributed quantum computing. The realized systems will have radiation tolerance advantages over current semiconductor technology and are likely to augment or even replace general purpose computing devices for space travel.

Hybrid designs utilizing arrays of quantum dots and photon communication channels will be an option for space travel supercomputing on the 40-year timescale. These systems operate at attainable temperatures without cryonics, and require no more shielding than humans. It is likely that spintronics will be an essential ingredient.

Simple organic computing based on DNA tiles will be realized in the next 20 years. On the 40-year time horizon useful DNA-based devices will be essential space exploration tools. These could take the form of orbital-delivered wireless sensors searching planetary or asteroid features or for essential compounds such as high concentrations of water. DNA computers will be realized on the 40-year timeline. Their advantage over solid state devices will be the ability to repair nanoscale elements damaged in normal use or by cosmic radiation. These will not be the fastest systems in the astro-arsenal, but they may be the most robust.

Conclusion

We have presented an introduction to quantum computing and the technologies that comprise the current state of the art. In the 10 to 20 year horizon, we will see optical and DNA-based computers realized on small production scales, but their readiness level for space travel will be lacking. On the 40-year horizon four major advances in space-ready technology will be seen: devices developed for optical computing will allow an all-optical computer to augment or replace general purpose computers; optical communication will play an essential role in hybrid designs of space-based quantum computers along with quantum dots; DNA devices will perform simple distributed sensor data analyses; and fault tolerant DNA computers will be available for mission-critical analysis tasks.

(The report’s 130-item reference list is omitted here; the complete text is at the source.)