Bio-Inspired and Nanoscale Integrated Computing (Nature-Inspired Computing Series)

BIO-INSPIRED AND NANOSCALE INTEGRATED COMPUTING

BIO-INSPIRED AND NANOSCALE INTEGRATED COMPUTING EDITED BY Mary Mehrnoosh Eshaghian-Wilner

A JOHN WILEY & SONS, INC., PUBLICATION

Copyright r 2009 John Wiley & Sons, Inc. All rights reserved. Published by John Wiley & Sons, Inc., Hoboken, New Jersey Published simultaneously in Canada No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax (978) 750-4470, or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, (201) 748-6011, fax (201) 748-6008, or online at http://www.wiley.com/go/permission. Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages. For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at (800) 762-2974, outside the United States at (317) 572-3993 or fax (317) 572-4002. Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com. Library of Congress Cataloging-in-Publication Data: Bio-inspired and nanoscale integrated computing / edited by Mary Mehrnoosh Eshaghian-Wilner. p. cm. – (Nature-inspired and nanoscale integrated computing) Includes bibliographical references and index. ISBN 978-0-470-11659-3 (cloth) 1. Molecular computers. 2. Biologically-inspired computing. 3. Nanotechnology. 4. Nanomedicine. I. Eshaghian-Wilner, Mary Mehrnoosh. QA76.887.B56 2009 004.1–dc22 2009013331

Printed in the United States of America 10 9 8 7 6

5 4 3 2

1

CONTENTS Foreword

vii

Preface

ix

Contributors

xiii

1

AN INTRODUCTION TO NANOCOMPUTING 1 Elaine Ann Ebreo Cara, Stephen Chu, Mary Mehrnoosh Eshaghian-Wilner, Eric Mlinar, Alireza Nojeh, Fady Rofail, Michael M. Safaee, Shawn Singh, Daniel Wu, and Chun Wing Yip

2

NANOSCALE DEVICES: APPLICATIONS AND MODELING Alireza Nojeh

31

3

QUANTUM COMPUTING John H. Reif

67

4

COMPUTING WITH QUANTUM-DOT CELLULAR AUTOMATA Konrad Walus and Graham A. Jullien

5

DIELECTROPHORETIC ARCHITECTURES Alexander D. Wissner-Gross

6

MULTILEVEL AND THREE-DIMENSIONAL NANOMAGNETIC RECORDING S. Khizroev, R. Chomko, I. Dumer, and D. Litvinov

111 155

175

7

SPIN-WAVE ARCHITECTURES Mary Mehrnoosh Eshaghian-Wilner, Alex Khitun, Shiva Navab, and Kang L. Wang

203

8

PARALLEL COMPUTING WITH SPIN WAVES Mary Mehrnoosh Eshaghian-Wilner and Shiva Navab

225

9

NANOSCALE STANDARD DIGITAL MODULES Shiva Navab

243

vi

10

11 12

CONTENTS

FAULT- AND DEFECT-TOLERANT ARCHITECTURES FOR NANOCOMPUTING Sumit Ahuja, Gaurav Singh, Debayan Bhaduri, and Sandeep Shukla

263

MOLECULAR COMPUTING: INTEGRATION OF MOLECULES FOR NANOCOMPUTING James M. Tour and Lin Zhong

295

SELF-ASSEMBLY OF SUPRAMOLECULAR NANOSTRUCTURES: ORDERED ARRAYS OF METAL IONS AND CARBON NANOTUBES Mario Ruben

327

13

DNA NANOTECHNOLOGY AND ITS BIOLOGICAL APPLICATIONS John H. Reif and Thomas H. LaBean

349

14

DNA SEQUENCE MATCHING AT NANOSCALE LEVEL Mary Mehrnoosh Eshaghian-Wilner, Ling Lau, Shiva Navab, and David D. Shen

377

15

COMPUTATIONAL TASKS IN MEDICAL NANOROBOTICS Robert A. Freitas, Jr.

391

16

HETEROGENEOUS NANOSTRUCTURES FOR BIOMEDICAL DIAGNOSTICS Hongyu Yu, Mahsa Rouhanizadeh, Lisong Ai, and Tzung K. Hsiai

429

17

BIOMIMETIC CORTICAL NANOCIRCUITS Alice C. Parker, Aaron K. Friesz, and Ko-Chung Tseng

455

18

BIOMEDICAL AND BIOMEDICINE APPLICATIONS OF CNTs Tulin Mangir

483

19

NANOSCALE IMAGE PROCESSING Mary Mehrnoosh Eshaghian-Wilner and Shiva Navab

515

20

CONCLUDING REMARKS AT THE BEGINNING OF A NEW COMPUTING ERA Varun Bhojwani, Stephen Chu, Mary Mehrnoosh Eshaghian-Wilner, Shawn Singh, and Chun Wing Yip

Index

535

547

FOREWORD Bio-inspired and Nanoscale Integrated Computing (edited by Professor Mary Mehrnoosh Eshaghian-Wilner) is the first book in a new and exciting Wiley book series, the Nature-Inspired Computing Series. The proliferation of computing devices in every aspect of our lives increases the demand for better understanding of emerging computing paradigms. The new book series seeks to provide an opportunity for researchers to explore the new computational paradigms and their impact on computing in the new millennium. The series is quite timely since the field of computing as a whole is undergoing many changes. A vast literature exists today on such new paradigms and their implications on a wide range of applications—a number of studies have reported on the success of such techniques in solving difficult problems in all key areas of computing. The list of topics covered by the series is by no means exhaustive but it serves as a guide to the diversity of the topics covered here. It is also hoped that the topics covered will get the readers to think of the implications of such new ideas on the developments in their own fields. These fields are: Quantum Computing, DNA Computing, Genetic Algorithms, Evolutionary Paradigms, Cellular Automata, Neural Networks, Swarm Algorithms, Fuzzy Logic, Computational Synthesis, Machine Learning Techniques, Computational Methods for Biological Systems. The series will also publish books related to technologies that are relevant to nature-inspired computing: Silicon Neuron Processing, Molecular Scale Computers and NanoTech, Optics, Evolvable Hardware, Quantum Hardware, Reconfigurable Hardware, and others. Bio-inspired and Nanoscale Integrated Computing is a solid inaugural contribution that overviews some of the recent developments in the area of nanocomputing. This is an important emergent discipline which is facilitated by scientific advances in the field of nanotechnology. This book, through a number of chapters covering a wide range of topics, increases the awareness of the potential of nanocomputing as a new paradigm that holds great promise. It is well-positioned to generate more interest and concerted effort in studying the different facets of nanocomputing and applying it to a wider range of problems in science and engineering. Bio-Inspired and Nanoscale Integrated Computing can be used by scientists, engineers, graduate students, senior undergraduate students, researchers, instructors, and practitioners, who want to learn more about nanocomputing. It is definitely an excellent reference on this topic. ALBERT Y. ZOMAYA The University of Sydney Sydney, New South Wales, Australia

PREFACE The word ‘‘bionics’’ is often described as a compound of ‘‘biology’’ and ‘‘electronics.’’ Some say it was coined in the 1950s and that it originates from the Greek word ‘‘bı´ on,’’ meaning ‘‘unit of life,’’ and the suffix ‘‘-ic,’’ meaning ‘‘like’’ or ‘‘in the manner of’’–hence ‘‘like life.’’ But just like many people of a certain age, I first came to know the term when I was a child (in my case growing up in Tehran) watching the then-famous duo of American TV series, ‘‘The Six Million Dollar Man’’ and ‘‘The Bionic Woman.’’ Back then, I had no idea how much of those programs was just fantasy. Not only was I too young to know better, but I was also under the impression that America was so much more advanced than where I lived, and therefore everything must have already been possible in the United States. As I grew older and eventually moved to the United States during my early teen years, I began to realize more and more just how far removed the bionic fantasy was. The absence of those advancements I had expected to see was certainly a big disappointment, yet it motivated me to begin my undergraduate studies in biomedical and electrical engineering at the University of Southern California (USC). As part of my studies, it became apparent that computer science and engineering were key disciplines that would make the bionic fantasy a reality. I therefore majored in Computer Engineering in the USC graduate school and received a Master s degree and a Ph.D. My ultimate dream was to make an actual bionic eye. To move one step closer to that dream, I concentrated on designing ultra-dense multiprocessor VLSI chips that had the capability of massive electrooptical intercommunications. I also designed a large number of algorithms that could be mapped onto those chips for image processing and computer vision. Before long, my career took off and my work received recognition in the area of parallel processing. I published, gave talks, taught courses, and organized conferences in various areas within parallel processing. Over time, my bionic dream was diminished to a small side issue. About two decades later, while employed as a professor and department head at the Rochester Institute of Technology, I learned about the intriguing advancements that were rapidly taking place in the new fields of nanotechnology and bioinformatics. I applied for and received a fellowship at the National Science Foundation’s Institute of Pure and Applied Mathematics at the University of California Los Angeles (UCLA). There, I interacted with an interdisciplinary group of scientists who were all interested in the applications of nanotechnology to their fields of expertise. Among them were biologists, chemists, physicists, mathematicians, electrical engineers, mechanical engineers, computer scientists,

x

PREFACE

and so forth. I knew that if I could somehow get all of them to understand each other, we could then also sit and design some of the world’s most challenging devices, e.g., those that were part of my ‘‘bionic dream.’’ Towards that goal, I began working with a small group of interdisciplinary scientists, and together we wrote a joint article about various ways computing could be done at a nanoscale level. The collaboration also led to the production of some very interesting breakthrough results that were widely disseminated and publicized through various news media. Shortly after that, I was contacted by an editor for the publisher, John Wiley & Sons, who told me Wiley would be interested in a book on the type of collaborative multidisciplinary work in which I was engaged. ‘‘Bio-inspired and Nanoscale Integrated Computing (BioNIC),’’ the name I had given to my research team at UCLA, was the title that I proposed to Wiley. I proposed a collection of the latest findings of leading scientists who were working in the proposed topic area, with the intent to get one step closer to the creation of actual bionic parts. Paul Petralia, the Wiley Editor, liked my proposal, then sent it for external review for which it received very positive and high peer ratings. I began working on the book immediately; and after about three years, it is now complete. The quality of the work presented in this book is all to the credit of the outstanding group of scientists with whom I had the distinct privilege and honor to collaborate. I must mention here that this book was initially planned to contain significantly fewer chapters than what you see before you. Only through the remarkable dedication and contributions of the co-authors did this book evolve to its current size. I am immensely thankful and indebted to all of them. I invite all of you to begin reading with a special emphasis on Chapter 1. That chapter was produced primarily by a group of amazing interdisciplinary UCLA students who took a seminar course on nanocomputing that I taught. Each student studied the application of nanocomputing to their prospective fields and, based on those, they all got together and wrote the chapter. The chapter not only contains a brief but comprehensive background, but it also serves as a guide to various chapters within the book where additional information can be found. Special credit goes to Shawn Singh, who took a superb leading role among all the students that were involved. I also thank Professor Alireza Nojeh for his final review of their work. There are many additional people to whom I am grateful. First and foremost, I thank Paul Petralia of Wiley, who had the foresight, leadership, and vision to help me produce this book from a simple idea to what it is now. He is also responsible for creating the Nature-Inspired Computing Series that I am coediting with my dear colleague, Professor Albert Zomaya. This book will serve as the first in the new series and it will be followed by several other interesting titles, some of which are currently in progress. I am extremely grateful and pleased for the opportunity to be working with the renowned Professor Zomaya on this important series.

PREFACE

xi

My undying gratitude also extends to the numerous other wonderful people at Wiley and UCLA who have worked with me nonstop on this book. At Wiley, a special shout-out goes to Lisa Morano Van Horn for her outstanding production work, to George Telecki for seamlessly transitioning into Paul Petralia’s role, and to Michael Christian for his routine help with all diverse tasks. Over at UCLA, I would like to thank my administrative assistant, Rose Weaver, and all of my research assistants, including Dr. Shiva Navab, David Shen, Jon Lau, Mike Yip, and Stephen Chu, and Eric Mlinar. Finally, I don’t think this book would have been possible without the various contributions of my family. My parents, Mehdi and Molly, my brothers, Michael and Mark, and my sister, Maggie, have always supported me throughout the various stages of my life and career. I am forever indebted to them. My husband, Arthur, who is an excellent writer himself, has been a great adviser to me. I thank him with all my heart for all his valuable feedback. But most of all, I owe the most credit to my beautiful daughter, Ariana, who has been so patient and understanding about Mommy’s crazy schedule. I love her more than words can describe, and I dedicate this book to her and our family. Thank you for reading this book. Enjoy! MARY MEHRNOOSH ESHAGHIAN-WILNER Los Angeles, California March 2009

CONTRIBUTORS Sumit Ahuja, Research Assistant, Fermat Lab, Virginia Polytechnic and State University, Blacksburg, Virginia Lisong Ai, Department of Biomedical Engineering and Division of Cardiovascular Medicine, University of Southern California, Los Angeles, California Debayan Bhaduri, Research Assistant, Fermat Lab, Virginia Polytechnic and State University, Blacksburg, Virginia Varun Bhojwani, Analyst, Wachovia Securities, Los Angeles, California Elaine Ann Ebreo Cara, Department of Electrical Engineering, University of California, Los Angeles, California R. Chomko, Assistant Research Professor, Department of Electrical Engineering, University of California, Riverside, California Stephen Chu, Department of Electrical Engineering, University of California, Los Angeles, California Dr. I. Dumer, Professor, Department of Electrical Engineering, University of California, Riverside, California Dr. Mary Mehrnoosh Eshaghian-Wilner, Adjunct Professor, Department of Electrical Engineering, University of California, Los Angeles, California Dr. Robert A. Freitas Jr., Senior Research Fellow, Institute for Molecular Manufacturing, Palo Alto, California Aaron K. Friesz, Department of Electrical Engineering, University of California, Los Angeles, California Tzung K. Hsiai, Department of Biomedical Engineering and Cardiovascular Medicine, University of Southern California, Los Angeles, California Dr. Graham A. Jullien, Professor, Department of Computer and Electrical Engineering, University of Calgary, Calgary, Alberta, Canada Alex Khitun, Research Engineer, Department of Electrical Engineering, University of California, Los Angeles, California Dr. Sakhrat Khizroev, Professor, Department of Electrical Engineering, University of California, Riverside, California Dr. Thomas H. LaBean, Professor, Department of Chemistry and Department of Computer Science, Duke University, Durham, North Carolina Ling Lau, Hardware Engineer, Cisco Systems, San Jose, California

xiv

CONTRIBUTORS

Dr. Dimitri Litvinov, Director, Center for Nanomagnetic Systems, Associate Professor, Electrical and Computer Engineering and Chemical and Biomolecular Engineering Departments, University of Houston, Houston, Texas Dr. Tulin Mangir, Professor, Electrical Engineering Department, College of Engineering, Director, Nano Technology Lab, and Director, Wireless and Mobile Security Lab, California State University, Long Beach, California Dr. Shiva Navab, Staff Scientist, Broadcom Corporation, Irvine, California Dr. Alireza Nojeh, Assistant Professor, Department of Electrical and Computer Engineering, University of British Columbia, Vancouver, British Columbia, Canada Dr. Alice C. Parker, Professor, Department of Electrical Engineering, University of California, Los Angeles, California Dr. John H. Reif, A. Hollis Edens Distinguished Professor of Computer Science, Duke University, Durham, North Carolina Fady Rofail, Department of Electrical Engineering, University of California, Los Angeles, California Mahsa Rouhanizadeh, Department of Biomedical Engineering, University of Southern California, Los Angeles, California Dr. Mario Ruben, Institut fur Nanotechnologie, Karlsruhe Institute of Technology (KIT), Karlsruhe, Germany Michael M. Safaee, David Geffen School of Medicine, University of California, Los Angeles, California David D. Shen, School of Law, University of California, Davis, California Sandeep Shukla, Associate Professor, Department of Electrical and Computer Engineering, Virginia Polytechnic and State University, Blacksburg, Virginia Gaurav Singh, Fermat Lab, Virginia Polytechnic and State University, Blacksburg, Virginia Shawn Singh, Department of Electrical Engineering, University of California, Los Angeles, California Dr. James M. Tour, Chao Professor of Chemistry, Professor of Computer Science, and Professor of Mechanical Engineering and Materials Science, Rice University, Houston, Texas Ko-Chung Tseng, Department of Electrical Engineering, University of California, Los Angeles, California Dr. Konrad Walus, Associate Professor, Electrical and Computer Engineering, University of British Columbia, Vancouver, British Columbia, Canada Dr. Kang L.Wang, Raytheon Chair Professor of Physical Electronics, Director, Marco Focus Center on Functional Engineered Nano Architectonics (FENA), and Director, Western Institute of Nanoelectronics (WIN), University of California, Los Angeles, California

CONTRIBUTORS

xv

Alexander D. Wissner-Gross, Environmental Fellow, Harvard University, Cambridge, Massachusetts Daniel Wu, Department of Electrical Engineering, University of California, Los Angeles, California Chun Wing Mike Yip, Department of Electrical Engineering, University of California, Los Angeles, California Dr. Hongyu Yu, Assistant Professor, School of Earth and Space Exploration, Department of Electrical Engineering, Arizona State University, Tempe, Arizona Dr. Lin Zhong, Professor, Department of Electrical and Computer Engineering, Rice University, Houston, Texas

1 AN INTRODUCTION TO NANOCOMPUTING Elaine Ann Ebreo Cara, Stephen Chu, Mary Mehrnoosh Eshaghian-Wilner, Eric Mlinar, Alireza Nojeh, Fady Rofail, Michael M. Safaee, Shawn Singh, Daniel Wu, and Chun Wing Yip The continuous shrinking of transistors has made it possible to do amazing feats with computers, and a major theme of the microelectronics era has been ‘‘smaller is better.’’ Today, technology has already shrunk to the nanometer scale, causing many practical challenges and motivating the search for new nanoscale materials and designs. In this chapter, we present a brief introduction to the concept of nanocomputing and provide a high level overview of nanocomputing devices and paradigms. We also discuss some applications of nanocomputing such as biomedical engineering and neuroscience.

1.1. INTRODUCTION In 1959, Nobel laureate Richard Feynman posed this question to his fellow physicists: ‘‘Why cannot we write the entire 24 volumes of the Encyclopedia Britannica on the head of a pin?’’ In that lecture, aptly named ‘‘There’s Plenty of Room at the Bottom,’’ Feynman challenged scientists and engineers to imagine what could be possible using nanoscale structures. He used computing as a prime example, suggesting that wires and circuits could be shrunk to only hundreds of angstroms in size [1], making it possible to combine billions of devices to perform amazing tasks. The transistor, today’s most prevalent modern computing device, can already be manufactured as small as hundreds of atoms across. This could mark the Bio-Inspired and Nanoscale Integrated Computing. Edited by Mary Mehrnoosh Eshaghian-Wilner Copyright r 2009 John Wiley & Sons, Inc.

2

CHAPTER 1: AN INTRODUCTION TO NANOCOMPUTING

end of the microcomputing era and the beginning of the nanocomputing era. Nanocomputing could be fundamentally different from microcomputing: individual particles could play a significant role; quantum effects enter the game much more directly. Even though Feynman’s vision has been partially realized with such tiny transistors, researchers are only beginning to explore the fundamental questions: How small can we make computers? How would such computers work? How can we embrace quantum mechanics for computation? What applications are possible with nanocomputing that were not possible with microcomputing? We will explore these questions throughout the book. In this introductory chapter, we will give a brief overview of devices, paradigms, and applications of nanocomputing. Of course, we cannot include all existing ideas about nanocomputing in the introduction, or even in the entire book. Instead, we aim to inspire the reader with a variety of ideas that appear commonly in nanocomputing research. We will first define computing and nanocomputing and provide some historical context of the microcomputing era. The limitations of today’s microcomputers motivate a discussion of nanoscale devices and paradigms, many of which are detailed in later chapters. We then consider two major fields that can greatly benefit from nanocomputing: biology and neurology.

1.2. WHAT IS NANOCOMPUTING? Computing is the representation and manipulation of information. Computer games, surfing the Internet, solving complex math equations, and even verbal communication are examples of computing. While we certainly compute using our own thinking power, it is often more useful to create a machine that computes on its own so we can use it to enhance our daily lives. Indeed, our world has become dependent on machines that automatically compute for us. These ‘‘computers’’ are used for entertainment, education, safety, and a vast number of other applications, all of which require manipulation of abstract information. To build a computing machine, abstract data must eventually be represented by something that physically exists. For example, digital states (such as 1’s and 0’s) can be represented as high and low voltages on a wire. Similarly, manipulations of abstract data, such as adding two numbers, must eventually be performed by a physical phenomenon that affects the data. Therefore, to explore the world of computing, we must ask the most fundamental question: How can we use physics to represent and manipulate abstract information? Directly or indirectly, researchers from all over the world are exploring this fundamental question. This endeavor spans across several disciplines, including mathematics, computer science, physics, chemistry, and biology. Throughout this book, there are many examples of how physics can be used for computation; some of these ideas may eventually lead to more powerful computers. Nanocomputing can be interpreted literally as computing at the nanometer scale. It is generally agreed that the terms nanotechnology, nanocomputing, and

1.2. WHAT IS NANOCOMPUTING?

3

nanoscale are used when considering devices that are at least one dimension smaller than 100 nanometers (nm). Today, devices such as transistors have channels that are well below 100 nanometers in length. Eventually the size of entire computers may also be measured in nanometers. Just how small is a nanometer? A nanometer is one-billionth of a meter (109 m). Figure 1.1 shows the approximate size of various physical entities at the nanometer scale. If it were possible to arrange 10 hydrogen atoms side by side, their combined width would measure approximately 1 nanometer. A typical processor found in a modern desktop computer is roughly 10 millimeters wide and 10 millimeters long—in terms of nanometers, this is nearly 10 million nanometers in width and length! Other computers are commonly much smaller; embedded processors used today in cell phones, cars, and many other devices are as small as a fraction of a millimeter squared. Nanocomputers will be even smaller; electrons, atoms, DNA, and proteins are all nanometer scale or smaller and offer a huge variety of ways to represent and manipulate data. At first this description may seem to be simply a matter of size. For more than 50 years, computers have continued to get smaller and faster, and so it may not be obvious that nanocomputing is drastically different than microcomputing. Looking deeper, however, the nanometer size opens a new world of possibilities. Nanocomputers will be able to fit anywhere, even inside our own bodies. They may be nearly undetectable, certainly invisible to the naked eye. Millions of such computers could work together and intelligently collect data about the world. Quantum physics makes it difficult to continue using old microcomputing techniques, but it also gives us infinitely more possibilities. With all this in mind, nanocomputing can be defined as the study of devices, paradigms, and applications that surpass the domain of traditional microcomputers by using physical phenomena and objects measuring 100 nm or less. This definition clarifies that nanocomputing encompasses a large variety of challenges, ranging from effectively fabricating nanoscale devices to creating revolutionary applications for nanocomputers. In the nanoscale world, it is unlikely that computers will work the same way they work today. Figure 1.2 lists some of the novel paradigms that can be realized with nanoscale physics, roughly estimating how they may be compared to each other given today’s understanding of nanocomputing. As the figure shows, there is a vast amount of untapped potential computational power beyond CMOS logic, today’s dominant technology. Another important aspect of nanocomputing is the new set of applications that will be possible with such tiny, powerful computers. In turn, the plethora of applications raises ethical, social, and economic questions that are also of great interest. The applications and impact of nanocomputing will be discussed later in this chapter, but let us first turn our attention to the fundamental question stated above, that is, exploring how physics can be used for computation. Over the next several sections we will discuss this idea, providing a historical context and generic taxonomy of nanocomputing topics that are detailed in the rest of this book.

4

CHAPTER 1: AN INTRODUCTION TO NANOCOMPUTING

1000 nm

400−700 nm Wavelength of visible light

100−300 nm Typical virus

100 nm

Human hair (50,000 nm)

45−120 nm Modem CMOS fabrication process 700x 2−100 nm Quantum dot 3−15 nm A protein

10 nm

Virus

2−10 nm Diameter of a carbon nanotube 100x

1 nm

2 nm Thickness of a DNA strand

0.01−10 nm Wavelength of X−rays

0.1 nm

0.1 nm Hydrogen atom

DNA strand

10x

Hydrogen atom (computer visualization)

Less than 0.1 nm Wavelength of an electron 0.01 nm

Figure 1.1. Left: Size of various objects, measured on a logarithmic scale. Right: Visual depiction of some of these objects, to compare relative size. Permissions obtained for the DNA strand from CalTech. The human hair and the virus pictures were taken from the Wikipedia public domain.

5

1.3. THE MICROCOMPUTING ERA: THE TRANSISTOR AS A SWITCH

Modern CMOS circuits

Analog circuits Wave-based communication and logic

Switch-based logic

Size

Cellular and neural logic DNA and protein computing

Quantum Computing

Estimated computational power

Figure 1.2. Visualization of how future paradigms in nanocomputing may compare to today’s CMOS technology.

1.3. THE MICROCOMPUTING ERA: THE TRANSISTOR AS A SWITCH Traditionally, the most common way to use physics for computation is to cleverly control electricity. Figure 1.3 shows a simplified transistor. We can add or remove electrons from the gate. When there is no charge in the gate, the wire can easily transmit its own electrons. If there are electrons in the gate, an electric field of negative charge is created, and this repelling force makes it difficult for electrons to flow through the wire. In a sense, we can control how much current flows through the wire by controlling how much charge we put into the gate. With this physical device, an abstract 0 or 1 is represented as a low or high current on the wire. This is known as the digital abstraction. The transistor’s

Gate Insulating barrier

− − − − − − − − − − − − − − − − − − − − − − Current flowing through channel

Gate − − − − − − − − − − − − − − −

− − − − − − Channel blocked

Figure 1.3. A simplified field-effect transistor. Ideally, the gate can ‘‘switch’’ current on or off.

6

CHAPTER 1: AN INTRODUCTION TO NANOCOMPUTING

behavior represents a simple switch: the gate can allow or prevent current from flowing through the wire. This is the switch abstraction. In practice, there are many more abstractions placed on top of these two (for example, representing integers in binary form with a series of 0’s and 1’s). However, the digital and switch abstractions are particularly significant because they bridge between a physical phenomenon, moving electrons and electric fields, to an entirely abstract world, manipulating 0’s and 1’s with switches. This use of transistors is the cornerstone of modern computing. One particularly interesting achievement occurred in 1959, when both Robert Noyce and Jack Kilby independently developed the integrated circuit. With integrated circuits, one fabrication process simultaneously creates many transistors, all of them integrated on a single crystalline structure such as silicon. As fabrication techniques began to improve, it became possible to pack more transistors together. By 1965 Gordon Moore, the co-founder of Intel, predicted that the number of transistors that fit into a given area would double every 18 months due to continued improvements in the fabrication process. Following this prediction known as Moore’s Law, transistor size, speed, and power consumption have exponentially improved for almost 50 years. Today it is possible to construct hundreds of millions, even billions, of tiny transistors on a small piece of silicon the size of a thumbnail (Fig. 1.4). In turn, it has become practical to create abstract computers that use millions or billions of switches. Because the fabrication process produces all transistors simultaneously, the cost of fabricating these computers is largely independent of the number of transistors. There is typically a large initial cost, and this initial cost can be amortized over thousands or millions of processors, which can be produced cheaply. The economics of this situation is staggering—with a smaller transistor, performance improves, power consumption decreases, more abstract computation fits onto a single processor, and all this happens as the price of each transistor decreases! With this persistent exponential improvement, it is very easy to manipulate large amounts of abstract information, and computers are used for a prolific number of applications today. All of this has hinged on the fact that transistors continue to get smaller, and this has led to the general trend that ‘‘smaller is better.’’

1.3.1. Difficulties with Transistors at the Nanometer Scale Transistor sizes are already at the nanometer scale, and this causes many practical difficulties. At the time of publication of this book, many consumer products are using a 45 nm fabrication process, and 32 nm technology has already been demonstrated. At these small sizes, fundamental limitations have to be considered. Entire books have been written on the subject, and here we describe only a few such challenges. One primary example of these difficulties is a quantum phenomenon known as tunneling, visualized in Figure 1.5. Due to the wave nature of particles, electrons can ‘‘jump,’’ or tunnel, through barriers with some nonzero probability. This probability increases exponentially as the size of the barrier decreases. The size of

7

1.3. THE MICROCOMPUTING ERA: THE TRANSISTOR AS A SWITCH

1,000,000,000

100,000,000

Number of Transistors

10,000,000

1,000,000

100,000

10,000

1,000

100 1970

1975

1980

1985

1990

1995

2000

2005

Year

Figure 1.4. The number of transistors found in commercial processors. Note that the y-axis is logarithmic. This exponential trend is mostly due to the decreasing size of transistors. It is expected that very soon transistors will become as small as physically possible, which motivates the exploration of other devices that may be smaller and more powerful. Data acquired from [2].

transistors has decreased so much that in today’s tiny transistors, electrons regularly tunnel between the gate and the wire. (Fig. 1.6). Since electrons and charge cannot be controlled as easily at the nanometer scale, the transistor behaves less and less like an ideal switch. Tunneling has become part of a larger tradeoff between performance and power consumption. The size of transistors has reached the point where traditional models of transistors cannot be applied without a detailed understanding of nonideal characteristics [3]. There are many reasons that electrons can unintentionally leak across the wire, even when the gate tries to block current. Furthermore, the smaller the wires become, the more difficult it becomes for electrons to move through wires; that is, thinner wires have greater resistance. Because of this, even more power is required to push electrons through the wires quickly. Most processors today are limited to about 4 GHz, largely because power requirements beyond this speed are too costly and generate too much heat for a processor to function properly. Many creative solutions have kept transistors useful despite these limitations. For example, by placing the appropriate stress or strain on the crystalline

8

CHAPTER 1: AN INTRODUCTION TO NANOCOMPUTING

An electron wave becomes a decaying signal as it tries to penetrate a barrier.

If the barrier is thin enough, the wave can continue on the other side.

Figure 1.5. Visualization of the tunneling phenomenon. Mathematically, the wave changes into an exponential decay when it enters a region of ‘‘high potential’’—the barrier—and resumes as a wave after it exits. The probability that an electron will tunnel across the barrier is related to how much amplitude the wave has left once it exits the barrier.

structure of silicon, electrons can move through a transistor more easily. This can be done by adding materials on top of transistors that naturally want to bend, thus pulling or pushing on the silicon. The so-called strained silicon [4] has quickly become a standard technique to improve the performance of transistors at 90 nm or less. Another example is the development of better insulating materials, known as high-K dielectrics [5]. The right combination of conducting and insulating materials can reduce the amount of undesirable tunneling between the gate and channel, even when the barrier is only a few layers of molecules thick. This advancement has been the key towards 45-nm technology. In the future, it may be necessary to use multiple gates to reliably control the current along a wire. FinFETs [6] or trigate transistors [7] are two multigate variations of transistors that may take us beyond 45 nm. There are several more limitations when using tiny transistors that motivate the nanocomputing ideas presented in this book. First, the wiring that interconnects transistors is becoming a very signficant limitation for performance, power, and size of devices. There are even theoretical limitations about how much

Gate

− − − − − − − − − − − − − − − − −

Gate Thin insulating barrier

− −

− − − −

− − − − − −

−

−

−

−

−

−

−

−

−

− − − −

Figure 1.6. One of many nonideal effects in a transistor is that electrons in the gate may tunnel into the wire. This occurs more often as the thickness of the insulating barrier decreases.

9

1.4. BEYOND THE TRANSISTOR: NANOSCALE DEVICES

− − − − − − − − −

−

− − − − − −

−

− −

−

− − −

Channel length > 5 nm to 15 nm, approximately

− −

−

−

−

− −

−

−

−

−

−

Channel length < 5 nm to 15 nm, approximately

Figure 1.7. When transistors become very tiny, electrons can tunnel across the channel when the gate tries to block current flow. If the channel length is small enough, electrons will regularly tunnel in this way, and the gate would no longer effectively control current flowing through the wire.

area interconnections require as long as we connect transistors with traditional wires [8]. As we will see in the next few sections, there are many ideas in this book that reduce the limitations of wiring. Second, variations during fabrication are now becoming a very significant problem. Relative to such tiny transistors, variations in geometry or chemical concentrations can easily change or break the behavior of the transistor. This variability decreases the yield and reliability of devices. Fault-tolerant methodology (Chapter 10) is desired for computing under unreliable conditions, and new fabrication methods, such as self-assembly (Chapter 12), may be better for reliable fabrication at the nanometer scale. Furthermore, reconfigurability (Chapter 5) offers a way to keep a device useful by updating or fixing its functionality. Finally, when transistors become very small (below 5 to 15 nm approximately), electrons will be able to tunnel in a different, much more challenging way: electrons would be able to tunnel through the channel itself, even when the gate tries to block current, defeating the purpose of a gate entirely (Fig. 1.7). It is currently not clear how to overcome this upcoming problem, except to find a better nanoscale device that can behave like a switch [9].

1.4. BEYOND THE TRANSISTOR: NANOSCALE DEVICES In practice, the use of transistors has been so successful that so far it remains unchallenged as the ‘‘best way’’ to use physics for computation. However, as mentioned above, it is not clear that the transistor will continue to be the best device to use as a switch at the nanometer scale. One major facet of nanocomputing research is finding new devices that exhibit switching or other behaviors that are useful for computing. Unlike the classical transistor, these

10

CHAPTER 1: AN INTRODUCTION TO NANOCOMPUTING

devices very directly embrace the properties of quantum physics to serve their function. In this section, we briefly describe various nanoscale device technologies, referring to the specific chapters where topics are discussed in more detail. It should be noted that this introductory material is not intended to be a comprehensive list of nanoscale devices; such information can be found in later chapters. In fact, this section only describes a mere fraction of the devices that are being explored at the nanometer scale. Instead, the purpose of this section is to give an intuitive understanding for several common aspects of nanoscale devices.

1.4.1. Molecular Devices In general, there are a huge variety of molecules and structures that can be explored (for example DNA, proteins, rotaxanes, nanotubes, and more) [10]. In some sense, atoms and molecules are just highly complicated toy blocks: there are an infinite number of ways to assemble molecules into something useful, limited only by the creativity of future research. Molecular structures can be used to create very tiny switches, ranging from 1 to 10 nm in size. One possible approach is to control how easily electrons can flow through the molecule, very much like a transistor, but with different underlying physics (e.g., [11]). Another possible approach is to control how light is absorbed or scattered by the molecules (e.g., [12]). These interactions with molecules can be controlled in many different ways, for example, by applying a nearby voltage or by changing the structure of molecules. Molecular switches and molecular computing are discussed further in Chapter 11. A big challenge with molecular switches—and many nanoscale devices—is to effectively fabricate and interconnect them to perform complex logic functions. In an attempt to circumvent these problems, one proposed molecular device is the NanoCell [13]. The NanoCell tolerates defects and variability that occur during self-assembly fabrication. To provide reliability, the NanoCell depends on postfabrication ‘‘training’’ to create the desired logic function. This approach is interesting for two reasons. First, the logic function of the NanoCell can (ideally) be reconfigured instead of permanently fixed; second, it allows the use of larger and fewer wires to connect between different cells. The function implemented by a single cell would be equivalent to using many transistors, thus simplifying the arrangement of large-scale computations.

1.4.2. Nanotubes One interesting class of molecular devices is nanotubes, particularly carbon nanotubes. Recall that pure carbon has two common crystalline forms: diamond, where carbon atoms form a three-dimensional structure; and graphite, where carbon atoms form flat sheets that can easily slide and peel from each other. A single-wall carbon nanotube (Fig. 1.8) can be visualized as a single sheet of graphite rolled into a tube (though it is not created in this way), with a diameter of only a few nanometers.

1.4. BEYOND THE TRANSISTOR: NANOSCALE DEVICES

11

Figure 1.8. Visualization of carbon nanotubes (CNT), an exciting class of molecular devices. CNTs can be visualized as a sheet of graphene (top) rolled into a tube, though they are not created this way. Note that these two nanotubes have slightly different configurations. Various configurations of nanotubes can result in drastically different physical properties. Images created by Gabriele Nateneli.

12

CHAPTER 1: AN INTRODUCTION TO NANOCOMPUTING

Carbon nanotubes have very interesting mechanical and electrical properties. Mechanically, they are extremely strong and versatile. The tensile strength and stiffness of carbon nanotubes are extremely high, especially relative to their weight. Also, two tubes arranged with one inside the other can have a very low friction interface, similar to the way two flat sheets of graphite can very easily slide over each other. Therefore, two nanotubes can have very efficient telescoping and rotation motions, useful for nanomachines [14]. Electrically, a nanotube can potentially behave as a ballistic conductor. This means that an electron travels through the tube with small, quantized levels of resistance. The typical levels of resistance are much lower than traditional conductors. Nanotubes can exhibit properties of a metal or a semiconductor, depending on how the sheet of graphite is rolled into a tube. It has even been suggested that nanotubes can behave like a waveguide, guiding the wave-like properties of an electron similar to the way electromagnetic (optical) waves are guided through a fiber-optic cable [15]. All of these properties are being investigated for future switches and wires. In fact, switches, wires, and support structures have all been demonstrated with carbon nanotubes, but, as with many nanoscale devices, the ability to fabricate a practical nanoscale device with nanotubes and nanowires is still an open challenge. Carbon nanotubes are discussed further in several chapters in this book. See Chapter 2, Chapter 12, and Chapter 18.

1.4.3. Quantum Dots and Tunneling Devices Many quantum phenomena occur when confining electrons to a very small space, such as the nanoscale range. For example, an electron confined to a small area can only have a select few discrete levels of energy, similar to the discrete levels of energy that an electron may have as part of an atom. When a group of electrons is confined in all axes of movement (i.e., in three dimensions), a quantum dot is formed. Similarly, a quantum wire is a group of electrons confined along a 1-dimensional line, and a quantum well restricts electrons to a 2-dimensional plane. These structures can exhibit properties similar to electrons in atoms or molecules, even if there is no nucleus of protons and neutrons. Their properties can be fine-tuned with more freedom than atoms or molecules, making them very interesting structures to use for computing. Often, the phenomenon of tunneling, described previously, is combined with quantum dots, wires, and wells to create useful devices. This is in contrast to traditional transistors, where tunneling is very undesirable. Three such nanoscale devices are the resonant tunneling diode (RTD), the single electron transistor (SET), and quantum-dot cellular automata (QCA). An RTD is a device that has a quantum well where electrons can be confined; therefore, electrons in this region can assume only a few possible discrete energy states. When the energy of an incoming electron is close to one of these ‘‘resonant’’ discrete energy states, the electron can tunnel through with high probability. This device can emit extremely high frequencies, in the hundreds of GHz, making it interesting for

13

1.4. BEYOND THE TRANSISTOR: NANOSCALE DEVICES

high-speed applications. RTDs can also be arranged to perform logic functions, digital or otherwise. For example, RTDs have been used to implement cellular automata and cellular nonlinear networks [16, 17], two paradigms described below. A single-electron transistor, or SET [18], operates on a principle similar to a conventional transistor: a gate can control the flow of electrons through a channel. However, unlike the classical transistor, in a SET the flow of a precise number of electrons is controlled. The device consists of a quantum dot between two barriers. When the gate has a negative electric field, the properties of the quantum dot are changed, effectively preventing electrons from entering (Fig. 1.9). When the gate does not block the flow of electrons, the space between two barriers accepts only a few electrons, typically allowing single electrons to tunnel through one at a time. In addition to quantum phenomena, an important mechanism that is generally dominant in SETs is the so-called coulomb blockade, which is essentially a classical effect, arising from the fact that charge is not continuous, but comes in packets of one electron each. The mutual repulsion of individual electrons, when confined to very small regions, leads to this effect. Currently, the smallest SETs are just as large as transistors, but it is expected that SETs will be able to shrink well beyond the limits of classical transistors. RTDs, SETs, quantum dots, and many other related devices are discussed further in Chapter 2. Another interesting use of quantum dots is in quantum-dot cellular automata (QCA) [19]. A single QCA cell is a container that has several quantum dots. Electrons in this container tunnel between the dots in order to try and find the ‘‘ground state,’’ that is, the state where the cell is at its lowest energy. A QCA cell has only two stable states, as shown in Figure 1.10. With two states, a QCA cell can realize the digital abstraction (i.e., logic 0’s and 1’s). However, there is no switching behavior in this concept. Instead, QCA are based on the property that adjacent cells prefer to have the same ground state. At the inputs, the cells can be constrained. Depending on how cells are arranged, the constrained inputs will propagate in

Gate

Gate − −

−

−

−

−

−

−

−

−

− −

Two tunneling barriers

−

−

−

−

−

−

− −

− −

−

−

−

Effectively one thick barrier

Figure 1.9. Conceptual illustration of a single-electron transistor (SET). A quantum dot (small confined space containing electrons) exists between two tunneling barriers, and electrons can tunnel in and out of the dot, one at a time. When the gate has electrons, the quantum dot changes and no electrons can flow from one side to the other.

14

CHAPTER 1: AN INTRODUCTION TO NANOCOMPUTING

0

1

Figure 1.10. Depiction of quantum-dot cellular automata (QCA). Each cell has several quantum dots (in this case five). A cell can have two possible states, where electrons are diagonally oriented. When the input value is changed, the change propagates over time, this particular arrangement of cells represents a logic function that inverts the input.

different ways, allowing for many interesting logic functions. Since there are no wires interconnecting various cells, they can be arranged very compactly, in turn allowing for compact logic functions. Note that quantum dots are only one of serveral ways to implement QCA cells. QCA are discussed in Chapter 4.

1.4.4. Spin Devices Electron spin is another interesting quantum effect that can be used to create nanoscale switching devices. Various particles can have different types of spin, but electrons in particular can have only two types: spin up and spin down. This is a natural way to introduce the digital abstraction. Furthermore, electron spin is a main nanoscale property that results in macroscopic magnetic fields. For example, if most of the electrons in a metal object assume a polarized spin state (either all spin up or all spin down), the metal object will be magnetic. One interesting phenomenon that is a result of the relationship between magnetism and electron spin is the magnetoresistive effect: the resistance of some materials can change depending on the surrounding magnetic field. Magnetoresistance is already widely used as the mechanism to read data from a disk drive that stores information magnetically. Manufacturers are also considering the possibility of magnetic random-access memory (MRAM), which would use magnetoresistance to implement nanoscale memory cells. MRAM may have a number of advantages over other types of memory storage. It is expected to have the high storage density of today’s dynamic RAM technology, while providing the high speed and power savings of today’s static RAM technology. Magnetoresistance can also be used to create a switching device. This sort of switch is called a spin transistor, or transpinnor [20]. Recall that a classical transistor uses an electric field to make it difficult for electrons to travel across the wire. Similarly, a spin transistor uses magnetoresistance to drastically increase the resistance of the wire, effectively blocking current like a switch. Magnetic storage is discussed in Chapter 6, and spin devices are discussed further in Chapters 7 and 9.

1.5. BEYOND THE SWITCH ABSTRACTION: NANOSCALE PARADIGMS

15

1.5. BEYOND THE SWITCH ABSTRACTION: NANOSCALE PARADIGMS The use of switches has fundamental limits. At some point, researchers may achieve a switch that is plainly as small as possible. This would mean that the exponential decrease in size of transistors would stop—the end of Moore’s Law. It would be desirable to find a new way of continuing Moore’s Law, not in the literal sense that transistors could get smaller, but rather that technology could continue to exponentially improve. Furthermore, the complexity of interconnecting switches is a fundamental limitation; even today, the wires are becoming the limiting factor when making high performance nanoscale transistors. In fact, there is no indication that switches, binary logic, or transistors are the best way to compute. This motivates the search for entirely new paradigms of computing that could eventually replace the digital and switch abstractions. Of course, the common thread in the ideas we consider is that they can be realized at the nanoscale level. Here we briefly describe some of the major paradigms of computing that are part of nanocomputing research, as well as mention the corresponding chapters where they are discussed further. As before, this section is not intended to be comprehensive; instead it aims to inspire the reader by illustrating some novel approaches to computing and how drastically different they are than today’s computing technology.

1.5.1. Cellular and Neural Logic One paradigm is the use of emergent properties. The idea is to use a large number of extremely simple processors. Alone, each processing element can be extremely small, and it can do only a limited number of trivial functions. However, powerful computers ‘‘emerge’’ from a group of such processors. Cellular automata, cellular nonlinear networks, and artificial neural networks are major examples of this paradigm. Cellular automata (CA) [21, 22] can be understood as a regular grid of identical cells, where each cell changes its state depending on its own state and the state of its neighbors (Fig. 1.11). Cellular nonlinear networks (CNN) [23] are similar to cellular automata, the main difference being that each cell in a CNN is an analog processor. Neural networks [24], unlike CA or CNN, use simple units that simulate the behavior of biological neurons. Figure 1.11 shows an example of how a behavior can emerge from a cellular automaton. At each step, every cell changes depending on the previous state of its neighboring cells. The pattern shown in this figure repeats every four steps, but gradually moves diagonally as well. This diagonal movement is a property that emerges from the group of cells. The rules that define how all cells behave are very simple, but the result is a rich, complex world of emergent properties that are being studied by many mathematicians and scientists and can be used for computation. In nanocomputing, the idea of having a huge number of very simple nanoscale structures is appealing for many reasons. The challenge of how to fabricate such

16

CHAPTER 1: AN INTRODUCTION TO NANOCOMPUTING

Figure 1.11. Example of a simple cellular automaton. Each cell can be ‘‘on’’ (black) or ‘‘off’’ (white). Depending on its neighbors, a cell may turn on or off in the next time-step. This specific example shows a ‘‘glider,’’ a structure that emerges from rules defined by the famous ‘‘Game of Life’’ by John Conway [25]. As time goes forward, the glider moves diagonally. More complex cellular automata can compute anything that a traditional computer can, and possibly more.

a computer becomes much easier because the same nanoscale structure can be repeated in a regular pattern. Most of the ideas in this paradigm are also faulttolerant, that is, able to handle a few defective cells or neurons. This alleviates the problem of variability when fabricating nanoscale devices. Their regular structure usually implies that they can perform different functions depending on the context, instead of being permanently hard coded with a fixed function; in other words, such computers are highly reconfigurable. Most importantly the potential computing power that is available with emergent properties is immense and only beginning to be explored. Even with the limited understanding of emergent properties, this paradigm already has many applications. Cellular automata and cellular nonlinear networks have been mostly used for image processing applications due to the highly parallel nature and intuitive correspondence between each simple processor and pixels on an image. Neural networks have been extensively studied for their applications in artificial intelligence and are useful practically anywhere uncertainty is encountered in computation. It has also been shown theoretically that cellular automata and neural networks can do anything that today’s computers can do [26, 27]. With all this in mind, one of the main challenges of this paradigm is to find a way to harness emergent properties for a wider variety of applications. Nanoscale devices that implement cellular automata, cellular nonlinear networks, and neural networks are actively being researched. NanoCells, quantumdot cellular automata (QCA), and RTDs, described in the previous section, are just a few possible ways to realize this paradigm. Quantom-dot cellular automata are discussed in Chapter 4, and nanoscale neural networks are discussed in Chapter 17.

1.5.2. Wave Computing Waves are an elegant but complicated way to communicate and manipulate abstract data. One of the most powerful features of waves is the phenomenon of diffraction, or the behavior of light as it propagates around objects or through a nonuniform medium. Perhaps the best known example of the power of diffraction

1.5. BEYOND THE SWITCH ABSTRACTION: NANOSCALE PARADIGMS

17

is seen—literally—in holography. To display a hologram, light waves are diffracted through patterns that were previously recorded. The diffraction of light actually reproduces all the waves of light that were originally recorded. Because of this, visual holograms are well known to have accurate details and amazing realism. Holography has found many other important engineering applications because diffraction can manipulate light waves in a flexible, powerful way. Equally important is the superposition of waves. Consider two waves that are traveling in opposite directions (Fig. 1.12). The waves continue with the same direction and speed, unaffected by each other. However, if desired, one could measure the intensity of the point where both waves cross. The propagation of the waves remains unaffected, but the intensity measured at a point where two waves overlap would be the sum of both waves, a result of constructive or destructive interference. This provides a convenient way to overcome the significant limitation of wiring: use waves for communication instead of particles. Because of superposition, waves can cross over each other without destroying the information being carried. In addition to guided waves, one could also use waves in free space, removing dependence on wiring. This may seem like a small matter at first, but as shown later in this book, it allows for significant improvements in theoretical algorithmic performance of computations. Note that improving algorithmic performance is usually more beneficial than simply making a processor ‘‘smaller and faster.’’

Figure 1.12. Visualization of how two waves cross. Unlike wires carrying an electrical signal, waves can occupy the same space while propagating. However, even though propagation over time remains unaffected, as they cross, the waves do interfere.

18

CHAPTER 1: AN INTRODUCTION TO NANOCOMPUTING

In addition to being used for communication, waves can also be used for computation by using interference. For example, constructive and destructive interference can result in either a high intensity or low intensity—introducing the digital abstraction without any switches. Furthermore, several waves can be combined at a single point, an occurence that can be advantageous over traditional logic that requires many transistors to handle many inputs. By combining the benefits of waves over wires with the functionality of waves over transistors, many limitations, theoretical and practical, can be overcome. The visual portion of the electromagnetic spectrum has wavelengths on the order of hundreds of nanometers, slightly larger than the nanoscale level. The principles of diffraction and interference, however, apply to any type of wave, including X-rays and electrons that have nanoscale or smaller wavelengths (recall from Fig. 1.1). Another useful nanoscale wave, known as a spin wave, occurs when the spin state of previous electrons affects the spin state of nearby electrons, causing a propagation of the change in magnetic field (recall that magnetism is the macroscopic property of spin). In addition to the many benefits of wave computing described above, a key benefit of spin waves is that they can conveniently communicate with electronic devices as well. Spin waves for computation are described in Chapters 7, 8, 9, 14, and 19.

1.5.3. DNA and Protein Computing DNA and protein are nanoscale molecular structures found in almost all existing biological life that we know. Recall that DNA is essentially a sequence of four primitive molecular structures: adenine (A), cytosine (C), guanine (G), and thymine (T), attached to a molecular ‘‘backbone.’’ The main property that can be exploited for computing is that adenine bonds only to thymine, and cytosine bonds only to guanine. This means that a sequence of these base pairs has exactly one complementary sequence that will bond to it. By setting up specific sequences of DNA, many clever interlocking ‘‘tiles’’ can be created, and the way these tiles interact is used for computation. Proteins are complex molecules comprised of a string of amino acids. Biologically, the sequence of amino acids that create a protein is defined by a sequence of DNA. Various proteins can interact to perform useful computations, for example, by exploiting the way a protein structure folds. Proteins are much more complex than DNA, and their use for computation has so far only been simulated [28]. The power of this paradigm is the principle of constraint satisfaction. Here, instead of representing abstract operations as physical phenomena, abstract rules are enforced (in this case with molecular structure), and physical phenomena (in this case, bonding between structures) do their best to find the lowest state of energy within the constraints. Performing constraint satisfaction in this way makes it possible to compute many things that are otherwise very difficult. The best example is a demonstration of DNA computing to solve the Hamiltonian Path Problem [29]. This is a well known problem in theoretical computer science

1.5. BEYOND THE SWITCH ABSTRACTION: NANOSCALE PARADIGMS

19

for which the best known solutions currently take exponential amounts of time. Because of this high complexity, only very small, trivial inputs can be solved by a traditional computer. To solve a large exponential problem on a traditional computer can take years, or even decades, even with all the computing power available in the world! Many real world problems are also exponentially difficult, and being able to quickly solve these problems would profoundly impact the world. While DNA computing still performs an exponential amount of computation, by using constraint satisfaction of nanoscale physics, this paradigm can quietly bypass many of the limitations of traditional computers, allowing the solution of the Hamiltonian Path Problem to be computed in a tractable amount of time. Note that constraint satisfaction is implicit in all physical phenomena used for computing. For example, a QCA cell in Figure 1.10 had two stable states because of the way electrons were constrained within quantum dots. The difference here is that the constraint itself is used for computation, rather than to make devices that can be used for computation. Another place that constraint satisfaction is useful is for self-assembly. By specifying tiles of DNA to connect in certain ways, the DNA can automatically assemble itself into structures that satisfy the constraints. DNA self-assembly has been demonstrated as a way to fabricate nanoscale structures [30, 31], which can then be used for other purposes (e.g., as a template to fabricate other integrated devices at the nanometer scale). The challenge with DNA and protein computing is to manage these complex molecules. Even though DNA computing solves the Hamiltonian Path Problem, extracting the computation from the reactions takes many hours of manual effort, and the constraints to set up do not scale well. For proteins, it is not yet fully understood how they fold to develop complex structures. The number of permutations with sequences of base pairs or amino acids can be astronomical, and finding sequences that result in useful structures is like trying to find a needle in a haystack. As future research overcomes these challenges, DNA and protein computing may become an essential paradigm to solving very difficult problems. Such topics are discussed further in Chapters 13 and 14.

1.5.4. Quantum Computing Further on the horizon of nanocomputing is the very powerful yet challenging field of quantum computing [32]. Recall that the fundamental question we have been discussing is how physics can be used for computation. All the ideas discussed above, even though they use properties of quantum physics, are only used to represent intuitive, essentially ‘‘classical’’ abstractions, such as digital 1’s and 0’s. Quantum computing, on the other hand, uses the general principles and mathematics of quantum mechanics as the abstraction itself. In this paradigm, the leap from physics into an abstract world is accomplished by a qubit: the quantum analogy to the digital abstraction. Recall that a classical bit can have one of two possible states, usually denoted as 0 and 1. A qubit also has two such states, often denoted as |0S and |1S, but in this case the qubit

20

CHAPTER 1: AN INTRODUCTION TO NANOCOMPUTING

actually is a combination of both states simultaneously! This combination of two states, however, is something that cannot be measured directly. When trying to observe the state of a qubit, we receive a |0S or |1S with some probability. This probability is the actual information contained by a qubit, and it is almost as if nature teases us by making this information impossible to measure. One of the key tasks of quantum computing is to manipulate this hidden information in such a way that it is meaningful to measure the qubit as only a |0S or |1S. The states |0S and |1S are actually just one ‘‘frame of reference’’ in understanding the actual underlying quantum system. One of the interesting powers of quantum computing is that we can freely decide which frame of reference we want in which to manipulate the qubit. For example, we could view the same qubit as a combination of |+S and |S, two other states that give us a different way of looking at the same qubits. Even more peculiar, two or more qubits may be completely unrelated in one frame of reference, but in another frame of reference, the qubits become entangled. This means that a change in one qubit will unavoidably affect the other qubit, and even though this complicates matters, it allows a powerful way to manipulate multiple qubits. Often, a useful quantum circuit first manipulates qubits in one frame of reference, where they are entangled, and then uses another frame of reference where the state of the qubits can be observed. Perhaps the best known example of the power of quantum computing is its use in finding the prime factors of a given number. Traditional algorithms can take extremely long for large numbers. A quantum algorithm known as Shor’s Algorithm [33] uses quantum computing to factor prime numbers. A physical implementation of this algorithm has been demonstrated using 7 qubits, triumphantly factoring the number 15 into the prime numbers 5 and 3 [34]. While the number 15 is not large and it seems like a trivial task that could have been done with any other computer, the real landmark of this result is to demonstrate that quantum computers can indeed work as theoretically proposed. With every next qubit, the amount of hidden information in a quantum system effectively doubles. With 7 qubits, there are 128 hidden ‘‘numbers’’ that represent a combination of 128 different states. With 20 qubits, there are more than a million such hidden numbers. It might take 30–40 qubits to represent computations that exceed the potential of traditional computers, and each qubit could possibly be represented by a single nanoscale particle! While this is currently a distant dream, the foundations towards realizing this dream are being studied extensively today. Despite this awe inspiring amount of power that seems possible with quantum computation, there are many daunting challenges to be addressed before quantum computing becomes more practical. First, physically implementing a quantum computer is a tricky task. While it would be ideal to isolate a single quantum system in reality as we can do mathematically, in practice a quantum system also interacts with the rest of the world. Therefore, it is difficult to keep the coherence of a quantum system, where coherence is a measure of how long the quantum system can stay intact before it gets disrupted by the surrounding environment. On the other hand, quantum phenomena such as photons of light

1.6. BIOMEDICAL APPLICATIONS

21

have a good coherence, but then it becomes difficult to get the photons to interact at all. Another problem is the difficulty of understanding how to develop algorithms for quantum computation. Some algorithms have been proposed that use quantum computation, and a few general computing framework are being proposed for using qubits in a practical setting. Chapter 3 gives a detailed history of the contributions in quantum computing as well as a discussion of its theoretical and practical limitations.

1.6. BIOMEDICAL APPLICATIONS Recent developments in the field of nanocomputing have laid the groundwork for technology that will revolutionize modern medicine. The most important biomedical research in the latter half of the twentieth century, which culminated in the publication of the human genome, was driven by an understanding of DNA, our genetic code. Similarly, nanotechnology has the potential to usher in an age of nanomedicine, creating a paradigm shift in the way we study and treat disease. This technology will not come without a heavy price. There are obvious financial impediments and technical challenges, but moral and ethical concerns will also play an important role in the development of this field. An excellent comparison can be drawn with genetically modified foods. A significant amount of the produce and livestock grown in the United States has been subject to genetic engineering. While many consider these modifications to be safe, some are still skeptical. Various nations, particularly some in the European Union, are hesitant to embrace such technology because of a fear that genetically modified foods are inherently unsafe and may damage local ecosystems. Some say nanomedicine may suffer a similar fate. Will governments and health care professionals trust and endorse this technology? Will individuals be comfortable with nanoscale devices circulating through their bodies? Regardless of the public’s willingness to accept nanomedicine, few will dispute its potential to revolutionize the biomedical research. By providing scientists with new techniques for targeting and attacking virtually every human ailment, nanocomputing will usher in an age of medicine in which physicians and scientists can treat disease at a molecular level and attack it in a way never thought possible. As nanotechnology provides more versatile tools, the rules of engagement for diseases will change. Physicians and scientists will no longer be hindered by the small size and tremendous complexity of the human cell, but rather utilize these features to develop therapies that are more specific and effective, producing better outcomes with fewer side effects.

1.6.1. Vaults The future of nanocomputing knows no bounds and its merger with biomedical research provides unlimited pathways to discovery. It is difficult to imagine an area in which there is more promise and a greater potential to revolutionize the

22

CHAPTER 1: AN INTRODUCTION TO NANOCOMPUTING

scientific field. It is also important to emphasize the importance of cooperation between scientists, physicians, and engineers to ensure the success of biomedical and nanotechnology related research. Perhaps the most intriguing development in this field was the discovery of nanoparticles called vaults. Groundbreaking work on vaults was performed at the University of California, Los Angeles, where these nanocapsulses have fascinated scientists since their discovery [35]. Current studies have shown that vaults are found in all eukaryotic cells and are composed of protein and RNA [36]. Through precise genetic manipulation, scientists predict that vaults may be used as structural support for nanomachines as well as integral parts of nanocircuits. Perhaps most appealing is the potential of vaults to serve as vehicles for drug delivery. These nanocapsulses may one day deliver precise amounts of drug to specific cells in the body, increasing their efficacy and eliminating the potential for certain adverse reactions. While this type of technology seems to be straight out of a science fiction film, it is indeed very real and has a tremendous potential to usher in the age of nanomedicine. Vaults may also be used as biological sensors, detoxification centers, and aid in environmental restoration [36]. Equally important will be their contributions to biomedical research as a whole. It is impossible to predict the full potential of vaults but they may revolutionize drug delivery, treatment of disease, and fundamentally change the way we practice medicine. Imagine for a moment a day in which vital signs, blood chemistries, and even disease progression can be monitored remotely by nanomachines. These safe and affordable nanorobots would be capable of transmitting data to a local physician and may even calculate complete blood counts, cholesterol levels, and search for invading pathogens. Some speculate that such robots could also be used to treat heart attacks and strokes by analyzing and neutralizing blood clots that pose a threat to the patient. Nanotechnology can provide physicians with more accurate and less invasive techniques for treating everything from the common cold to the most severe and debilitating diseases. Medicine would never be the same.

1.6.2. Molecular Motors In analyzing the problem of providing power for future nanocomputing devices, researchers are exploring the use of molecular motors. These motors, instrumental in the functioning of biological systems such as muscle contraction, will allow for the movement of nanorobots within organisms. All motors consume a form of energy to perform work; in the case of molecular motors, it is some form of chemical energy, such as ATP [37]. Molecular motors are attractive because they are smaller and more efficient than any other man-made motor [37]. Numerous molecular motors exist, the most well-known being the proteins myosin and kinesin. Myosin lies along actin filaments in muscle cells and utilize a single ATP molecule per cycle to perform a power stroke [38]. Kinesin carries cargo in the intercellular space and uses 1 ATP to move 8 nm. The development of effective and reliable molecular motors will be essential for the utilization of nanorobots in biomedical applications.

1.6. BIOMEDICAL APPLICATIONS

23

A focal point of such research is treating motor neuron diseases, such as Amyotrophic Lateral Sclerosis (Lou Gehrig’s Disease) and other types of atrophy [38]. Motor neuron diseases typically result in the degradation of neurons that control voluntary muscle, which are critical in performing tasks such as speaking and swallowing. Researchers have discovered a mutation in a molecular motor gene that leads to the buildup of improperly folded proteins in the cell. Many hypothesize that nanorobots and molecular motors may prove useful in preventing such degradation by restoring normal function to the cell and preventing the buildup of protein [37]. Scientists are currently attempting to construct nanoscale devices for this application, but they face many challenges. By studying molecular motors, they hope to discover ways for powering and mobilizing future nanodevices.

1.6.3. Nanorobots Based on the existence of vaults, it is clear that nature has created its own nanoparticles. But what about man-made nanomachines? As nanocomputing advances, the field of nanorobotics is sure to progress as well. Approximately 10 years ago, the first theoretical design of a nanorobot for medicinal purposes was presented to the scientific community. The device utilized 18 billion precisely arranged atoms to form a diamonoid vessel with active pumping capabilities [41]. This has the potential to deliver over 200 times more oxygen to tissues than red blood cells. Theoretical designs also exist for synthetic white blood cells that are able to digest blood-borne pathogens. These nanorobots would have the ability to operate faster and more reliably than naturally occurring white blood cells. Other designs include nanorobots with platelet functions that will allow hemostasis in as little as a single second. This complex machine would be invaluable in treating patients with severe hemorrhaging, especially in traumatic injuries. Perhaps most intriguing is the idea of a chromallocyte, a hypothetical mobile repair nanorobot capable of performing chromosome replacement therapy (CRT) [41]. This process involves the replacement of the entire chromatin content of a living cell with a prefabricated set of error-free chromosomes. This may allow for the treatment of entire organs such as the liver or heart and will without a doubt revolutionize the way we treat disease. These nanomachines will be the core of nanocomputing and nanotechnology’s biomedical applications; they represent a fundamental change in the way engineers and doctors will communicate. Indeed, it is essential for researchers on both sides of this fascinating technology to exchange ideas and strategies if they are to fully utilize the potential of nanotechnology. Nanorobotics is discussed in detail in Chapter 15.

1.6.4. Pharmaceuticals Pharmaceuticals are a multibillion dollar a year industry, evolving daily with the discovery and patenting of new drugs. Developers are constantly seeking stronger and more effective medicines that will also reduce side effects. Nanotechnology and

24

CHAPTER 1: AN INTRODUCTION TO NANOCOMPUTING

nanocomputing stand as beacons of hope for fulfilling these goals as they encompass several areas of pharmaceuticals, including ‘‘discovery, development, delivery and even post-delivery’’ [39]. Currently, several short- and long-term projects are underway to revolutionize the industry, as well as talks with large pharmaceutical corporations [39]. The National Cancer Institute has also created a nanotechnology branch to allow companies to expedite the processing of their drugs. Presently, many of the benefits achieved by this technology are decreased toxicity and reduction of side effects [39]. Two anti-cancer drugs, Doxil and Abraxane, have had their adverse effects reduced nanoformulation. Other applications include improved targeting of drugs by both oral and parenteral means [40]. These present developments are minuscule compared to the limitless longterm applications of nanocomputing and nanotechnology. Three crucial applications are in the areas of design, delivery, and drug monitoring [40]. Monitoring the efficiency of pharmaceuticals remains an persistent obstacle to both pharmaceutical corporations as well as medical practitioners. The use of nanorobots composed of ‘‘diamondoid nanometer-scale nanosensors’’ may allow imaging after drug delivery [41]. This would enable physicians to consistently monitor patients and evaluate the efficacy of certain medicines over a broad spectrum of individuals. Additionally, by using recently pioneered nanodelivery systems, several drugs may be combined into a single ‘‘package.’’ [42].

1.6.5. The Future of Biomedical Nanotechnology The future of nanotechnology is bright and every day new and important advancements are made in the field of nanocomputing. The merger with biomedical research will bring in a new age of scientific development unlike anything we have ever seen. Like the biotechnology revolution of the 1960s and 1970s, biomedical nanotechnology will revolutionize research and provide an almost infinite supply of techniques for treating the most challenging ailments. Even the simplest tasks may be delegated to nanomachines, which make fewer mistakes and will monitor parts of the human body not possible by physicians. The brain, heart, liver, kidneys, and other vital organs may be under the constant watch of millions of nanorobots that can take precise and accurate measurements in real time. This data can be sent to a local computer where it is processed and transmitted to a healthcare professional for analysis. Doctors will change their approach to treating disease, and computing in nanotechnology will make diagnoses more accurate, treatments more effective, and lives more fulfilling. The technology is real. The potential is real. All we need is time. Chapters 15, 16, and 18 provide additional information.

1.7. NANOCOMPUTING AND NEUROSCIENCE Nanotech applications in biology and medicine now allow for surgeons to induce desired physiological responses in the human body throughout the central nervous

1.7. NANOCOMPUTING AND NEUROSCIENCE

25

system (CNS). Pioneer work being done in this novel field may one day bring us numerous new therapeutic choices that hold much less risk for patients, as well as prove a more convenient means for surgeons to handle molecular machinery. According to Dr. Gabriel A. Silva, technological advancements must occur alongside clinical neuroscience advancements [43, 44] simply because of the highly interdisciplinary nature. An emerging field of neuroscience nanocomputing is the production of materials and devices designed to interact with neurons at the molecular level. The developing platform technology of nanowires that is to be discussed in this section may prove to have broad applications in neuroscience and, of greater importance, possess the potential to save lives much sooner than expected.

1.7.1. Nanomachinery: Opportunities and Challenges Imagine wires that were hundreds or thousands of times thinner than the human hair, utilizing blood vessels in the body as conduits towards adjacent individual neurons. These are what we would call nanowires [45]. Dr. Charles M. Leiber, an interested researcher at Harvard University in the field of nanocomputing, invented a nanowire transistor that can detect, stimulate, and inhibit neuronal signals [46]. This gives rise to the question of what a nanowire is. In simple terms, a nanowire is a wire of dimensions in the order of a nanometer. These range in makeup, being either metallic, semiconducting, or insulating. Some previous technology was available in this area but was too large in size. Micropipette electrodes were previously available but were harmful to cells in that they destructively poked cells. By contrast, the tiny nanowire transistors developed by Lieber and colleagues gently touch a neuronal projection to form a hybrid synapse, making them noninvasive and thousands of times smaller than the electronics now used to measure brain activity [46]. In addition to being nonintrusive, nanowires can be biodegradable, biocompatible, and capable of producing diagnostic test results in minutes instead of days. A great effort has already been invested in this nanomachinery, and a series of promising results have thus been revealed. One such opportunity is the silicon nanowires’ precision in its detection of bioterrorism threats. When discussing neuropathological disease processes at a molecular level, scientists can observe that there is potential in a nanowire’s ability to limit such disease processes with early detection. Unlike conventional DNA sensors, such nanowire techniques provide much more detailed information on the scale of neurons, as well as give a sharper focus of disease markers in perhaps any bodily fluid in humans [47]. Likewise with degenerative diseases such as Parkinson’s and Alzheimer’s, nanowires provide hope for treatment rid of damaging side effects (brain tissue scars) by stimulating the affected area of the brain with wires tinier than capillaries themselves. Many researchers envision nanowires connected to a catheter tube and able to be guided throughout the circulatory system to the brain, where nerveto-nerve interactions will allow neuroscientists to make earlier diagnoses and provide earlier treatment without the cost of time consuming procedures.

26

CHAPTER 1: AN INTRODUCTION TO NANOCOMPUTING

Through electrophysiological measurements of brain activity, made possible by nanowires, important signal propagation through individual neurons and neural networks can be understood. Sophisticated networks between the brain and external prosthetic technology can be produced through this revolutionary manipulative technique. Much of this technology has great potential in the field because it can be used to monitor signaling among larger networks of nerve cells, thereby allowing doctors to detect electrical activity going on between neurons, tumors, and brain abnormalities; to localize seizures; and to pinpoint damage caused by injuries and stroke [47]. Eventually, the technology will be used to detect the diverse kinds of neurotransmitters that leap synapses from neuron to neuron. The mystery behind many neural system disabilities such as mental illnesses and certain paralysis diseases could be unraveled with this amazing invention in the scientific community. Working at the molecular level with nanowires still has its shortcomings and is an incredible challenge in the field of neuroscience and nanocomputing. The extremely intricate composition of the CNS poses obvious challenges to nanocomputing’s applications in neuroscience. Specifically, these include cellular heterogeneity and multi-dimensional cellular interactions which explain the basis of its extremely complex information processing [43]. There is also the challenge of guiding nanowire probes to a predetermined location among the thousands of capillary branches in the human brain that reside in the brain’s vascular system. And because it is considerably more difficult to manipulate materials on the nanoscale level, it is also difficult to measure the electrical and mechanical properties of the nanomaterials themselves. Along with developing the functions of engineered machinery to carry out neural regeneration, neuroprotection, and other tasks of the sort, there is an evident need for precise and proper synthesis of such machinery. These ‘‘tailored nanotechnologies’’ cannot provide any solution to neurobiological complications unless they are designed by the most skilled and competent specialists, which in this case is not the role of the neuroscientist [44]. We know that materials scientists, chemists, and specialists of other similar disciplines have, unlike neuroscientists, devoted their careers to the synthesis of such technologies. Neuroscientists in turn contribute to this interdisciplinary science through their wealth of knowledge in neurobiology, neuropathology, and other areas. In this book, an implementation of neural network with nanotechnology is studied in Chapter 17. Evidently, these challenges have the potential to improve what may have otherwise been overlooked in synthesizing machinery. Often such obstacles help us to be more focused on the safety behind clinical neuroscience advancements.

1.7.2. Current Work and Research Functional nanotechnology, including nanocomputing, is still at its infancy stages, with numerous institutions of various scientific fields finding ways to make nanotechnology as safe and effective as can be. The government has given research grants to scientists from different universities such as Brown, Stanford,

REFERENCES

27

MIT, and CIT in order to facilitate research in such a promising field. Leading researchers such as Dr. Charles M. Lieber of Harvard University have contributed greatly to the advancement of nanocomputing. Dr. Lieber, along with his associate Jong-in Hahm, Ph.D., recently helped start a company called NanoSys, Inc., which is currently in the process of developing nanowire technology and other nanotech products. Other researchers include neuroscientist Rodolfo R. Llinas of the New York University School of Medicine and Masayuki Nakao of the University of Tokyo [45, 47]. As the general public can see, the advent of nanotechnology is one that will affect the lives of people worldwide and not simply arrive to us as a packaged fad whose hype is short lived. The great deal of research that is currently being done on the neurological applications of nanotechnology was bolstered when six scientists at Brown University were awarded $4.25 million to begin research on such interactions in the mammalian nervous system. Along with many professionals from an array of different fields—surgery, chemistry, physics, and others—these brilliant minds are collaborating to help advance knowledge and further discovery of nanotechnology and nanocomputing. This commitment to research, coupled with a great amount of popular sentiment towards nanotechnology and nanocomputing, may further our own knowledge as observers and students and accelerate the progress of this exciting phenomenon. For more information on funding and patenting issues, see Chapter 20.

1.8. CONCLUSIONS For the past 50 years, transistors have been shrinking consistently, and we have entered the era of nanocomputing. In this new era, transistors are only a small portion of the technologies that are available at nanoscale. There is a vast landscape of nano devices and paradigms that are currently being studied. In this chapter, we gave a brief introduction to nanocomputing and presented a high level overview of nanocomputing devices and paradigms. Nanocomputing has a potential to provide a remedy for some traditional problems in microelectronics. We also discussed some applications of nanocomputing such as bio medical engineering and neuroscience. The rest of this book will take the reader on a journey from low level device physics to architecture-level, bio-inspired architectures, all of which have the potential to be used for implementing various devices, such as biomedical and biomimetic nanoscale integrated circuits.

REFERENCES 1. R. P. Feynman. There’s plenty of room at the bottom: an invitation to enter a new field of physics. Engineering and Science, 23(5): 1960. 2. Wikipedia. List of Intel Microprocessors. 2007. http://en.wikipedia.org/w/index.php? title=List_of_Intel_microprocessors&oldid=181278285.

28

CHAPTER 1: AN INTRODUCTION TO NANOCOMPUTING

3. N. Weste and D. Harris. CMOS VLSI Design: A Circuits and Systems Perspective. Reading, MA: Addison Wesley, 2004. 4. C. K. Maiti, N. B. Chakrabarti, and S. K. Ray. Strained Silicon Heterostructures: Materials and Devices. Piscataway, NJ: IEEE, 2001. 5. M. Houssa. High k Gate Dielectrics. New York: AIP, 2004. 6. X. Huang, W. C. Lee, C. Kuo, D. Hisamoto, L. Chang, J. Kedzierski, E. Anderson, H. Takeuchi, Y. K. Choi, K. Asano, V. Subramanian, T. J. King, J. Bokor, and C. Hu. Sub 50-nm finFET: PMOS. Electron Devices Meeting, 1999. IEDM Technical Digest International: pp 67–70, 1999. 7. B. S. Doyle, S. Datta, M. Doczy, S. Hareland, B. Jin, J. Kavalieros, T. Linton, A. Murthy, R. Rios, and R. Chau. High performance fully depleted tri-gate CMOS transistors. IEEE Electron Device Letters, 24(4): pp 263–265, Apr 2003. 8. Harold Abelson and Peter Andreae. Information transfer and area-time tradeoffs for VLSI multiplication. Communications of the ACM, 23(1): pp 20–23, 1980. 9. J. Wang and M. Lundstrom. Electron Devices Meeting, 2002. Does source-to-drain tunneling limit the ultimate scaling of MOSFETs? In: IEDM ‘02 Digest. International: pp 707–710, 2002. 10. V. Balzani, A. Credi, and M. Venturi. Molecular Devices and Machines: A Journey into the Nanoworld. Weinheim: Wiley-VCH, 2003. 11. Y. Chen, G. Y. Jung, D. A. A. Ohlberg, X. Li, D. R Stewart, J. O. Jeppesen, K. A. Nielsen, J. F. Stoddart, and R. S. Williams. Nanoscale molecular-switch crossbar circuits. Nanotechnology, 14(4): pp 462–468, 2003. 12. B. L. Feringa. Molecular Switches. Weinheim: Wiley-VCH, 2001. 13. J. M. Tour, W. L. Van Zandt, C. P. Husband, S. M. Husband, L. S. Wilson, P. D. Franzon, and D. P. Nackashi. Nanocell logic gates for molecular vomputing. Nanotechnology, 1(2): pp 100–109, Jun 2002. 14. J. Cumings, A. Zettl. Low-friction nanoscale linear bearing realized from multiwall carbon nanotubes. Science, 289(5479): pp 602–604, 2000. 15. W. Liang, M. Bockrath, D. Bozovic, J. H. Hafner, M. Tinkham, and H. Park. Fabry– Perot interference in a nanotube electron waveguide. Nature, 411: pp 665–669, June 2001. 16. A. Khitun and K. L. Wang. Multifunctional edge driven nanoscale cellular automata based on semiconductor tunneling nanostructure with a self-assembled quantum dot layer. Superlattices and Microstructures, 37(1): pp 55–76, 2005. 17. A. Khitun and K. L. Wang. Cellular nonlinear network based on semiconductor tunneling nanostructure. IEEE Transactions on Electron Devices, 52(2): pp 183–189, Feb 2005. 18. M. A. Kastner. The single electron transistor and articial atoms. Annalen der Physik, 9: pp 885–894, Nov 2000. 19. C. S. Lent, P. D. Tougaw, W. Porod, and G. H. Bernstein. Quantum cellular automata. Nanotechnology, 4(1): pp 49–57, 1993. 20. M. Johnson. Bipolar spin switch. Science, 260(5106): pp 320–323, 1993. 21. S. Wolfram. A New Kind of Science. Wolfram Media, 2002. 22. A. Ilachinski. Cellular Automata: A Discrete Universe. Singapore: World Scientific, 2002. 23. L. O. Chua and L. Yang. Cellular Neural Networks. Circuits and Systems, 1988.

REFERENCES

29

24. C. M. Bishop. Neural Networks for Pattern Recognition. Oxford, UK: Oxford University Press, 1994. 25. M. Gardner. Mathematical games: the fantastic combinations of john conway’s new solitaire game ‘life.’ Scientific American, 223(4): pp 120–123, 1970. 26. M. Cook. Universality in elementary cellular automata. Complex Systems, 15(1): pp 1–40, 2004. 27. T. Roska and L. O. Chua. The CNN universal machine: an analogic array computer. IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, 40(3): pp 163–173, Mar 1993. 28. C. N. Eichelberger and K. Najarian. Simulating protein computing: character recognition via probabilistic transition trees. IEEE International Conference on Granular Computing, 2006. pp 101–105, May 2006. 29. L. M. Adleman. Molecular computation of solutions to combinatorial problems. Science, 266(11). 30. P. W. Rothemund, N. Papadakis, and E. Winfree. Algorithmic self-assembly of DNA sierpinski triangles. PLoS Biology, 2(12): Dec 2004. 31. P. W. Rothemund. Folding DNA to create nanoscale shapes and patterns. Nature, 440: pp 297–302, 2006. 32. M. A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge: Cambridge University Press, 2000. 33. P. W. Shor. Algorithms for Quantum Computation: Discrete Logarithms and Factoring. IEEE Symposium on Foundations of Computer Science: pp 124–134, 1994. 34. L. M. Vandersypen, M. Steffen, G. Breyta, C. S. Yannoni, M. H. Sherwood, and I. L. Chuang. Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance. Nature, 414: pp 883–887, Dec 2001. 35. N. L. Kedersha, D. F. Hill, K. E. Kronquist, L. H. Rome. L.H. Subpopulations of liver coated vesicles resolved by preparative agarose gel electrophoresis. Journal of Cell Biology, 103: pp 287–297, 1986. 36. National Science Foundation. ‘‘Vaults: From Biological Mystery to Nanotech Workhorse?’’ Biological Sciences, Arlington, VA: The National Science Foundation. http:// www.nsf.gov/discoveries/disc_summ.jsp?cntn_id=104106&org=MCB, 2007. 37. Regents of the University of Michigan. Molecular Motors. http://www.umich.edu/ news/MT/04/Fall04/story.html?molecular. Jan 16, 2007. 38. Y. E. Goldman. Functional studies of individual myosin moleculares. Annals of the New York Academy of Sciences, 1(18): 2006. 39. C. McCarthy, Nano Science and Technology Institute. Pharma Explores Business Opportunities for Nanotech. http://www.nsti.org/news/item.html?id=. Mar 13, 2007. 40. Cirrus Pharmaceuticals. Pharmaceutical Nanotechnology. http://www.cirruspharm. com/pdf/brochures/Nanotechnology.pdf. Mar 13, 2007. 41. R. A. Freitas. Computational Tasks in Medical Nanorobotics. Insitute for Molecular Manufacturing, 2007. 42. P. Chapman. Nanotechnology in the pharmaceutical industry. Expert Opinion on Theraperutic Patients. 15(3): pp. 249–255, 2005. 43. G. A. Silva. Introduction to nanotechnology and its applications to medicine: applying nanotechnology to medicine. Surgical Neurology, 61: pp 216–220, 2004.

30

CHAPTER 1: AN INTRODUCTION TO NANOCOMPUTING

44. G. A. Silva. Neurosicence nanotechnology: progress, opportunities, and challenges. Nature Reviews Neuroscience, 7: pp 65–74, 2006. 45. National Science Foundation. Nanowires in blood vessels may help monitor,sStimulate neurons in the brain. http://www.nsf.gov/news/newssumm.jsp?cntnid=104288&org= ENG. July 7, 2005. 46. F. Patolsky, B. P. Timko, G. Yu, Y. Fang, A. B. Greytak, G. Zheng, and C. M. Lieber. Detection, stimulation, and inhibition of neuronal signals with high-density nanowire transistor arrays. Science, 313: pp 1100–1104, 2006. 47. Tiny Nanowire Could be Next Big Diangostic Tool for Doctors. Science Daily: Dec. 18, 2003.

2 NANOSCALE DEVICES: APPLICATIONS AND MODELING Alireza Nojeh This chapter starts with a discussion of the roots of nanotechnology, the distinguishing aspects of the nanoscale, and the definition of nanoscale devices. Some of the common materials and techniques used to fabricate such devices are briefly reviewed. The physics of the operation of nanoscale devices is the subject of the next part. Quantum dots, resonant tunneling diodes, and single-electron transistors, which can be made using traditional fabrication methods, are first studied. Then a number of devices based on newer materials such as carbon nanotubes are introduced, and how the properties of these materials provide opportunities for innovative device design is discussed. The last part of the chapter deals with the theoretical study, modeling, and simulation of nanoscale devices. The challenge of the many-body problem and the difference between firstprinciples and semi-empirical approaches are highlighted. A brief introduction to some of the simulation methods, such as the Hartree–Fock approximation, density functional theory, molecular dynamics, tight-binding, and Monte Carlo, concludes the chapter.

2.1. INTRODUCTION 2.1.1. The Roots of Nanotechnology Although one can easily think of many milestones, such as the invention of the scanning tunneling and atomic force microscopes or the discovery of fullerenes in the 1980s, that have pushed us more and more into the nano era, it is not easy to define a single point in time when it all started. For instance, many of the imaging tools relevant to the nanoscale, such as electron microscopes, have been around Bio-Inspired and Nanoscale Integrated Computing. Edited by Mary Mehrnoosh Eshaghian-Wilner Copyright r 2009 John Wiley & Sons, Inc.

32

CHAPTER 2: NANOSCALE DEVICES: APPLICATIONS AND MODELING

for a long time. But as we see, they have been called microscopes and not nanoscopes. One tends to think that at least one aspect of what we consider nanotechnology is the extension of microtechnology to smaller sizes, and it is hard to separate the roots of these two, although some clear distinctions can be drawn between them. As discussed in Chapter 1, a particularly interesting early reference to small scale devices and technologies was made by physicist Richard Feynman in a lecture he gave in 1959 [1]. Feynman did not make specific claims about what would happen in future, but rather gave a tour of what could very logically and naturally be available at small scales from a purely scientific point of view (i.e., without contradicting the laws of physics as we know them). After almost half a century, that lecture can be an insightful introduction for newcomers to the field of nanotechnology and a great inspiration to seasoned nanotechnologists.

2.1.2. Two Ways to Reach the Nanoscale It could be argued that one of the most dramatic changes in our lifestyles has been brought about by the rapid advance of the microelectronics industry over the last few decades. The steady decrease in the size of transistors, the fundamental building blocks of microelectronic circuits, has lead to today’s low cost and high performance computer chips. For instance, the transistors in your computer are about a tenth of a micrometer in size, or maybe even about a twentieth of a micrometer if you have recently bought a new one—that is about 50 nanometers (nm). Thus, for those who work in this industry, nanoelectronics is a completely natural continuation of microelectronics. In fact, many tend to define a device as being a nanodevice if one of its dimensions is smaller than 100 nm. In that sense, the semiconductor industry has already entered the era of nanoelectronics—without really calling itself nanotechnology! Pushing our traditional microfabrication techniques to make devices much smaller than a micrometer is one way of approaching the nanoscale. One could think of this as the art of ‘‘carving’’ ultra-small objects. However, there are objects that are very small by their nature, such as molecules. They provide another approach to nanotechnology: use small objects already available to us through nature and try to add some level of control to where and how they are arranged so that they can perform the functions we are interested in.

2.1.3. The ‘‘Nano’’ Difference As pointed out in Chapter 1, there is more to the nanoscale than just the ability to pack a large number of devices in a small area or to manipulate very small objects. There is a fundamental reason that makes ‘‘nano’’ attractive from a scientist’s point of view but a nonexpert might have a little more difficulty appreciating it. Let us see what that is. We know that objects are made of individual units called atoms that are extremely small. This book you are reading, for example, contains on the order of one hundred trillion trillion atoms—that is a 1 with 26 zeros in front of it! When

2.1. INTRODUCTION

33

such a large collection of atoms is put together, the general behavior of the ensemble in everyday life experiences does not directly reflect the atomistic nature of the system. It looks like a solid, bulky material for which the behavior can be explained relatively easily: You can describe it in terms of its macroscopic properties, i.e., weight, dimensions, color, etc. You can also use the laws of classical physics, such as Newtonian mechanics, to describe its motion if a force is applied to it. In fact, atoms behave according to laws discovered much later than Sir Isaac Newton’s classical mechanics. The laws of quantum mechanics, developed mainly in the first half of the twentieth century, are rather nonintuitive for someone who is used to everyday phenomena with large objects, but they constitute the best description we have so far for the world of small particles such as atoms. Let us continue with the example of the book. When such a huge collection of atoms is put together, the overall behavior will be a statistical average of the behavior of the individual atoms, subject to external forces and the constraints that keep them together. This average behavior can be explained well with classical physics. The result is that we do not really need quantum mechanics to be able to handle a book! Now, imagine a microelectronic device, such as a transistor, with dimensions on the order of a micrometer. Such a device would contain about one trillion atoms (a 1 with 12 zeros in front of it). That is still a very large number and so, even in such a small device, most of the characteristics are determined by the statistical averages of many interactions and phenomena. Thus, although in order to properly understand these phenomena and the resulting average behaviors one needs to apply quantum mechanics, more phenomenological laws can be derived using statistical analysis that explain the device behavior accurately enough for most engineering purposes. In fact, quantum mechanics is still somewhat masked and its effects are only indirectly visible at the microscale. In other words, you do not need to resort to quantum mechanics every time you want to study or use a microscale transistor. In this sense, even microdevices could be considered somewhat classical. Now let us imagine devices that have dimensions on the order of only a few nanometers. In matter, atoms are spaced apart by a few angstroms. An angstrom is 10 times smaller than a nanometer. Thus, in the volume of our nanoscale device, there would be only a few hundred or thousand atoms. It turns out that in such small collections of atoms, statistical averages are not always very meaningful. But the individual character of each atom—its quantum mechanical nature—is much more visible. Therefore, when working with nanodevices one observes quantum mechanics very directly and, by the same token, can take advantage of the laws of quantum mechanics to design devices and systems that are not achievable at larger scales (that is, where quantum effects have averaged out to give way to more classical behavior). This direct access to quantum mechanics at the nanoscale makes a fundamental difference that involves more than manipulating small objects or squeezing a large number of devices into a small area. A whole new world of functionalities and possibilities previously unimaginable is opened up. One is tempted to argue that this is the most important aspect of the nano

34

CHAPTER 2: NANOSCALE DEVICES: APPLICATIONS AND MODELING

world, but that remains to be determined by the course of progress of this field in the future. In addition, the surface-to-volume ratio of objects increases as the objects become smaller. For instance, the surface of a cube with side x is 6x2 and its volume is x3, so the surface-to-volume ratio, 6/x, increases as x decreases. Usually, the surfaces of materials act differently from their bulk in terms of physical properties. As one goes to smaller and smaller scales, surface phenomena become a more important part of device behavior, and this could have very practical implications.

2.1.4. What is a Nanodevice? The exact definition of what a nanodevice is remains somewhat fuzzy and subjective. There seems to be a general consensus that any device with at least one dimension below 100 nm is a nanodevice. In many cases, depending on how a particular device is made and its principle of operation, some may choose to call it a nanodevice and some may not. What seems to be clear is that, regardless of how we reach the nanoscale and whether or not we manage to make sophisticated nanorobots at some point in future, many interesting phenomena happen at the nanoscale that are worth studying and could be used for new device ideas. This chapter hopes to reach out to a large audience. For the nontechnical who are intrigued by the word ‘‘nano,’’ the chapter provides a general insight. For the nonexpert technical person or those wishing to enter the field of nanodevice research (such as advanced undergraduate or fresh graduate students in science and engineering), it provides an introduction and perspective. The main focus of the chapter is on the electronics aspects of nanodevices, but there exist many other aspects to these devices, as well as different approaches to understanding them and creating new ones. Obviously none of the devices or methods discussed here can be reviewed in full detail in the context of a one-chapter overview, nor can all the valuable references in the field be cited. However, the author hopes that the references provided here will be a good starting point for those interested in learning more about each subject.

2.2. MATERIALS OF NANOTECHNOLOGY The first question that might come to mind when thinking about materials for nanodevices is such: Can one take any material (even a piece of wood), carve a nanoscale object out of it (assuming one has the means, such as an ultra-sharp carving tip to make something that small!), and hope that it would exhibit some interesting nanodevice characteristics? The answer, in principle, is yes. In practice, however, just as is the case in the microscopic or macroscopic worlds, different materials have different properties at the nanoscale level; depending on the particular application the nanodevice is intended for, one has to spend some effort to find the right material for it.

2.2. MATERIALS OF NANOTECHNOLOGY

35

The well established materials of the microelectronics industry, such as silicon, dielectrics, and metal layers, also represent a very important category of materials necessary in nanodevices. Not only can many nanoscale devices be made using only these materials and standard microfabrication processes, but in many other cases at least part of the structure of a nanodevice involves these materials and processes. We will talk more about this later in the chapter, but for now let us focus on objects that are more ‘‘nano’’ by nature.

2.2.1. Molecules We know that a molecule is a collection of atoms of either one element or several different elements. Most of the molecules we are familiar with (for example from our high school chemistry) are made of a relatively small number of atoms. Consider the water molecule. It has one oxygen and two hydrogen atoms. However, there is no reason why we could not have much bigger molecules that include hundreds or even thousands of atoms—as a matter of fact, we do! Let us go back and think about our nanodevices for a moment. We estimated that a typical nanodevice would have hundreds or thousands of atoms in it. Can we say a nanodevice is a molecule? In reality, many nanodevices could be considered molecules. Many would be a system of several molecules put together or with other structures in a certain fashion. The term molecular electronics is quite commonly used these days. One difference between these molecules and the more ‘‘traditional’’ molecules that we remember from good old high school chemistry is that there the molecule was a concept describing the smallest building blocks of a much larger substance. When we say a nanodevice can be thought of as a molecule, we are really only emphasizing the fact that it is a stable collection of a number of atoms, and not necessarily a unit that is going to be used to build a macroscopic substance. Also, when one thinks of a molecule, the first examples that usually come to mind are rather small ones that contain only a few atoms (such as the hydrogen or benzene molecules), although much larger molecules are also commonplace (such as many polymer molecules or the DNA that can reach macroscopic length scales). Nanodevices, if one wants to call them molecules, are usually very large molecules.

2.2.2. Nanoparticles One important set of ‘‘objects’’ that are very useful to the world of nanotechnology is nanoparticles. As the name implies, a nanoparticle is a particle that has dimensions on the order of a few nanometers. This typically includes a few thousands of atoms. Nanoparticles can be made from various materials. Many metals, for instance, form good nanoparticles. Nanoparticles containing more than one element can also be formed. Again, what is really important about a nanoparticle is the fact that it is small enough such that the quantum effects and large surface-to-volume ratio effect discussed before are dominant in it, to the extent that its properties can no longer be described by the same general properties

36

CHAPTER 2: NANOSCALE DEVICES: APPLICATIONS AND MODELING

describing a microscopic or macroscopic piece of the same material. In this sense, nanoparticles are at the intermediate level between bulk materials and the atomic world.

2.2.3. Nanowires We recall from geometry that an object can be zero-dimensional (0D: a point), one-dimensional (1D: a line), two-dimensional (2D: a plane) or three-dimensional (3D: a volume). In analogy, nanoparticles are like points. One important category of nanomaterials is 1D objects or ‘‘lines’’ at the nanoscale, namely nanowires. A typical nanowire has a thickness of a few nanometers to a few tens of nanometers; its length is much more than a nanometer, giving it a very high aspect ratio (like a line). Nanowires have been made of many materials, such as silicon, germanium, zinc oxide, and gallium nitride [2–5]. Nanowires are extremely important due to their one-dimensionality. In particular, the electronic properties in these 1D materials can be drastically different from their bulk counterparts due to the fact that charge carriers (electrons) are confined to a small space (only a few nanometers) in the lateral dimensions. This leads to very strong quantum mechanical effects and can result in outstanding electronic transport characteristics for devices such as transistors and switches needed in ultra-high-performance electronic circuits and chips.

2.2.4. Nanotubes One particularly important form of nanowires is what we call a nanotube. The name explains it all: It is a hollow cylinder with a diameter on the order of 1 nm. The most common nanotubes are those made of carbon, i.e., carbon nanotubes. Graphite is a well known form of carbon. Pencil lead is made out of graphite. Graphite has an interesting structure, in that it is composed of one-atom-thick layers stacked on top of each other. Each layer, called graphene, is a sheet of carbon atoms arranged in a hexagonal lattice structure, like a chicken wire. A carbon nanotube can be thought of as a single graphene sheet rolled along a certain direction into a nanometer-diameter tube that is hollow inside. Carbon nanotubes can be extremely long, up to several centimeters, and that means they have aspect ratios on the order of 107. Thus, they represent highly 1D systems. They can be single-walled (Fig. 2.1), i.e., composed of only one layer, or multiwalled, composed of several co-axial, single-walled nanotubes. Carbon nanotubes were discovered in 1991 by Sumio Iijima [6] and have since attracted much attention in the world of nanotechnology due to characteristics such as outstanding electronic properties arising from their 1D nature, as well as extreme mechanical strength due to the strong carbon-carbon SP2 bond. One fundamental difference between nanotubes and other forms of nanowires is that a nanotube is by itself a perfect structure. In other words, most nanowires can be thought of as a very thin wire carved out of a 3D bulk. As such, there could be many unsatisfied and dangling bonds on the surface of these structures. They

2.3. WORKING AT THE NANOSCALE

37

Figure 2.1. 3D view of a section of a single-walled carbon nanotube.

could also be rather brittle. A nanotube is, on the other hand, one of the natural, stable forms of its material. For example, a carbon nanotube is an allotrope of carbon, the same way graphite and diamond are. A nanotube surface does not have dangling bonds and all atoms are in a perfect crystalline structure, contributing to the stability of the overall system. A carbon nanotube is, in fact, a giant molecule. For a detailed study of carbon nanotubes the reader is referred to [7].

2.3. WORKING AT THE NANOSCALE Nanofabrication, at least so far, has been heavily reliant on the processes used to fabricate microelectronic circuits or micro electro mechanical systems (MEMS). In fact, many of the processes used for nanodevice fabrication are simply microfabrication processes. In most cases, the term ‘‘nanofabrication’’ only implies that we are using them to make nanodevices. For a detailed study of microfabrication and MEMS techniques references [8, 9] can be used. A typical nanodevice fabrication process involves several microfabrication steps, with the addition of one or two new steps to the process. Let us consider a device consisting of a nanotube attached to two metal electrodes lying on an insulating surface (Fig. 2.2). The fabrication of this device starts with thermal oxidation of silicon to create a thin dielectric layer on a silicon wafer. Then lithography and metal deposition are used to create the contact electrodes. Another lithography step helps pattern catalyst islands that will later be used to grow carbon nanotubes. So far everything is standard microfabrication. The last step, i.e., the growth of the nanotube, can be done using chemical vapor deposition (CVD) [10]. Although CVD has long been around for various fabrication purposes,

38

CHAPTER 2: NANOSCALE DEVICES: APPLICATIONS AND MODELING

Catalyst island Nanotube

Drain

Source (thickness: 50 nm)

Silicon dioxide (thickness: 100 nm) Back gate Silicon wafer 5 μm

Figure 2.2. Schematic representation of a device including a nanotube attached to two metal electrodes.

nanotube CVD is a relatively recent process that is not standard to the microelectronics or MEMS industry, and can be qualified exclusively as a nanofabrication step. In general, CVD leads to nanotubes growing randomly in all directions; the task of locating the nanotubes in desired locations and orientations after CVD can be quite time consuming and, more importantly, cannot be relied upon for mass production of devices. It has been demonstrated, however, that the direction of the nanotubes grown by CVD can be controlled to a large extent by the application of an electric field [11, 12] or by using the direction of the laminar flow of gases [13, 14] during CVD. Just as in the case of fabrication, many of the inspection and imaging techniques appropriate for nanotechnology have also existed for a long time. Some of the most commonly used imaging methods with nanoscale (or even subnanoscale) resolution include scanning and transmission electron microscopy (SEM and TEM). These work on principles very similar to optical microscopes; the basic difference is that instead of photons (light particles) they use electrons to obtain an image. The reason is that electrons generated in typical laboratory equipment can easily have associated wavelengths much smaller than photons and thus be focused to a much smaller spot, leading to higher resolution. Another group of techniques for imaging and manipulating nanoscale objects is scanning probe microscopy (SPM). The idea behind these is to have a very small and sharp tip brought in contact with a sample (although the term contact should be used loosely in this context), scan the surface, and record the profile. Based on whether the sample is conductive or insulating and other requirements, various types of SPM methods can be used. Scanning tunneling microscopy (STM) and atomic force microscopy (AFM) are two of the most popular techniques of this kind. After a device has been fabricated and imaged, various measurements and experiments are performed on it. There are two big challenges. The first is reaching

2.4. NANODEVICE APPLICATIONS

39

such small devices to perform, say, electrical measurements on them. Usually this can be done by making ‘‘interface’’ structures to connect the nano world to our macroscopic world. For instance, in the case of the device in Figure 2.2, the metal electrodes on the sides can be connected to large pads that one can use for wire bonding to the outside world. Another option is to use high resolution motion probes, such as in an SPM tool, to move, manipulate, and contact objects at the nanoscale. The second challenge is determining whether a measurement or perceived effect is really due to the nanodevice and not other surrounding structures, noise, inaccuracies, etc. This is true in any experiment in general, but it becomes particularly important at the nanoscale since one is dealing with very small signals. Creative techniques need to be developed constantly for such experiments. This is an ongoing challenge in nanotechnology.

2.4. NANODEVICE APPLICATIONS Although nanotechnology is still very much in a research phase, many applications have been suggested and even demonstrated at the laboratory level for nanoscale devices. It should be noted that many of the more traditional microdevices have also found their way into nanotechnology. Their scaled down versions could well be considered nanodevices, especially since the reduction in scale results in major differences in characteristics and operation, such as the operating temperature. In this section we will first review some of the more established devices in this category, and then present some of the less traditional nanodevice ideas.

2.4.1. ‘‘Traditional’’ Nanodevices The fundamental building blocks of our computers are field-effect transistors (FETs), which act as switches to perform logic operations. In parallel with efforts to shrink those devices in the well-established silicon technology, as well as in new types of materials (discussed later in this chapter), there have also been many efforts in making alternative devices that could perform such operations. Here we will look at some of the most common devices in this category, namely resonant tunneling diodes (RTDs), single-electron transistors (SETs), and quantum dots (QDs). An interesting overview of these devices can be found in [15]. As discussed, a fundamental aspect of nanodevices is that quantum effects are directly visible in them. We will take a closer look at this here. 2.4.1.1. Resonant Tunneling Diodes. Consider the problem of a ‘‘particle in a box.’’ By this we mean a particle, say an electron, confined to a small region in space by a potential energy distribution such as the one shown in Figure 2.3. This represents what is called an infinite potential ‘‘well’’—namely, a region where the electron is trapped by two barriers on the sides.

40

CHAPTER 2: NANOSCALE DEVICES: APPLICATIONS AND MODELING

4

3 2 1 d

Figure 2.3. A potential well where electrons are confined in space due to energy barriers on the sides. Electrons in such a ‘‘box’’ can only take on discrete energy levels as shown. The horizontal axis is location and vertical axis is energy of the electron.

As will be discussed in more detail later in this chapter, the fundamental equation that governs the behavior of quantum mechanical particles, such as electrons, is the Schro¨dinger equation. The energy levels that an electron is allowed to have in this one-dimensional potential well can be easily obtained by an analytical solution of the Schro¨dinger equation. The result is EN ¼

_2 p 2 N 2 ; 2md 2

N ¼ 1; 2; . . .

Here _ is Planck’s constant and d is the width of the well. In other words, the electron in the well cannot have just any energy, but must take one of the discrete values given by the above formula. In general, such ‘‘quantization’’ of energy levels also happens in the 3D case. This idea is at the heart of some of the quantum devices that we will discuss in this section. Now consider a region in space where a potential well is connected to two metal electrodes through barriers with finite heights and widths on the sides, such as in Figure 2.4. This is an RTD. An electron can enter this region from outside, leave the region by overcoming the barrier heights (by, for instance, acquiring thermal energy and going to higher energy levels), or move through the barriers by a process called quantum mechanical tunneling. What is interesting is that in the transport characteristics of this device, the effect of these discrete energy levels becomes completely visible. Now imagine a voltage bias is applied to the structure that leads to a relative shift in the chemical potentials of the two contact electrodes, such as in Figure 2.5. An electron will be able to tunnel through the device from one side to the other only if the biases on the two sides are such that there is an energy level in the well in the range where electrons exist on the left and empty states exist on the right, i.e., when there is a level lower than m1 but higher than m2. (Remember that in the electrodes all energy states up to the chemical potentials are filled with electrons.)

41

2.4. NANODEVICE APPLICATIONS

μ1

μ2

Figure 2.4. The double-barrier structure of an RTD. The gray areas on the sides represent metal contacts or reservoirs of electrons with chemical potentials m1 and m2. The horizontal axis is location and vertical axis is energy of the electron.

Thus, as the applied bias is increased, every time a new energy level enters the range between the two side chemical potentials, there will be a peak in the device’s current versus voltage curve (Fig. 2.6). If a ‘‘gate’’ electrode is placed below the device to enable us to move the energy levels up and down, then we can use this gate to control which level lies between the side chemical potentials, and therefore we can control the conductance of the device. This is the basis of a three-terminal switching device or resonant tunneling transistor. Note that the conductance through this device cannot be modeled by simply considering two single barriers in series. In fact, what is essential here is the wave nature of the electrons and the resonance phenomenon in the well that leads to a high transmission probability of electrons from one side to the other, giving rise to the peaks in conductance. This is analogous to the transmission of light through a multilayer structure with layer thicknesses on the order of the wavelength of the incident light or smaller. Resonance phenomena there can lead to high transmission for a given set of layer properties (thicknesses and refractive indices) and incident wavelength. In general, this is the problem of a resonant cavity, which in the case of the RTD is a cavity for electrons.

μ1 μ2

Figure 2.5. A double-barrier under applied bias, which creates a difference between the chemical potentials on the two sides.

42

CHAPTER 2: NANOSCALE DEVICES: APPLICATIONS AND MODELING

I

Resonant peaks

V

Figure 2.6. Conceptual representation of the current-voltage characteristics of an RTD.

2.4.1.2. Single-Electron Transistors. In the operation of the RTD, we looked at the problem as if there were only one electron in the system. In other words, we neglected electron-electron interactions. Electrons repel each other through Coulomb forces; if an electron is put inside the device, it will be harder for a second one to enter since it will have to face the repulsive force of the first one. This is called Coulomb blockade. In other words, if multiple electrons are to enter the device at a time, each subsequent electron will have to be put at an energy not only determined by the level quantization shown in Figure 2.3, but also by the charging energy of the device due to its capacitance. As a consequence, the difference between the energy of the electrons will be approximately the sum of the two contributions. One effect may be more dominant than the other based on the actual device size and material. In RTDs the device has a relatively large capacitance such that the charging energy e2/C is much smaller than the level quantization energy discussed above. In an SET, however, the structure is such that the charging energy is much larger than the level quantization energy. Note that although the end result of both effects (resonant tunneling and Coulomb blockade) is that transport happens through discrete energy states and gives rise to unusual device characteristics, the two effects are fundamentally different: one effect is due to the wave nature of particles (quantum mechanical), and the other one due to the fact that the value of charge is quantized (which could be regarded as a somewhat more classical effect). A review of single-electron transistor devices can be found in [16]. Such structures could also be operated under an alternating voltage, and the frequency and amplitude of this signal is such that only one electron is transferred per cycle through the device. Such a device is called a singleelectron turnstile [17]. 2.4.1.3. Quantum Dots. There seems to be some degree of ambiguity in the literature as to the exact definition of a QD. In particular, the terms SET and QD often seem to be used one instead of the other. A QD could be thought of as a confined region between two potential barriers such as in Figure 2.4, although confinement in all three dimensions is typically assumed. In a sense, RTDs and SETs can be considered special forms of QDs. Both energy level quantization

43

2.4. NANODEVICE APPLICATIONS

I

V

Figure 2.7. The staircase-like current-voltage characteristics of a QD. The width of the plateaus is defined by the separation of the energy levels due to quantum confinement and/or Coulomb blockade.

(due to the wave or quantum mechanical nature of electrons) and Coulomb blockade (due to the discrete nature of charge) are present in the electronic characteristics of a QD. The authors in [15] present the clear distinction that if these two effects are on the same order of strength and significance, the device is a QD; otherwise it is an RTD or SET depending on which effect is dominant. In so doing, they correlate these effects to the number of ‘‘small’’ or confined dimensions in each device. What is really important in any case is the clear understanding of both these effects and their fundamental difference. Also, note that typically the structure of an RTD is such that as the bias is increased, only one level at a time is in the energy ranges where there are available electrons for transport, giving rise to the peaks in the conductance characteristics of the device and the negative differential conductance after each peak (Fig. 2.6). However, in what we usually think of as QDs or SETs, often a wider energy range can be available for the incoming electrons (compared to the level spacing inside the well); as the bias is increased, first one level enters that range, then a second one, a third one, and so on, without the previous levels leaving that range. Thus, instead of a number of peaks in the current–voltage characteristics, one can have a staircase-like profile: every time a new level enters the allowable energy ranges of the contacts, the current goes up by a finite amount (Fig. 2.7). Because electron energy is quantized in a QD (like the energy levels in an atom) quantum dots are sometimes referred to as artificial atoms. For more detail on the operation of QDs the reader can consult [18, 19]. The above quantum devices can be realized in various ways. One popular method is to create a so called two-dimensional electron gas (2DEG) in the interface region of a heterojunction of III-V semiconductors with different band gaps. A set of electrodes is patterned on top of this 2DEG, and by the application of proper bias to these electrodes, some regions of this 2DEG can be depleted (Fig. 2.8). As a result, an ‘‘island’’ of electrons is created that is connected to the reservoirs on the sides through potential barriers (the depleted regions).

2.4.1.4. Temperature Dependence. Table 2.1 shows the first few allowed energy levels in a potential well with different widths calculated using the formula

44

CHAPTER 2: NANOSCALE DEVICES: APPLICATIONS AND MODELING

Figure 2.8. Schematic top view of a QD created in a 2DEG.

presented earlier. As can be seen, going from 100 to 1 nm changes the energy level separations significantly. Note that the thermal energy of electrons at room temperature is kT=25.9 meV (k is Boltzmann’s constant and T is temperature on the absolute or Kelvin scale). If the separation of levels is smaller than this value, the thermal energy of the electrons will be enough to allow them to freely move between these levels; subsequently, the quantization of levels becomes masked at room temperature. Table 2.1 shows that one can hope to see room temperature operation only if the device size is on the order of 10 nm or less. This is in fact the case, and most experiments on QD-type devices are performed at very low temperatures (cryogenic temperatures such as liquid helium temperature). A similar effect also exists with regards to the Coulomb blockade energy e2/C. This energy will be large enough to have an effect at room temperature only if the device dimensions, and therefore its capacitance, are small enough. This typically happens at the nanoscale. An example of room temperature operation can be seen in [20].

2.4.2. Less Traditional Nanodevices By making the ‘‘island’’ of electrons smaller and smaller in the devices discussed in the previous section, one goes from the world of microdevices to that of nanodevices. This could be accomplished, for instance, by using lithography TA B L E 2 . 1 . The First Four Energy Levels in an Infinite Potential Well with Various Widths N

eN (meV) for W=100 nm

eN (meV) for W=10 nm

eN (meV) for W=1 nm

1 2 3 4

0.038 0.151 0.339 0.603

3.8 15.1 33.9 60.3

380 1510 3390 6030

45

2.4. NANODEVICE APPLICATIONS

Source

Gate

Drain

N

N Channel

P

Figure 2.9. Schematic representation (side view) of an MOS FET (N-channel type).

with higher resolution or new methods of fabrication. But there are other types of nanodevices that are ‘‘nano’’ by nature without the need for us to try to make them smaller. This section reviews some of these devices. 2.4.2.1. Nanoscale Field-Effect Transistors. Let us recall from Chapter 1 the operation of a metal-oxide-semiconductor field-effect transistor (MOS FET), shown schematically in Figure 2.9. Conduction in this device happens between source and drain in a channel below the gate. The properties of this channel can be modulated by the voltage applied to the gate (by attracting more charge carriers to the channel or pushing them away from it), and this is the basis of the switching action of the transistor. Now let us focus more on the channel itself. We introduced nanowires and nanotubes earlier in this chapter. The basic idea behind nanoscale FETs is the use of a nanowire or nanotube as the conducting channel of the transistor. This wire or tube is connected between two electrodes (source and drain), and a third electrode placed in close proximity (above, below, or even on its side) acts as gate (Fig. 2.10). The difference with traditional MOS devices is that here transport does not happen in a 3D bulk material, but rather in a 1D structure, which is radically different. As a result, these nanoscale FETs can have major differences in characteristics from their traditional counterparts, including several advantages. In these 1D structures or quantum wires, charge carriers are confined in the two lateral directions and behave completely differently compared to 3D materials: not only do they experience strong energy quantization effects, but their movements are strongly correlated with each other. In particular, carriers in these

Gate Source

Drain Nanotube channel

Silicon substrate

Figure 2.10. Schematic representation (side view) of a nanotube FET.

46

CHAPTER 2: NANOSCALE DEVICES: APPLICATIONS AND MODELING

wires can have very high mean free paths (the average distance they travel before being scattered), and even ballistic transport (collision free transport) can happen over lengths of up to several micrometers. This could lead to very high operation speed. Transistor action in these devices can happen as a result of both direct modulation of the channel due to the gate or the modulation of the tunnel barriers at the source and drain contacts. These nano transistors are currently the subject of active research, both experimentally and theoretically. For instance, silicon nanowire transistors have been reported to have higher on–off ratios and smaller subthreshold slope (approaching the theoretical limit) than planar silicon-oninsulator FETs [21]. FETs based on other types of nanowires, including germanium, zinc oxide, and gallium nitride, have also been investigated [3, 22, 23]. Similarly, high performance FETs based on carbon nanotubes, including ballistic transport devices, have been demonstrated [24–26]. Applications for logic circuits and high frequency operation (GHz range) have also been investigated [27, 28]. For a theoretical study and modeling of nanowire and nanotube transistors, the reader is invited to consult [29–32]. 2.4.2.2. Exploiting the Hidden Offerings of Nanomaterials. If the length of the channel in a nanowire or nanotube transistor is made very short, the device will naturally become a quantum dot or single electron transistor. Obviously this can be achieved if high resolution patterning is possible, and it is one way of making nanoelectronic devices with new materials [33, 34]. Note that in this approach we are using only the fact that these materials are one-dimensional or quantum wires, i.e., confinement in two directions is already in place. However, the size of the quantum dot achieved in this way is still determined by our ability to pattern electrodes on the nanotube with very high spatial resolution. Therefore, this kind of quantum dot typically has a length on the order of 100 nm and, as discussed before, room temperature operation is not easy. Here we will discuss briefly how some of the less obvious properties of these nanomaterials can be exploited to make new types of devices that are less dependent on traditional patterning techniques. Consider a single-walled carbon nanotube. It is a quantum wire and can be made into a quantum dot by creating only one additional degree of confinement in it. Using first-principles calculations, the authors in [35] predict that if the cross section of a nanotube is deformed from circular to elliptical, its electronic structure (both valence and conduction bands) can be altered significantly, changing the nanotube from semiconducting to metallic and vice versa. This property was used in [36] and two kinks were created in a nanotube using AFM manipulation (Fig. 2.11) to induce potential barriers and isolate a dot as small as 20 nm, which exhibited room temperature operation. The device was also studied theoretically in [37]. Another device suggested in [38] is based on the geometrical idea that a dot can be defined by crossing two lines. Here the induced mechanical deformation at the intersection of two nanotubes crossing each other (Fig. 2.12) creates a local potential well with a width of about 1.5 nm, potentially enabling room temperature operation.

47

2.4. NANODEVICE APPLICATIONS

(a)

(b)

Figure 2.11. (a) Nanotube QD fabricated by creating two kinks in the nanotube shank using AFM manipulation. Scale bar indicates 20 nm.(From [36]. Reprinted with permission from AAAS.) (b) Simulation of the structure Reprinted with permission from [37] (r 2005 American Institute of Physics)

The advantage here is that once the two nanotubes are made to cross one another, the quantum dot is formed by the natural relaxed configuration of the system and its size is defined automatically to be about 1.5 nm, which would be impossible to achieve using the established patterning techniques. The effect of this deformation on the local density of states in a similar structure was also investigated experimentally in [39]. Thus, as can be seen, there are properties in nanomaterials that can be capitalized on for the creation of novel devices. The author believes that this is one of the major advantages of the world of nanoscale devices and that many unexplored opportunities in this regard still exist.

2.4.3. Other Nanodevice Applications 2.4.3.1. Electron Emitters. Electron emitters have long been in use in vacuum tubes and applications such as electron microscopy and electron beam lithography. With the advances in electron optics in these systems, the electron emitter or source remains the performance bottleneck. Parameters such as the brightness, energy spread, and shot noise of the electron beam directly affect resolution, signal-to-noise ratio, and throughput in such applications. Electron emission is the phenomenon of extracting electrons from inside a metal or semiconductor into a vacuum. An electron emitter could be as simple as a tungsten hairpin with a sharp point. Figure 2.13 summarizes various well established electron emission mechanisms including emission by heating the sample to provide the necessary kinetic energy for the electrons to overcome the

48

CHAPTER 2: NANOSCALE DEVICES: APPLICATIONS AND MODELING

(a)

(b)

Figure 2.12. Nanotube cross QD. (a) AFM image of structure. (b) Simulated structure using molecular dynamics. Reprinted with permission from [38]. (r 2003 American Chemical Society)

workfunction barrier (thermionic emission), by applying a large external electric field to extract electrons by quantum mechanical tunneling through the potential barrier (field-emission), or by a combination of heat and external field (Schottky emission). Another way to provide the necessary escape energy to the electrons is by using light (photo-emission). A sharp object enhances an externally applied electric field and makes electron emission easier. With the advent of nanotechnology and the possibility of fabricating very small and sharp tips with high aspect ratios, electron emission research has reached new dimensions and become a very popular subject in the world of nanodevice applications (Fig. 2.14). In particular, carbon nanotubes, with their extremely strong mechanical structure, high current carrying capacity (109 A/cm2—orders of magnitude higher than copper and silver), and high aspect ratios, seem like ideal candidates for field-electron emitters [40–44]. Moreover, their unique structure could lead to interesting electron emission characteristics or be used to make more controllable electron emitters. In one experiment, electron

49

2.4. NANODEVICE APPLICATIONS

Vacuum level Thermionic emission

e e

Schottky emission

Work function

Fermi level

e

Field-emission

Metal

Vacuum

Figure 2.13. Various electron emission mechanisms.

emission from the tip of a nanotube was triggered by a combination of an external field and another electron beam hitting the nanotube with a very high multiplication factor (ratio of emitted electrons to the incoming ones) [45]. This could have many applications in nanoscale vacuum transistors and electron detectors. Other nanowires have also been investigated for electron emitter applications, including silicon, zinc oxide, and tungsten nanowires [46–48]. Controllable nanoscale electron emitters are in demand not only in electron beam lithography and microscopy, but also in vacuum nanoelectronics, flat panel display technologies [49, 50], free-electron analog to digital conversion [51], time-resolved electron holography, and synchrotrons. 2.4.3.2. Sensors and Actuators. In order to sense a molecule or particle, one needs a device that shows a measurable change in characteristics as the result of the proximity or adsorption of that particle. In nanostructures, due to the large surface-to-volume ratio, even a single particle sitting on the nanostructure could potentially have a large effect on the nanostructure properties such as electronic transport characteristics. Sensor applications have, therefore, been investigated in nanotubes and nanowires. The advantages of these sensors include very high sensitivity, low-voltage operation, low power consumption, and portability. Examples include gas sensors [52, 53], biosensors [54–56], and chemical sensors

e

Cathode structure

e

e

e

Nanotube tip

Figure 2.14. Schematic representation of a nanoelectron source for vacuum nanoelectronic applications.

50

CHAPTER 2: NANOSCALE DEVICES: APPLICATIONS AND MODELING

[57, 58]. Similarly, the actuation mechanism in nanostructures is being studied actively. For instance, electromechanical actuation in carbon nanotubes has been demonstrated [59, 60] for applications such as artificial muscles. 2.4.3.3. Interconnect. One of the big challenges facing the integrated circuit industry is the issue of interconnect. As devices shrink and are packed more densely, routing the connections between them becomes more complicated; the interconnect lines themselves can severely affect the operation speed and power consumption of the circuit, to the point of becoming a limiting factor. Various approaches are being pursued to address this problem. One solution is to make 3D integrated circuits (as opposed to current planar or 2D circuits), which would create more ways of connecting devices and make shorter paths possible [61]. So far in this chapter we have been discussing the usage of nanomaterials to make devices. It is noteworthy that several research groups are also working on the possibility of using materials such as carbon nanotubes for interconnecting the devices on a circuit [62, 63]. Since these materials can carry large current densities and operate in the ballistic transport regime, this could lead to potentially faster interconnects with less power consumption. 2.4.3.4. Hydrogen Storage. Alternative energy sources are becoming increasingly important and research in this field is very active. Hydrogen-based energy requires the storage of hydrogen in a safe and efficient manner. Carbon nanotubes are being investigated for their potential in storing hydrogen in high densities [64]. 2.4.3.5. Optical Properties of Nanostructures. The focus of this chapter has been mainly on the electronic properties of nanodevices. However, optical properties are closely related to electronic properties; microscale optoelectronic devices are in widespread use. Nanoscale optoelectronic devices are the subject of active research. Examples include lasers based on nanowires [65] and optical emitters [66, 67], detectors [68, 69], and antennas [70] based on carbon nanotubes.

2.5. MODELING AND SIMULATING NANODEVICES 2.5.1. The Art of Modeling In the world of natural sciences and engineering, the art of modeling consists of describing a physical system in terms of parts and phenomena that we can understand based on our knowledge of nature, in the simplest possible manner, in such a way that none of the fundamental aspects of its operation are lost, and that we can use the model to predict/explain the results of experiments on the system. The model often involves a number of mathematical equations that can be solved to explain or to predict experimental outcomes. As a matter of fact, it could be argued that the most fundamental laws of nature, as we know them, are

2.5. MODELING AND SIMULATING NANODEVICES

51

themselves models at the most basic and general level, and they attempt to describe all of nature and its phenomena in one shot. But as long as these models are not derived from more general models and are at the root of our modeling hierarchy, we call them fundamental laws. Before the advent of fast calculating machines and computers, researchers had to rely mainly on solving these equations analytically (as much as possible) before attempting to plug in numbers. In the recent times, modeling is often accompanied by heavy numerical simulations; that is, once a good model is chosen for a given system, predictions on the behavior of the system under various circumstances are done by numerically solving the equations using fast computers. One may ask that if we know the fundamental laws of nature, and if we have a fast computer to solve equations, why can we not always start from those fundamental laws (whether classical or quantum mechanical) and solve the relevant equations for any system in the most general sense? The answer is that this ‘‘firstprinciples’’ approach usually leads to a complex system of interrelated equations that even the most advanced supercomputers cannot handle numerically for a simple physical system. As a consequence, regardless of how good our computers have become, modeling has remained an integral part of studying natural systems. For example, think about an inert gas. The sciences of statistical mechanics and thermodynamics have provided us with an elegant model that describes an ‘‘ideal’’ gas that results in a very simple equation relating its pressure, volume, and temperature. For many a practical application, this model provides a description that is accurate enough to find those parameters, without the need for heavy calculations. In contrast, imagine the practically impossible task of solving the equations of motion for all the atoms in a given volume of gas (trillions of trillions of atoms) every time one needs to study the gas’ expansion as a function of temperature. With the introduction of every new branch of science and engineering, models start being developed (and gradually improved) to describe systems relevant to the discipline. There are well established models for gases, solids, and fluids that engineers use every day to design new devices and systems. We have been very successful so far in coming up with good physical models to describe systems ranging from giant spacecraft all the way down to microelectronic devices. In other words, when designing a spacecraft, an engineer does not start with the behavior of the individual atoms in it, but rather uses the much more high level models of mechanical engineering that describe the system containing a very large number of atoms. Similarly, even in microelectronic devices, a designer/engineer does not look at individual atoms or electrons, but uses the well established equations of microscopic electronic transport in a system containing a large number of atoms and electrons. These cases (spacecraft and microelectronic device) have in common the fact that in both systems there exists such a large collection of atoms that the details of the exact behavior of each individual atom is of little significance to the overall system, and it is the statistical averages of these behaviors that determine what happens. Thus, the fact that there is a large number of atoms to be accounted for is not only not a threat to modeling, but is actually the very reason why such successful macroscopic models can be developed and used.

52

CHAPTER 2: NANOSCALE DEVICES: APPLICATIONS AND MODELING

2.5.2. The Challenge of Nanoscale Modeling If you have two planets interacting with each other through gravitational forces, you can use Newtonian mechanics to trace their motion analytically. Add one more planet to the system (the so called three-body problem) and a closed-form analytical solution will generally not exist. This is also true for interacting electrons and protons. There is no analytical solution to the interacting manybody problem and one will need to resort to numerical methods to study such systems. Although simple in theory, the practical difficulty arises from the fact that with the addition of every new particle to the system, the amount of calculations needed grows considerably. Now let us imagine that we want to study a system that includes only a few electrons. As discussed, we know the fundamental laws that describe the system— that is quantum mechanics. One tends to think that it should not be too hard to analyze such systems with a reasonably good computer. In fact, that might be the case when there are only a few particles involved. However, if there are hundreds or thousands of interacting atoms in the system, such as in nanoscale devices, then the exact solution of the equations of quantum mechanics for the entire system is absurdly out of reach for even the most advanced supercomputers of the modern day. At the same time, hundreds or thousands of atoms do not represent a large enough system where we could neglect the individual character of each atom and simply describe the system in terms of statistical averages. Thus, nanoscale devices present a regime of physical systems—in terms of their size—where we can neither neglect the atomic nature of the structure, nor treat it exactly using numerical methods and fast computers. It is noteworthy that this book focuses on new approaches to making computers with significantly more power than our traditional computers. When such efforts eventually become successful, our method of dealing with nanoscale devices from a modeling and simulation perspective could also change in major ways.

2.5.3. Smart Physical Modeling So how do we deal with nanoscale devices? The solution lies in a smart approach to modeling. Often, a hybrid, multiscale approach is necessary to treat the system: more classical methods for aspects of the system that are less affected by the atomic nature, and more fundamental, quantum mechanical calculations where needed. Another important factor is that often a given property or experimental outcome could be explained based on a small part of the overall device. The art of modeling nanostructures consists of seeing what is essential to retain in a minimal subsystem (that we can handle with our available computing power in reasonable time) in order to study a certain subject relevant to the nanodevice in question. Nanodevices constitute a very new field and there is not, at least not yet, a general approach to modeling all nanodevices (such as is the case for larger devices like microelectronic transistors). Therefore, every researcher working in the field will, at some point, have to deal with modeling the specific system he/she is studying.

2.5. MODELING AND SIMULATING NANODEVICES

53

Nonetheless, there are many different levels of theory that have been developed over the years that could be applied based on the level/depth of the model itself. These include methods ranging from semi-classical treatments of atoms to single-electron methods to lower level methods directly relying on the solution of the fundamental equations of quantum mechanics for all the atoms. In the next few sections we shall briefly introduce some of the common methods in this context.

2.5.4. The Methods Generally speaking, the methods of modeling and simulating nanodevices could be divided into two major categories: the so called ab initio (from the beginning) or first-principles approaches, and methods that have more of a phenomenological or empirical aspect to them. In first-principles methods, as the name suggests, the idea is to start with the basic physical equations for the entire system, such as the Schro¨dinger and Poisson equations, and solve them to find all the desired characteristics like electronic structure or transport properties. The Hartree– Fock theory is one such method that provides a framework for treating the quantum many-body problem by solving the Schro¨dinger equation. As discussed before, this could be a remarkably difficult task to accomplish (in terms of computational complexity) for a reasonably large system such as a nanodevice with hundreds of atoms. Therefore, other methods have been developed that rely on approximations and fitting parameters that, although not as accurate as firstprinciples approaches, depending on the problem at hand could still capture most of the underlying physics and handle much larger systems in a practical manner. Molecular dynamics and tight-binding approximations are some important examples in this category. 2.5.4.1. Ab Initio (First-Principles) Approaches. Quantum mechanics and relativity are the theories that describe the world around us (the best theories we have so far, though not necessarily the absolute truth!). In everyday experiences, quantum mechanical and relativistic effects are often masked and simpler theories, such as Newtonian mechanics, provide an accurate enough description. At very small scales, such as the nanoscale, quantum mechanical effects are dominant (although relativistic effects can be negligible in many nanodevice applications). We will begin our discussion here with a quick look at what is at the heart of quantum mechanics. In one common approach to quantum mechanics, the behavior of a particle can be described by the Schro¨dinger equation: HC ¼ eC: Here, H is the so called Hamiltonian operator of the system, including both potential and kinetic energy terms and e represents the allowed energies in the system. Particles are described in terms of waves (C). The amplitude of the wave

54

CHAPTER 2: NANOSCALE DEVICES: APPLICATIONS AND MODELING

represents the probability of the particle being at a given location. (You cannot know for sure where a particle is; rather, you have a probability distribution for its existence in various locations in space. To the best of our knowledge so far, this is the reality, but it might sound counterintuitive because this reality reveals itself only at small scales, and so we are not used to it in everyday life.) Note that the Schro¨dinger equation is, in general, a time-dependent differential equation. Here we have shown the time-independent case just for the sake of introduction. At the root of modeling a nanoscale device is the problem of writing the above equation for the system by including the proper terms in the Hamiltonian and solving it to find C and e. From C and e one can proceed to finding other parameters of interest in the system. Thus, for nanoscale modeling, learning quantum mechanics, at least at an introductory level, is the first necessary step. The reader is referred to [71, 72] as good examples of quantum mechanics textbooks. Finding a solution to the above equation without invoking empirical parameters is what ab initio approaches try to accomplish. SLATER DETERMINANTS AND THE HARTREE–FOCK METHOD. In one simplification, exact instantaneous electron–electron interactions are neglected in studying a system of atoms. The problem is reduced to that of a single electron moving in the ‘‘average’’ field created by the rest of the system. This approximation is very useful in many practical cases and captures the basic physics of the problem while greatly simplifying the computational complexity. When trying to solve the Schro¨dinger equation in this case, one can represent the overall wave function C of the system as products of individual wave functions for electrons; this is basically the technique of separation of variables in solving differential equations. In addition, Pauli’s exclusion principle that no two electrons with the same spin can reside in the same state must be satisfied. This, together with the fact that electrons are indistinguishable particles from one another, requires that the system wave function be antisymmetric with respect to simultaneous change of spin and space coordinates of electrons. A general form for the many-body wave function that satisfies this condition is the so called Slater determinant [73, 74]:    f1 ð1Þ f1 ð2Þ    f1 ðN Þ       f2 ð1Þ f2 ð2Þ    f2 ðN Þ    C/ . ..  .. ..  .. .  . .     f N ð 1 Þ f N ð 2Þ    f N ð N Þ  In the above each f represents a single-electron wave function (including the spin part). Since swapping two rows or columns in a determinant changes the sign, this form satisfies the antisymmetry condition. In the Hartree–Fock method, the wave function of the system is obtained in the form of a Slater determinant. More on this method can be found in [74, 75]. Although this method neglects electron–electron correlation (i.e., the instantaneous nature of electron–electron

2.5. MODELING AND SIMULATING NANODEVICES

55

interactions as they move in their complex orbitals), it can often provide a good insight into the physics of a problem and even make relatively good quantitative predictions as well. For instance, this method has shown to be quite effective in finding the occupied orbitals of carbon nanotubes and ionization energies of several molecular systems [76, 77]. THE DENSITY FUNCTIONAL THEORY. The density functional theory (DFT) is perhaps the most celebrated of approaches to solving the quantum many-body problem and has become increasingly popular in modeling and simulating solid materials including nanostructures. DFT provides a framework to accurately treat the quantum many-body problem. So, in principle it could be classified as a firstprinciples approach. However, later we will see that in practical implementations of DFT one needs to use approximate descriptions for the so called exchange– correlation energy. Therefore, DFT is not always necessarily considered an ab initio technique. Nonetheless, due to the fact that it does not essentially rely on empirical data, it is included in this section. A paper published by Hohenberg and Kohn in 1964 [78] demonstrates that in treating an N-body problem, instead of working with the coordinates of all individual particles (electrons and nuclei), one can use a particle density distribution in space. This remarkably simplifies the problem and brings it to a much more manageable level. This is accomplished on the basis of the two following theorems, proven in that seminal paper [75, 78]: 1. The external potential acting on a fully interacting many-particle system in the ground state is determined uniquely by its electron density distribution in space. (Obviously we can add a constant to the potential everywhere without any real effect). 2. The ground state energy of the system (with the correct density) is smaller than the energy in any other configuration (with any other trial density). The first theorem enables one to transform the many-body Schro¨dinger equation to an equation for the particle density functional. The second theorem provides a variational principle to solve the equation by finding the density distribution that minimizes the resulting energy for the system, which will be its ground state. A formal approach to finding the solution was proposed by Kohn and Sham in 1965 [79]. The key to this approach is that, using the introduction of an effective potential, the equation for the interacting many-body system is rewritten in such a way that it looks like the equation for a system of noninteracting particles. Then this equation is solved in a self-consistent manner as follows: one makes a guess for the density distribution, uses it to find the effective potential, uses the effective potential to find the orbitals (which is feasible since the equation looks like the one for noninteracting particles), and then calculates the electron density again from these orbitals. This process is continued until the density converges, and then one will have the ground state energy,

56

CHAPTER 2: NANOSCALE DEVICES: APPLICATIONS AND MODELING

orbitals and density. This cycle of iterations to find the solution is common to many methods including DFT and Hartree–Fock and therefore these methods are referred to as Self-Consistent Field (SCF) methods. It should be noted that no miracle is performed in DFT. In following the Kohn–Sham method, a term called the exchange–correlation energy appears in the equations, due to both the quantum mechanical nature of particles and the fact that they are interacting. But this term is not known exactly. Therefore, the final solution will be approximate. There is indeed ongoing work on finding improved descriptions for the exchange–correlation energy in various systems [75]. One of the most widely established methods is the so called local density approximation (LDA). Here, the exchange–correlation energy for the system at each point in space is taken to be equal to that of a system with a uniform density that is the density in the actual system at that location. Despite the fact that the lack of an exact exchange–correlation energy makes the results obtained by DFT approximate (like other methods), it is important to note that DFT is, in principle, a rigorous approach and is not based on a simplified model for the system. As such, it provides a way not only to understand what approximations one is making (when choosing the exchange–correlation functional) but also to improve those approximations in a systematic manner. In this regard, it also helps to put some of the other methods (that are based on simplified models of the real problem) into perspective and to provide a means of analyzing how accurate they are. For a very well written summary on DFT the reader is encouraged to consult [75]. For more detail [80–82] can be used. 2.5.4.2. Semi-Empirical Methods. As pointed out before, starting from first principles and solving the many-body quantum mechanical problem can often be a formidable task even for the most advanced computers. Therefore, methods have been developed that, in addition to theory, use empirical data to provide simplified descriptions of many-particle systems. Molecular dynamics, tight-binding, and Monte Carlo approaches are some of the popular methods of this genre. CLASSICAL MOLECULAR DYNAMICS. The basic idea in molecular dynamics is to represent the interaction between each two atoms as a mean field arising from the interaction of all individual electrons and nuclei. For example, in the case of two carbon atoms instead of trying to calculate the force between them as the sum of the attractive and repulsive forces between all the individual electrons and protons (6 protons and 6 electrons in each atom, resulting in a total of 12*12=144 complex interactions), a semi-empirical model for the force between the two atoms would be used. This force would be expressed as a function of the relative positioning of the two atoms with a number of parameters that are obtained by fitting the predictions of the model to available experimental data. In very simple terms, the potential energy resulting from the interaction of two atoms could be something like the curve in Figure 2.15. Since force is the negative of the derivative of potential energy with respect to position, it can be seen that if

2.5. MODELING AND SIMULATING NANODEVICES

57

Potential energy Equilibrium point

d

Interatomic distance

Figure 2.15. A simple representation of the interaction potential energy of two atoms.

the two atoms are a distance d apart, they are in equilibrium. If they are pushed closer, the force between them will be repulsive. If they are pulled farther, the force between them will be attractive. Both cases would lead to the atoms going back to their equilibrium distance. Here is how molecular dynamics works in principle: consider a system of a number of atoms. We place them in close proximity and would like to find what the equilibrium position of each atom in the ‘‘relaxed’’ structure would be. We can start by calculating the force on each atom resulting from the rest of the atoms, using curves such as the one in Figure 2.15. Then, using Newton’s equation of motion F=ma, we can calculate the acceleration on each atom due to this force. Now we let all the atoms move under these accelerations for a very small duration of time—a duration short enough that we can assume the force (and, as a result, acceleration) on each atom does not change significantly during that time. After this very short time, we have the new locations of the atoms and their new velocities. From the new locations we can calculate the new accelerations each will be feeling, and then move in time one more short step. If we repeat this process for a large enough number of time steps, at some point we will see that the atoms will not move significantly any longer as time passes. This will be the equilibrium or relaxed configuration of the system. One way to see this is to plot the total potential energy (the sum of all atom–atom interactions) of the system as a function of time. Eventually, this curve will saturate and asymptotically go toward the relaxed energy of the system. One important issue to consider is that the system could converge to the metastable state closest to where we started from (in terms of initial choice of atomic positions). Therefore, in order to find the global minimum energy configuration of the structure, one may need to repeat the simulation with various choices of initial configurations and compare the end results in terms of total energy, or incorporate mechanisms to ‘‘kick’’ the system out of metastable configurations (using parameters such as thermal energy) with the hope that it will find its global minimum. Many variations of molecular dynamics are in use today and they can handle systems of relatively large numbers of atoms (thousands or tens of thousands of atoms) in reasonable time on present day

58

CHAPTER 2: NANOSCALE DEVICES: APPLICATIONS AND MODELING

computers. There have also been many valuable attempts at modeling the interatomic interactions for use in molecular dynamics simulations. One good example is the Brenner–Tersoff potentials that are well established for describing hydrocarbon systems [83, 84]. For a detailed review of molecular dynamics the reader is referred to [85]. TIGHT-BINDING. One way to approach a problem involving multiple atoms is to try to solve the Schro¨dinger equation by finding an expanded form for the expected solution. It is customary to write the solution in the form of a linear combination of atomic orbitals (LCAO), that is, as a weighted sum of wave functions that have been found for individual, isolated atoms. The parameters involved could be derived from first-principles methods. In many cases, however, these can be found from elsewhere, such as using experimental data. For instance, the core of an atom could be represented by a pseudopotential, instead of explicitly including all the individual electron contributions, just like in molecular dynamics. Thus, as opposed to exact, real orbitals, the atom will be represented by parameters derived by fitting to other available data. In such cases, especially when interactions with close neighbors are considered only, the LCAO method would typically be referred to as the tight-binding (TB) approximation. TB has the advantage of being computationally much less expensive than ab initio methods and therefore capable of providing, at least, a qualitative description of the behavior of a relatively large system quickly. For more on LCAO methods and TB, [86–88] can be studied. MONTE CARLO. Monte Carlo methods are in place in many disciplines. The basic idea is to start from a known point and trace the behavior of a system by following a random-walk process. In each state, the system has the possibility of going to several of subsequent states with different probabilities. The choice of which one of those states the system will go into at each step is decided by a random process that is weighted by those different probabilities. For instance, consider the movement of an atom sitting on a crystalline surface through a loose bond. This atom moves around due to its thermal, kinetic energy. At each point, there exists several sites around it for it to move to. There would be a potential barrier in front of the atom to cross in order to make the transition to any of these sites, but the barriers have different heights and widths for the different sites, which correspond to different transition probabilities. The random walk of this atom could be traced using the Monte Carlo approach. Both semiclassical and quantum Monte Carlo methods are widely in use in nanoscale modeling [89, 90]. 2.5.4.3. Use of Green’s Functions. Green’s functions are powerful tools in solving differential equations. Since the goal in nanosale modeling is to find the solution to the Schro¨dinger equation, which is a differential equation, Green’s functions often come in very handy. In particular, they provide a useful way of dealing with problems involving open boundary systems. Consider, for example, a QD or SET connected to two large metal contacts on the sides. Although the

2.6. CONCLUSIONS

59

device itself is small (nanoscale), the contacts are usually very large (microscale) and could be treated as semi-infinite systems for the purposes of the analysis. The use of Green’s functions greatly simplifies the problem in such cases. In particular, problems involving electronic transport usually have contacts playing a crucial role and thus the so called nonequilibrium Green’s function (NEGF) formalism is commonly used. Moreover, Green’s functions provide a way of dealing with interparticle interactions in electronic transport modeling. For a study of Green’s functions with application to transport problems in nanostructures the reader is referred to [91–93]. 2.5.4.4. System-Level Modeling. Although most of the research in the field of nanodevices is currently focused on the device itself, it is noteworthy that valuable efforts are being made on system-level issues, such as designing circuits based on these novel nanodevices and analyzing such systems. Researchers have worked on circuit design paradigms for future computers based on QD-type devices such as quantum dot cellular automata (QCA) [94]. Although this research is very new, even compared to the field of nanodevices itself, there are already examples of computer-aided design (CAD) tools that have been developed for circuit design applications. An example is the software called QCADesigner [95].

2.6. CONCLUSIONS There are various methods that could be used for the analysis of a given device depending on the aspects being studied. For instance, classical molecular dynamics usually gives an accurate enough result for the mechanical structure of the system, but does not provide much in the way of electronic structure. DFT gives very accurate results for electronic structure and can be used to relax the mechanical structure of the system, although it is extremely expensive computationally. To illustrate how these various methods could be used in practice, let us consider the example of a carbon nanotube with a length of 10 nm connected between two metal electrodes to form a quantum dot. One way to approach the problem of electronic transport in this device is the following: the coordinates of the carbon atoms as well as those of the metal atoms in the contact electrodes are generated based on the lattice structures of the nanotube and the electrode. However, we know that once a short section (10 nm) of the nanotube is cut and put in contact with the electrodes, the atoms, especially at the edges, rearrange themselves slightly. A molecular dynamics simulation is run to determine the exact location of all the atoms in the metal-nanotube-metal structure. Then both DFT and TB are used to determine the electronic structure (orbitals or band structure), while using the NEGF approach to study the transport characteristics. If the current as a function of applied voltage is to be found, it would mean a series of electronic structure calculations with different system Hamiltonians (each reflecting a single bias point). This is very time consuming with DFT. So, one could use TB for this, and at the same time use DFT for some of the bias

60

CHAPTER 2: NANOSCALE DEVICES: APPLICATIONS AND MODELING

points to have a benchmark for comparison in order to evaluate the accuracy of the TB results. The objective of this chapter was to provide an introduction to the world of nanodevices. We briefly reviewed the motivations behind making devices at the small scale, the process of how they are made, some of their applications, and some of the common methods of studying and simulating them. Entering any level of detail in those subjects is obviously beyond the scope of this single chapter, but the author hopes that the chapter shows the big picture of what to expect in this area and how to pursue a given direction of interest.

REFERENCES 1. R. P. Feynman. There’s plenty of room at the bottom [data storage]. Journal of Microelectromechanical Systems, 1: pp 60–66, 1992. 2. Y. Wu, Y. Cui, L. Huynh, C. J. Barrelet, D. C. Bell, and C. M. Lieber. Controlled growth and structures of molecular-scale silicon nanowires. Nano Letters, 4: pp 433–436, 2004. 3. D. Wang, Q. Wang, A. Javey, R. Tu, H. Dai, H. Kim, P. C. McIntyre, T. Krishnamohan, and K. C. Saraswat. Germanium nanowire field-effect transistors with SiO2 and high-k HfO2 gate dielectrics. Applied Physics Letters, 83: pp 2432–2434, 2003. 4. Y. C. Kong, D. P. Yu, B. Zhang, W. Fang, and S. Q. Feng. Ultraviolet-emitting ZnO nanowires synthesized by a physical vapor deposition approach. Applied Physics Letters, 78: pp 407–409, 2001. 5. Y. Huang, X. Duan, Y. Cui, and C. M. Lieber, Gallium nitride nanowire nanodevices. Nano Letters, 2: pp 101–104, 2002. 6. S. Iijima. Helical microtubules of graphitic carbon. Nature, 354: pp 56–58, 1991. 7. R. Saito, G. Dresselhaus, and M. S. Dresselhaus. Physical Properties of Carbon Nanotubes. London: Imperial College Press, 1998. 8. J. D. Plummer, M. Deal, and P. B. Griffin. Silicon VLSI Technology: Fundamentals, Practice, and Modeling. Upper-Saddle River, NJ: Prentice Hall, 2000. 9. C. Liu. Foundations of MEMS. Upper Saddle River, NJ: Pearson/Prentice Hall, 2006. 10. J. Kong, H. T. Soh, A. M. Cassell, C. F. Quate, and H. Dai. Synthesis of individual single-walled carbon nanotubes on patterned silicon wafers. Nature, 395: pp 878–881, 1998. 11. A. Ural, Y. Li, and H. Dai. Electric-field-aligned growth of single-walled carbon nanotubes on surfaces. Applied Physics Letters, 81: p 3464, 2002. 12. A. Nojeh, A. Ural, R. F. Pease, and H. Dai. Electric-field-directed growth of carbon nanotubes in two dimensions. Journal of Vacuum Science and Technology B, 22: pp 3421–3425, 2004. 13. S. Huang, X. Cai, and J. Liu. Growth of millimeter-long and horizontally aligned single-walled carbon nanotubes on flat substrates. Journal of the American Chemical Society, 125: pp 5636–5637, 2003.

REFERENCES

61

14. S. Huang, M. Woodson, R. Smalley, and J. Liu. Growth mechanism of oriented long single walled carbon nanotubes using fast-heating chemical vapor deposition process. Nano Letters, 4: pp 1025–1028, 2004. 15. D. Goldhaber-Gordon, M. S. Montemerlo, J. C. Love, G. J. Opiteck, and J. C. Ellenbogen. Overview of nanoelectronic devices. Proceedings of the IEEE, 85: pp 521–540, 1997. 16. M. A. Kastner. The single electron transistor and artificial atoms. Annalen der Physik (Leipzig), 9: pp 11–12, 2000. 17. L. J. Geerligs, V. F. Anderegg, P. A. M. Holweg, J. E. Mooij, H. Pothier, D. Esteve, C. Urbina, and M. H. Devoret. Frequency-locked turnstile device for single electrons. Physical Review Letters, 64: pp 2691–2694, 1990. 18. C. W. J. Beenakker. Theory of Coulomb-blockade oscillations in the conductance of a quantum dot. Physical Review B, 44: pp 1646–1656, 1991. 19. Y. Alhassid. The statistical theory of quantum dots. Reviews of Modern Physics, 72: pp 895–968, 2000. 20. K. Matsumoto, M. Ishii, K. Segawa, Y. Oka, B. J. Vartanian, and J. S. Harris. Room temperature operation of a single electron transistor made by the scanning tunneling microscope nanooxidation process for the TiO[sub x]/Ti system. Applied Physics Letters, 68: pp 34–36, 1996. 21. Y. Cui, Z. Zhong, D. Wang, W. U. Wang, and C. M. Lieber. High performance silicon nanowire field effect transistors. Nano Letters, 3: pp 149–152, 2003. 22. J. Goldberger, D. J. Sirbuly, M. Law, and P. Yang. ZnO nanowire transistors. Journal of Physical Chemistry B, 109: pp 9–14, 2005. 23. S. Han, W. Jin, D. Zhang, T. Tang, C. Li, X. Liu, Z. Liu, B. Lei, and C. Zhou. Photoconduction studies on GaN nanowire transistors under UV and polarized UV illumination. Chemical Physics Letters, 389: pp 176–180, 2004. 24. J. Appenzeller, J. Knoch, V. Derycke, R. Martel, S. Wind, and P. Avouris. Fieldmodulated carrier transport in carbon nanotube transistors. Physical Review Letters, 89: p 126801, 2002. 25. A. Javey, H. Kim, M. Brink, Q. Wang, A. Ural, J. Guo, P. McIntyre, P. McEuen, M. Lundstrom, and H. Dai. High-k dielectrics for advanced carbon-nanotube transistors and logic gates. Nature Materials, 1: pp 241–246, 2002. 26. A. Javey, J. Guo, Q. Wang, M. Lundstrom, and H. Dai. Ballistic carbon nanotube field-effect transistors. Nature, 424: pp 654–657, 2003. 27. A. Bachtold, P. Hadley, T. Nakanishi, and C. Dekker. Logic circuits with carbon nanotube transistors. Science, 294: p 1317, 2001. 28. S. Li, Z. Yu, S. F. Yen, W. C. Tang, and P. J. Burke. Carbon nanotube transistor operation at 2.6 GHz. Nano Letters, 4: pp 753–756, 2004. 29. J. Wang, A. Rahman, A. Ghosh, G. Klimeck, and M. Lundstrom. Performance evaluation of ballistic silicon nanowire transistors with atomic-basis dispersion relations. Applied Physics Letters, 86: p 093113, 2005. 30. J. P. Clifford, D. L. John, L. C. Castro, and D. L. Pulfrey. Electrostatics of partially gated carbon nanotube FETs. IEEE Transactions on Nanotechnology, 3: pp 281–286, 2004.

62

CHAPTER 2: NANOSCALE DEVICES: APPLICATIONS AND MODELING

31. D. L. John and D. L. Pulfrey. Switching-speed calculations for Schottky-barrier carbon nanotube field-effect transistors. Journal of Vacuum Science and Technology A: Vacuum, Surfaces, and Films, 24: p 708, 2006. 32. L. C. Castro and D. L. Pulfrey. Extrapolated fmax for carbon nanotube field-effect transistors. Nanotechnology, 17: pp 300–304, 2006. 33. N. Mason, M. J. Biercuk, and C. M. Marcus. Local gate control of a carbon nanotube double quantum dot. Science (AAAS), 303: pp 655–658, 2004. 34. M. T. Woodside and P. L. McEuen. Scanned Probe Imaging of Single-Electron Charge States in Nanotube Quantum Dots. Science, 296: pp 1098–1101, 2002. 35. S. Peng and K. Cho. Nano electro mechanics of semiconducting carbon nanotube. Journal of Applied Mechanics (Transactions of the ASME), 69: pp 451–453, 2001. 36. H. W. C. Postma, T. Teepen, Z. Yao, M. Grifoni, and C. Dekker. Carbon Nanotube Single-Electron Transistors at Room Temperature. Science, 293: pp 76–79, July 2001. 37. B. Shan, G. W. Lakatos, S. Peng, and K. Cho. First-principles study of band-gap change in deformed nanotubes. Applied Physics Letters, 87: p 173109, 2005. 38. A. Nojeh, G. W. Lakatos, S. Peng, K. Cho, and R. F. W. Pease. A carbon nanotube cross structure as a nanoscale quantum device. Nano Letters, 3: pp 1187–1190, 2003. 39. L. Vitali, M. Burghard, P. Wahl, M. A. Schneider, and K. Kern. Local pressureinduced metallization of a semiconducting carbon nanotube in a crossed junction. Physical Review Letters, 96: p 86804, 2006. 40. K. A. Dean and B. R. Chalamala. Current saturation mechanisms in carbon nanotube field emitters. Applied Physics Letters, 76: pp 375–377, 2000. 41. N. de Jonge, M. Allioux, J. T. Oostveen, K. B. K. Teo, and W. I. Milne. Optical performance of carbon-nanotube electron sources. Physical Review Letters, 94: pp 186807–186804, 2005. 42. N. de Jonge and J-M Bonard. Carbon nanotube electron sources and applications. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 362: pp 2239–2266, 2004. 43. T. Fujieda, K. Hidaka, M. Hayashibara, T. Kamino, H. Matsumoto, Y. Ose, H. Abe, T. Shimizu, and H. Tokumoto. In situ observation of field emissions from an individual carbon nanotube by Lorenz microscopy. Applied Physics Letters, 85: pp 5739–5741, 2004. 44. P. G. Collins and A. Zettl. Unique characteristics of cold cathode carbon-nanotubematrix field emitters. Physical Review B, 55: 1997 p 9391, 1997. 45. A. Nojeh, W. K. Wong, E. Yieh, R. F. Pease, and H. Dai. Electron beam stimulated field-emission from single-walled carbon nanotubes. Journal of Vacuum Science and Technology B: Microelectronics and Nanometer Structures, 22: pp 3124–3127, 2004. 46. A. I. Klimovskaya, Y. M. Litvin, Y. Y. Moklyak, A. A. Dadykin, T. I. Kamins, and S. Sharma. Field-electron emission at 300 K in self-assembled arrays of silicon nanowires. Applied Physics Letters, 89: pp 093122–093123, 2006. 47. C. J. Lee, T. J. Lee, S. C. Lyu, Y. Zhang, H. Ruh, and H. J. Lee. Field emission from well-aligned zinc oxide nanowires grown at low temperature. Applied Physics Letters, 81: p 3648, Nov 2002.

REFERENCES

63

48. A. G. Umnov, Y. Shiratori, and H. Hiraoka. Giant field amplification in tungsten nanowires. Applied Physics A: Materials Science and Processing, 77: pp 159–161, 2003. 49. J. L. Kwo, M. Yokoyama, W. C. Wang, F. Y. Chuang, and I. N. Lin. Characteristics of flat panel display using carbon nanotubes as electron emitters. Diamond and Related Materials, 9: pp 1270–1274, 2000. 50. S. G. Yu, S. Jin, W. Yi, J. Kang, T. Jeong, Y. Choi, J. Lee, J. Heo, N. S. Lee, and J. B. Yoo. Undergate-type Triode Carbon Nanotube Field Emission Display with a Microchannel Plate. Japanese Journal of Applied Physics, 40: pp 6088–6091, 2001. 51. K. Ioakeimidi, R. F. Leheny, S. Gradinaru, P. R. Bolton, R. Aldana, K. Ma, J. E. Clendenin, J. S. Harris, and R.F.W. Pease. Photoelectronic analog-to-digital conversion: sampling and quantizing at 100 Gs/s. IEEE Transactions on Microwave Theory and Techniques, 53: pp 336–342, 2005. 52. A. Modi, N. Koratkar, E. Lass, B. Wei, and P. M. Ajayyan. Miniaturized gas ionization sensors using carbon nanotubes. Nature, 424: pp 171–174, 2003. 53. C. S. Rout, A. Govindaraj, and C. N. R. Rao. High-sensitivity hydrocarbon sensors based on tungsten oxide nanowires. Journal of Materials Chemistry, 16: pp 3936–3941, 2006. 54. S. Sotiropoulou and N. A. Chaniotakis. Carbon nanotube array-based biosensor. Analytical and Bioanalytical Chemistry, 375: pp 103–105, 2003. 55. K. Besteman, J. O. Lee, F. G. M. Wiertz, H. A. Heering, and C. Dekker. Enzyme-coated carbon nanotubes as single-molecule biosensors. Nano Letters, 3: pp 727–730, 2003. 56. G. Zheng, F. Patolsky, Y. I. Cui, W. U. Wang, and C. M. Lieber. Multiplexed electrical detection of cancer markers with nanowire sensor arrays. Nature Biotechnology, 23: pp 1294–1301, 2005. 57. J. Kong, N. R. Franklin, C. Zhou, M. G. Chapline, S. Peng, K. Cho, and H. Dai. Nanotube molecular wires as chemical sensors. Science, 287: pp 622–625, 2000. 58. X. Y. Xue, Y. J. Chen, Y. G. Wang, and T. H. Wang. Synthesis and ethanol sensing properties of ZnSnO nanowires. Applied Physics Letters, 86: p 233101, 2005. 59. R. H. Baughman, C. Cui, A. A. Zakhidov, Z. Iqbal, J. N. Barisci, G. M. Spinks, G. G. Wallace, A. Mazzoldi, D. De Rossi, and A. G. Rinzler. Carbon nanotube actuators. Science, 284: pp 1340–1344, 1999. 60. T. Mirfakhrai, J. Oh, M. Kozlov, E. C. W. Fok, M. Zhang, S. Fang, R. H. Baughman, and J. D. W. Madden. Electrochemical actuation of carbon nanotube yarns. Smart Materials and Structures, 16: pp S243–S249, 2007. 61. M. Ieong, K. W. Guarini, V. Chan, K. Bernstein, R. Joshi, J. Kedzierski, and W. Haensch. Three-dimensional CMOS devices and integrated circuits, Custom Integrated Circuits Conference, 2003. Proceedings of the IEEE 2003: pp 207–213, 2003. 62. A. Raychowdhury and K. Roy. Modeling of metallic carbon-nanotube interconnects for circuit simulations and a comparison with Cu interconnects for scaled technologies. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 25: pp 58–65, 2006. 63. A. Nieuwoudt and Y. Massoud. Understanding the impact of inductance in carbon nanotube bundles for VLSI interconnect using scalable modeling techniques. IEEE Transactions on Nanotechnology, 5: pp 758–765, 2006.

64

CHAPTER 2: NANOSCALE DEVICES: APPLICATIONS AND MODELING

64. F. L. Darkrim, P. Malbrunot, and G. P. Tartaglia. Review of hydrogen storage by adsorption in carbon nanotubes. International Journal of Hydrogen Energy, 27: pp 193–202, 2002. 65. M. H. Huang, S. Mao, H. Feick, H. Yan, Y. Wu, H. Kind, E. Weber, R. Russo, and P. Yang. Room-temperature ultraviolet nanowire nanolasers. Science, 292: p 1897, 2001. 66. M. Freitag, J. Chen, J. Tersoff, J. C. Tsang, Q. Fu, J. Liu, and P. Avouris. Mobile ambipolar domain in carbon-nanotube infrared emitters. Physical Review Letters, 93: pp 076803–076804, 2004. 67. D. L. McGuire and D. L. Pulfrey. A multi-scale model for mobile and localized electroluminescence in carbon nanotube field-effect transistors. Nanotechnology, 17: pp 5805–5811, 2006. 68. M. Freitag, Y. Martin, J. A. Misewich, R. Martel, and P. Avouris. Photoconductivity of single carbon nanotubes. Nano Letters, 3: pp 1067–1071, 2003. 69. P. Servati, A. Colli, S. Hofmann, Y. Q. Fu, P. Beecher, Z. A. K. Durrani, A. C. Ferrari, A. J. Flewitt, J. Robertson, and W. I. Milne. Scalable silicon nanowire photodetectors. Physica E: Low-dimensional Systems and Nanostructures, 3: pp 64–66, 2007. 70. Y. Wang, K. Kempa, B. Kimball, J. B. Carlson, G. Benham, W. Z. Li, T. Kempa, J. Rybczynski, A. Herczynski, and Z. F. Ren. Receiving and transmitting light-like radio waves: antenna effect in arrays of aligned carbon nanotubes. Applied Physics Letters, 85: pp 2607–2609, 2004. 71. J. J. Sakurai. In: S. F. Tan, editor. Modern Quantum Mechanics. Reading, MA: Addison-Wesley, 1994. 72. W. A. Harrison. Applied Quantum Mechanics. Singapore: World Scientific, 2000. 73. J. C. Slater. The Theory of Complex Spectra. Physical Review, 34: pp 1293–1322, 1929. 74. A. Szabo´ and N. S. Ostlund. Modern Quantum Chemistry: Introduction to Advanced Electronic Structure Theory. New York: Dover Publications, 1996. 75. A. Gonis. Theoretical Materials Science: Tracing the Electronic Origins of Materials Behavior. Warrendale, PA: Materials Research Society, 2000. 76. A. Rose´n, D. E. Ellis, H. Adachi, and F. W. Averill. Calculations of molecular ionization energies using a self-consistent-charge Hartree–Fock–Slater method. The Journal of Chemical Physics, 65: p 3629, 1976. 77. A. Nojeh, B. Shan, K. Cho, and R. F. W. Pease. Ab initio modeling of the interaction of electron beams and single-walled carbon nanotubes. Physical Review Letters, 96: p 56802, 2006 78. P. Hohenberg and W. Kohn. Inhomogeneous electron gas. Physical Review, 136: p B864, 1964. 79. W. Kohn and L. J. Sham. Self-consistent equations including exchange and correlation effects. Physical Review, 140: p A1133, 1965. 80. R. G. Parr and W. Yang. Density-Functional Theory of Atoms and Molecules. Oxford, UK: Oxford University Press, 1989 81. S. Lundqvist and N. H. March. Theory of The Inhomogeneous Electron Gas. New York: Plenum Press, 1983. 82. R. M. Dreizler and E. K. U. Gross. Density Functional Theory. New York: Springer, 1990. 83. J. Tersoff. Modeling solid-state chemistry: interatomic potentials for multicomponent systems. Physical Review B, 39: pp 5566–5568, 1989.

REFERENCES

65

84. D. W. Brenner. Empirical potential for hydrocarbons for use in simulating the chemical vapor deposition of diamond films, Physical Review B, vol. 42: pp 9458–9471, 1990. 85. P. B. Balbuena and J. M. Seminario. Molecular Dynamics: From Classical to Quantum Methods. Amsterdam: Elsevier, 1999. 86. J. Lowe and K. Peterson. Quantum Chemistry. Amsterdam. Boston: Elsevier Academic Press, 2006. 87. W. A. Harrison. Elementary Electronic Structure. Singopore: World Scientific, 2004. 88. H. Eschrig. Optimized LCAO Method and the Electronic Structure of Extended Systems. Berlin: Springer-Verlag, 1989. 89. M. Suzuki, editor. Quantum Monte Carlo Methods in Equilibrium and Nonequilibrium Systems: Proceedings of the Ninth Taniguchi International Symposium, Susono, Japan, November 14–18, 1986. Berlin: Springer-Verlag, 1987. 90. M. H. Kalos, editor. Monte Carlo Methods in Quantum Problems. New York: D. Reidel Pub. Co.; sold and distributed in the U.S. and Canada by Kluwer Academic Publishers, 1984. 91. S. Datta. Electronic Transport in Mesoscopic Systems. Cambridge: Cambridge University Press, 2003. 92. M. S. Lundstrom and J. Guo. Nanoscale Transistors: Device Physics, Modeling and Simulation. New York: Springer, 2006. 93. E. N. Economou. Green’s Functions in Quantum Physics. Berlin: Springer-Verlag, 2006. 94. W. Porod. Quantum-dot devices and quantum-dot cellular automata. International Journal of Bifurcation and Chaos, 7: pp 2199–2218, 1997. 95. K. Walus, T. J. Dysart, G. A. Jullien, and R. A. Budiman. QCADesigner: a rapid design and simulation tool for quantum-dot cellular automata. IEEE Transactions on Nanotechnology, 3: pp 26–31, 2004.

3 QUANTUM COMPUTING John H. Reif Quantum computation (QC) is a type of computation where unitary and measurement operations are executed on linear superpositions of basis states. This chapter provides a brief introduction to QC. We begin with a discussion of basic models for QC such as quantum TMs, quantum gates, and circuits and related complexity results. We then discuss a number of topics in quantum information theory including bounds for quantum communication and I/O complexity, methods for quantum data compression and quantum error correction (that is, techniques for decreasing decoherence errors in QC), Furthermore, we enumerate a number of methodologies and technologies for doing QC. Finally, we discuss resource bounds for QC including bonds for processing time, energy, and volume, particularly emphasizing challenges in determining volume bounds for observation apparatus.

3.1. INTRODUCTION 3.1.1. Reversible Computations Reversible computations are computations where each state transformation is a reversible function, so that any computation can be reversed without loss of information. Landauer [1] showed that irreversible computations must generate heat in the computing process, and that reversible computations have the property that if executed slowly enough, they (in the limit) can consume no energy in an adiabatic computation. Bennett [2] (also see Bennett, Landauer [3], Landauer [4], Toffoli [5]) showed that any computing machine (e.g., an abstract machine such as

Bio-Inspired and Nanoscale Integrated Computing. Edited by Mary Mehrnoosh Eshaghian-Wilner Copyright r 2009 John Wiley & Sons, Inc.

68

CHAPTER 3: QUANTUM COMPUTING

a Turing Machine) can be transformed to do reversible computations. Bennett’s reversibility construction required extra space to store information to insure reversibility; Li Vitanyi [6] give tradeoffs between time and space in the resulting reversible machine. An innovative technique due to Bennett [2, 7] can be used to make reversible functions bijective, as required for quantum computations. Given a bijective function f, suppose we can reversibly compute in time T(x) a bijective function f and it’s inverse f1 using auxiliary registers for storage of the input. He proves in time O(T(n)) we can also reversibly compute the bijective mapping, ðx; 0; 0Þ ! ð f ðxÞ; 0; 0Þ, without use of auxiliary registers for storage of the input.

3.1.2. An Introduction to Quantum Computation Computations and methods that do not make use of quantum mechanics will be termed classical. In contrast, quantum computation (QC) applies quantum mechanics to do computation. A single molecule (or collection of particles and/or atoms) may have a number n of degrees of freedom known as qubits. Associated with each fixed setting X of the n qubits to Boolean values is a basis state denoted 7aS. Quantum mechanics allows for a linear superposition (also termed an entangled quantum state) of these basis states to exist simultaneously. Each basis state 7aS of the superposition is assigned a given complex amplitude a; this is denoted a 7aS. Unitary transformations are reversible operations on the superpositions which can be represented by unitary matrices A (e.g., permutation matrices, rotation matrices, and the matrices of Fourier transforms) where AAT=I. The sum of the squares of the magnitudes of the amplitudes of all basis states is 1. This sum remains invariant due to the application of a unitary transformations. The Hilbert space Hn is the set of all possible such linear superpositions. QC is a method of computation where various operations can be executed on these superpositions:  unitary operations, and  observation operations, which allow for the (strong) measurement of each qubit, providing a mapping from the current superposition to a superposition where the measured qubit is assigned a Boolean value with probability given by the square of the amplitude of the qubit in its original superposition. Elementary unitary operations that suffice for any quantum computation over qubits (see [8] and [9]) include a conditional form of the conditional XOR operation , the Boolean operation NOT, and a constant Boolean operation yielding 0. The time bound for a quantum computations is defined to be the number of such elementary unitary operations.

3.1. INTRODUCTION

69

3.1.3. Surveys of QC The following are reviews and surveys have been made of QC: Bennett [10], Barenco [11], Benio [12], Brassard [13, 14], Haroche, Raimond [15], Brassard [16], Preskill [17], Scarani [18], Steane [19], and Vedral, Plenio [20]. Also, Taubes [21] and Gershenfeld, Chuang [22] give popular press descriptions of QC. The following are texts on quantum computing.      

Overviews: [23–26] Quantum information processing: [27–34] Quantum cryptography: [35–37] Quantum coding theory: [38, 39] Quantum algorithms: [40] Experimental implementation of quantum computation: [41–45]

3.1.4. Initial Work in QC Feynman [46, 47] and Benioff [48] were the first to suggest the use of quantum mechanical principles for doing computation. Deutsch and Jozsa [49] give the first example of a quantum algorithm that gave a rapid solution of an example problem, where the problem (for a given a black box function) is not quickly solvable by any deterministic conventional computing machine. But their problem could be quickly solved using randomization. Bernstein and Vazirani [50] then provided the first example of a fast quantum algorithm for a problem that could not be quickly solved by conventional computing machines even using randomization. (See also Costantini, Smeraldi [51] for a generalization of Deutsch’s example and see Collins et al. [52] for a simplified Deutsch–Jozsa algorithm, and Jozsa [53–55] for further work in quantum computation and complexity.)

3.1.5. Organization of this Chapter In Section 3.1 we introduced QC. In Section 3.2 we introduce formal quantum computing models and in Section 3.3 we discuss quantum complexity classes. Next we overview key topics concerning quantum information processing: Section 3.4 discusses bounds for quantum communication; Section 3.5 discusses methods for quantum errorless compression; Section 3.6 discusses methods for quantum error coding; and Section 3.7 describes methods for quantum cryptography. In Section 3.8 we discuss further algorithmic applications of QC. In Section 3.9 we enumerate various technologies for doing QC. In Section 3.10 we review of the resource bounds of quantum computing as compared with the resources required by classical methods for computation. In Section 3.11 we conclude the chapter. In Appendix 3.12 we discuss the challenge of providing volume bounds for observation apparatus when doing QC.

70

CHAPTER 3: QUANTUM COMPUTING

3.2. QUANTUM COMPUTING MODELS  Quantum TMs and other Automata. Deutsch [56] gave the first formal description of a quantum computer, known as a quantum TM. The tape contents of the TM are qubits. Quantum configurations of the QTM are superpositions of (classical) TM configurations. A transition of the QTM is a unitary mapping on quantum configurations of the QTM. Thus, a computation of the QTM is a unitary mapping from the initial quantum configuration to the final quantum configuration. Various papers generalize machines and automata to the quantum case. Moore, Crutchfield [57] propose quantum finite-state and push-down automata, and regular and context-free grammars; they generalize several formal language and automata theorems, e.g., pumping lemmas, closure properties, rational and algebraic generating functions, and Greibach normal form. Kondacs and Watrous [58] partially characterize the power of quantum finite state automata. Dunlavey [59] gives a space efficient simulation of a deterministic finite state machine (FSM) on a quantum computer (using Grover’s search algorithm discussed below). Watrous [60] investigates quantum cellular automata and Du¨rr et al. [61, 62] give decision procedures for unitary linear (one dimensional) quantum cellular automata.  Quantum Gates. A set of Boolean gates are universal if any Boolean operation on arbitrarily many bits can be expressed as compositions of these gates. Toffoli [5] defined an extended XOR 3-bit gate (which is an XOR gate condition on one of the inputs and is known as the Toffoli gate) and showed that this gate, in combination with certain 1-bit gates, is universal. A set of quantum qubit gates are universal for Boolean computations for QC if any unitary operation on arbitrarily many qubits can be expressed as compositions of these gates. Deutsch defined the extended quantum XOR 3-qubit gate (known as the Deutsch–Toffoli gate) and proved this gate, in combination with certain one qubit gates, is universal. Barenco [63], Sleator et al. [64], Barenco et al. [65], and DiVincenzo [66] proved the 2-qubit XOR gates with certain 1-qubit gates can implement the Deutsch–Toffoli gate, so are universal for QC (also see Smolin and DiVincenzo [67], DiVincenzo et al. [68], Poyatos et al. [69], and Mozyrsky et al. [70, 71]). Lloyd [72] then proved that almost any 2-qubit quantum logic gate (with certain 1-qubit gates) is universal for QC. Monroe et al. [73], DiVincenz et al. [74] gave experimental demonstrations of quantum gates [75]. Defined a quantum computing model known as a quantum gate array, which allows execution of a (possibly cyclic) sequence of quantum gates, each input is a qubit, and each gate computes a unitary transformation.  Quantum Circuits. Yao [76] restricted the concept to (acyclic) quantum circuits, which are a generalization of Boolean logic circuits for quantum gates. It suffices that a quantum circuit use only these universal gates. Yao [76] proved that QTM computations are equivalent to uniform quantum

3.3. COMPLEXITY BOUNDS FOR QC

71

circuit families. Bernstein and Vazirani [50] showed that quantum gates of only logarithmic accuracy suffice for polynomial time quantum circuits. Aharonov et al. [77] discusses a generalization of quantum circuits to allow mixed states, where measurements can be done in the middle of the computation, and showed that such quantum circuits are equivalent in computational power to standard quantum circuits. This generalized an earlier result of Bernstein and Vazirani [50] that showed that all observation operations can be pushed to the end of the computation by repeated use of a quantum XOR gate construction. Aharonov et al. [78] considered an adiabatic model of quantum computation and showed it is equivalent to standard quantum computation.  Computer Simulations of QC. Obenland, Despain [79–81] have given efficient computer simulations of QC, including errors and decoherence, and Cerf, Koonin [82] have given Monte Carlo simulations of QC.

3.3. COMPLEXITY BOUNDS FOR QC 3.3.1. Quantum Complexity Classes and Structural Complexity Berthiaume, Brassard [83] survey open QC structural complexity problems (also see Berthiaume [84]). QC can clearly execute deterministic and randomized computations with no slow down. P (NP, QP, respectively) are the class of problems solved by deterministic (nondeterministic, quantum, respectively) polynomial time computations. Thus QP is the quantum analog of the time efficient class P. It is not known if QP contains NP, that is, if QC can solve NP search problems in polynomial time. It is also not known whether QP is a superset of P, nor if there are any problems QC can solve in polynomial time that are not in P (but this is true given quantum oracles; see Berthiaume, Brassard [85, 86], Machta [87], and van Dam [88, 89] for complexity bounds for computing with quantum oracles).

3.3.2. Bounded Precision QC Let BQP be the class of polynomial time quantum computations that are computed within bounded error. Most of the algorithms we will mention (such as Shor’s) are in the class BQP [50]. Showed that BQP computations can be done using unitary operations with a fixed irrational rotation. Adleman et al. [90] improved this to show that BQP can be computed using only unitary operations with rational rotations, and that BQP is in the class PSPACE of polynomial space computations of (classical) TMs. Practical implementations of QC most likely will need to be done via unitary transitions within some modest amplitude precision. Bernstein, Vazirani [50] proved that BQP computations running in time T can be done with unitary operations specified by only O(log T) bits of precision.

72

CHAPTER 3: QUANTUM COMPUTING

3.3.3. Quantum Parallel Complexity Classes Let NC (QNC, respectively) be the class of (quantum, respectively) circuits with polynomial size and polylogorithmic depth. Thus QNC is the quantum analog of the processor efficient parallel class NC. Moore, Nilsson [91] define QNC and show various problems are in QNC; for example, they show that the quantum Fourier transform can be parallelized to linear depth and polynomial size.

3.4. BOUNDS ON MEASUREMENT, SENSING, AND COMMUNICATION 3.4.1. Lower Bounds on Quantum Communication Cleve et al. [92] prove linear lower bounds for the quantum communication complexity of the inner product function and give a reduction from the quantum information theory problem to the problem of quantum computation of the inner product. Knill, Laflamme [93] characterize the communication complexity of one qubit.

3.4.2. Interaction-Free Quantum Measurement A method for (nearly) interaction-free measurement (IFM) specifies the design of a quantum optical sensing system that is able to determine with arbitrarily high likelihood if an obstructing body has been inserted into the system, without moving or modifying its optical components; moreover, in the case that the obstructing body is present, IFM uses at most an arbitrarily small multiplicative factor of the input intensity to do the sensing. Kwiat et al. [94] (also see [95]) have given a method for IFM which does repeated rounds of measurement to affect small phase changes that eventually determine (via the quantum Zeno effect) whether an obstructing body has been inserted. Kwiat et al. [95] assert their method can be applied to sensing tasks such as photography, but the use of their method for IMF has major practical limitations (i.e., if the obstructing body has not been inserted, then the amount of sensing can be quite large).

3.4.3. Interaction-Free Quantum Sensing Reif [96] defines (nearly) interaction-free sensing (IFS) similarly to IFM, except an upper bound is imposed on both the intensity to do the sensing (which again is an arbitrarily small multiplicative factor of the input intensity) whether or not the obstructing body is present. A quantum optical method for IFS (but not IFM) may be used to do I/O with bandwidth reduced by an arbitrarily small multiplicative factor of the bandwidth required for classical (e.g., conventional optical or electronic) I/O methods. Reif [96] proves there is no method for IFS with

3.5. QUANTUM COMPRESSION

73

unitary transformations and so concludes that I/O bandwidth cannot be significantly reduced by such quantum methods for sensing. (Also see Holevo [97], Fuchs and Caves [98] for proof that quantum methods cannot increase the bandwidth for transmission of classical information.)

3.5. QUANTUM COMPRESSION As noted above, quantum methods cannot increase the bandwidth for transmission of classical information; still, in certain cases, entangled states can be compressed to fewer qubits. This quantum compression could have important applications in practice, where the number of usable qubits is very limited. Schumacher [99] considered compression and decompression of a noiseless source of n quantum bits (qubits), each sampled independently from a given mixed state quantum ensemble. For such a quantum source, the compression factor obtainable by classical information theory is limited by the Shannon entropy, which in general (except in the case where the quantum ensemble has only orthogonal states) is less than the quantum compression factor given by the von Neumann entropy. In particular, Schumacher [99] proved a quantum noiseless coding theorem that states that the source’s von Neumann entropy is the number of qubits per source state which is necessary and sufficient to asymptotically (in the limit of large code-block size) encode the output of the source with arbitrarily high fidelity. The quantum noiseless coding of Schumacher has asymptotically optimal fidelity and size; the resulting compressed number of qubits can be far fewer than in the classical case. SHANNON ENTROPY AND THE LIMITATIONS OF CLASSICAL METHODS FOR NOISELESS COMPRESSION. Suppose n characters from a finite alphabet S are each sampled independently over some probability distribution p. In classical information theory, the Shannon entropy of each character is HS ðpÞ ¼ P  1a2S pðaÞ log pðaÞ. A string of these n bits may be compressed without loss to a bit string of mean length HS (p)n. THE VON NEUMANN ENTROPY AND QUANTUM NOISELESS COMPRESSION. Following Schumacher [99], we assume there is a finite quantum state ensemble (S, p) which is a mixed state consisting of a finite number of qubit states S ¼ fja0 i; . . . ; jajSj1 ig, where each jai i 2 S has probability pi. The compressor is assumed to act on blocks of n qubits (so is a block compressor), and is assumed to know thisP underlying ensemble (S, p). The density matrix of (S, p) is an jSj  jSj jSj1 matrix r ¼ i¼0 pi jai ihai j: The von Neumann entropy (see [99, 100]) corresponding to (S, p) is HVN ðrÞ ¼ Trðr log rÞ: In general, the Shannon entropy HS (p) is greater than or equal to the von Neumann entropy. These entropies are equal only when the states in S are mutually orthogonal.

74

CHAPTER 3: QUANTUM COMPUTING

An Example: Consider a slightly more complex example of a source consisting of a sequence of n photons polarized randomly, with equal probability of phase 0 or phase angle y (e.g., As a very simple example of a source with low von Neumann entropy, consider N photons polarized randomly, equiprobably at 0 or 1.) In this case, the states are S ¼ fja0 i; ja1 ig; where the first state ja0 i ¼ j0i; corresponds to phase 0, and the other state ja1 i ¼ cos yj0i þ sin yj1i corresponds to phase angle y, and the probabilities are both pð0Þ ¼ pð1Þ ¼ 12. The density matrix is r ¼ 12 ja0 iha0 j þ 12 ja1 iha1 j ¼ 12 ðj0ih0j þ ðcos yj0i þ sin yj1iÞðcos yh0j þ sin yh1j ÞÞ ¼ 2 1 2 2 ðð1 þ cos yÞj0ih0j þ  cos y sin yj0ih1j þ cos y sin yj1ih0j þ sin yj1ih1j   Þ which has 2  2 matrix form

2 1 1þcos y 2 cos y sin y

cos y sin y sin2 y

over the basis vector

j0i j1i

: Then we can

find an appropriate b which gives a change of basis with new basis states j00 i ¼ j0i 0 r0 ¼ and  j1 i ¼ cos bj0i þ sin bj1i; providing  a diagonal density matrix  1 2

ð1þcos2 yÞþcos y sin y tan b

0

0

cos y sin yþsin2 y tan b

over the basis vector

j00 i

: Although

j10 i

this source has high Shannon entropy HS(p), it will have low von Neumann entropy HVN (r) in the case of a small magnitude phase angle y However, note that the entropies are the same in the special case where y=p/2, so the states ja0 i ¼ j0i, ja1 i ¼ j1i are orthogonal and the density matrix is simply the diagonal  matrix r ¼ 12 ðj0ih0j þ j1ih1jÞwhich has a diagonal density matrix r ¼   j0i basis vector j1i .

1 2

0

0

1 2

over the

For technical reasons, the unitary compression and decompression mappings need to preserve the number of bits (some of which are ignored). An n-to-n0 quantum compressor is a unitary transformation that maps n-qubit strings to n-qubit strings; the first n0 qubits that are output by the compressor are taken as the compressed version of its input, and the remaining nn0 qubits are discarded. An n0 -to-n decompressor is a unitary transformation that maps n-qubit strings to n-qubit strings; the first n0 qubits input to the decompressor are the compressed version of the uncompressed n qubits, and the remaining nn0 qubits are all 0. The source to the compression scheme is assumed to be a sequence of n qubits sampled independently from (S, p). The observed output is the result of first compressing the input qubits, then decompressing them, and measuring the result (over a basis containing the n inputs). The compression rate is n/n0 and the compression factor is n0 /n. The fidelity of the compression scheme is the probability that the observed output is equal to the original input (that is, the probability that the original qubits are correctly recovered from the compressed qubits). The goal here is a quantum compression with both a high fidelity and a high compression rate. Example (Continued): Consider again the example of a source consisting of a sequence of n photons polarized randomly, with equal probability of phase 0 or phase angle y. If y has small magnitude, then a quantum encoder can compress these photons into an entangled state using just a few photons. Furthermore, a

3.5. QUANTUM COMPRESSION

75

quantum decoder can the recover n photons with the original distribution (with arbitrarily high fidelity for large n) from these compressed photons. SCHUMACHER QUANTUM NOISELESS COMPRESSION. Schumacher [99] gave a quantum noiseless coding theorem which provided asymptotically optimal noiseless compression of a sequence of qubits independently sampled from a finite quantum state ensemble (S, p). The quantum noiseless coding theorem states that for any e,dW0 and sufficiently large n, (i) there is an n-to-n0 quantum compression scheme with fidelity at least 1e and compression to length n0  nðHVN ðrÞ þ dÞ, and (ii) any n-to-n00 quantum compression scheme which gives compression to length n00  nðHVN ðrÞ  dÞ, has fidelity o1e. That is, in the limit of large code-block size, the source’s von Neumann entropy HVN (r) is asymptotically the number of qubits per source state which is necessary and sufficient to encode the output of the source with arbitrarily high fidelity. Given a known finite quantum state ensemble (S, p), Schumacher’s compression scheme assumes a known basis for which the density matrix r is diagonal, with nonincreasing values along the diagonal. The proof of the Schumacher quantum noiseless coding theorem and its refinements by Jozsa and Schumacher [101] and H. Szeto [102] make use of the existence of a typical subspace L (see [101]) within a Hilbert space of n qubits over a source of von Neumann entropy HVN (r). The typical subspace L has dimension  2nHVN ðrÞ and with high probability, a sample of n qubits has an almost unit projection onto L. The Schumacher compressor simply transposes (via a permutation mapping) the subspace L into the Hilbert space of a smaller block of nHVN (r) qubits. These proofs are not completely constructive. Bennett [103] gave a constructive presentation of the Schumacher compression. He observes that the Schumacher compression can be done by a unitary mapping to a basis for which the density matrix r is diagonal (in certain simple cases the density matrix r is already diagonal, e.g., when the input is a set of n identical qubits) followed by certain combinatorial computation which we will call the Schumacher compression function SCHUMACHER. The Schumacher compression function SCHUMACHER simply orders the basis states first by the number of ones (from smallest to largest) that are in the binary expansion of the bits and then refines this order by a lexical sort of the the binary expansion of the bits. That is, all strings with i ones are mapped before all strings with i+1 ones, and those strings with the same number of ones are lexically ordered. Note that for any given value X of the qubits, this transformation SCHUMACHER (X ) is simply a deterministic mapping from an n bit sequence to a n0 bit sequence defined by a combinatorial computation. In particular, given an n bit binary string X, the transformation SCHUMACHER (X) is the number of n bit strings so ordered before X. It is easy to show that SCHUMACHER(X ) is a permutation. Since it is a permutation, it is a bijective function which is uniquely reversible; it is also a unitary transformation. To insure that the overall transformation (for all the states) is a quantum computation, it is essential that the transformation SCHUMACHER (X ) be done using only reversible, quantum-coherent elementary operations. (Bennett et al. [104] gave a

76

CHAPTER 3: QUANTUM COMPUTING

polynomial time quantum algorithm for the related problem of extraction of only classical information from a quantum noiseless coding.) Cleve, DiVincenzo [105] then developed the first polynomial time algorithm for Schumacher noiseless compression of n qubits. In particular, they explicitly computed the bijective function SCHUMACHER (X) and it’s reverse using O(n3) reversible, elementary unitary operations. This was previously the fastest previous algorithm for the Schumacher encoding and decoding functions. Recently, Reif and Chakraborty [108] gave a time efficient algorithm for asymptotically optimal noiseless quantum compression and decompression, costing only Oðnðlog4 nÞlog log nÞ elementary quantum operations. This modified Schumacher encoding requires the evaluation of various combinatorial sums, for which Reif and Chakraborty provide efficient recursive, reversible quantum algorithms. The coding of [106] employed a modified Schumacher encoding that was still asymptotically optimal in fidelity and size. The Schumacher quantum noiseless coding theorem assumes the compressor knows the source. Jozsa et al. [107] recently gave a generalization of the Schumacher compression, that is, the compressor does not know the source, and thus provides the first asymptotically optimal universal algorithm for quantum compression. Also, Braustein et al. [108] have recently given a fast algorithm for an quantum analog of Huffman coding, but do not provide a proof that this coding gives asymptotically optimal noiseless quantum compression (that is, reaches the von Neumann entropy), as provided by Schumacher compression. ([102] assumes the compressor knows the source, but can be extended using the techniques of Jozsa et al. [107] to a asymptotically optimal universal algorithm for quantum compression where the compressor does not know the source.)

3.6. QUANTUM ERROR-CORRECTING CODES 3.6.1. Quantum Coding Theory The qubit can be defined in quantum information theory as the amount of information that can be carried in a quantum system with two basis states, e.g., the internal degree of freedom of a polarized photon. The qubit is thus a fundamental unit of quantum channel capacity. Nielsen [109] (Svozil [110, 111], Holevo [112], Knill, Laflamme [113, 114], and Ohya [115] develop a theory of quantum errorcorrecting codes and quantum information theory, e.g., they give the definition of quantum mutual entropy for an entangled state. Buhrman et al. [116], and Adami, Cerf [117] contrast quantum information theory with classical information theory. Quantum channel capacity has been investigated for noisy channels (DiVincenzo, et al. [118], Holevo [119], Barnum et al. [120]), very noisy channels (Shor, Smolin [121]), and quantum erasure channels (Bennett et al. [122]). Fuchs [123] showed that nonorthogonal quantum states maximize classical information capacity. (Also, Helstrom [124, 125] defines a quantum theory of information detection, and Fuchs [126] defines a related quantum theory of information distinguishability.)

3.7. QUANTUM CRYPTOGRAPHY

77

3.6.2. Decoherence Errors in QC Quantum decoherence is the gradual introduction of errors of amplitude in the quantum superposition of basis states. All known experimental implementations of QC suffer from the gradual decoherence of entangled states. The rate of decoherence per step of QC depends on the specific technology implementing QC. A significant property of Shor’s algorithm is that the precision of the amplitudes in the superpositions need be only a polynomial number of bits. Although the addition of decoherence errors in the amplitudes may at first not have a major effect on the QC, the effect of the errors may accumulate over time and completely destroy the computation. Researchers have dealt with decoherence errors by extending classical error correction techniques to quantum analogs. Generally, there is assumed a decoherence error model where the errors introduced are assumed to be uniform random with bounded magnitude, independently for each qubit.

3.6.3. Quantum Codes Shor [127] and Steane [128] gave the first techniques for reducing quantum decoherence by the addition of extra qubits which are then projected via observation operations to eliminate errors in the superposition. Calderbank, Shor [129], and Steane [130] then proved that QC can be done with bounded decoherence error, assuming the error correction mechanism is without error itself. Bennett et al. [131], and Laflamme [132] gave the first optimal 5-qubit codes, leading to asymptotically optimal (for large code blocks) quantum error correction codes. Shor [133] and Kitaev [134, 135] extended these techniques to do fault tolerant quantum computation on quantum networks, in the presence of bounded decoherence error, even if the error correction mechanism also suffers from error decoherence errors. A final innovation (Aharonov, Ben-O [136], and Knill et al. [137, 138]) was concatenated versions of the above quantum codes that allow for arbitrarily long QC in the presence of arbitrary (i.e., not necessarily random) decoherence error below a fixed constant threshold. Current bounds on this threshold are very small, and it seems likely (although it is not yet known) that they can be increased to above the decoherance error bounds of experimental techniques for QC. Also see the texts [38, 39] on quantum coding theory.

3.7. QUANTUM CRYPTOGRAPHY Here we overview quantum cryptography; also see the following texts: [35–37].

3.7.1. Quantum Keys Bennett et al. [139] and Bennett and Brassard [140] gave the first methods for quantum cryptography using qubits as keys, which were proved to be secure

78

CHAPTER 3: QUANTUM COMPUTING

against certain types of attacks. (However, see the remarks at the end of this subsection.) Surveys of quantum cryptography are given in Bennett, Brassard, Ekert [141], Brassard [142], Bennett, Brassard [143], Brassard [144], and Gisin [145]. Ozhigov [146] gives a protocol for security of information in quantum databases. Hruby [147] discusses further methods for quantum cryptography. Bennett et al. [148], Hughes et al. [149] describes experiments of quantum cryptography, including optical fibers. Bennett et al. [150] gave a protocol for quantum oblivious transfer. Mayers [151] gives quantum oblivious transfer and key distribution protocols and Mayers [152] extends the protocols to noisy channels. Lo, Chau [153] give a quantum key distribution protocol which is unconditionally secure over arbitrarily long distance. Brassard, Crpeau [154] gave quantum bit commitment and quantum coin tossing protocols. Brassard et al. [155] gives a quantum bit commitment scheme provably unbreakable by both parties. Yao [156] proved quantum protocols secure against coherent measurements. Brassard et al. [157] shows how to defeat classical bit commitments with a quantum computer. Chau, Lo [158] gives further methods for qubit commitment. Crpeau et al. [159] gives protocols for quantum oblivious mutual identification. IS QUANTUM CRYPTOGRAPHY ACTUALLY UNBREAKABLE? Unfortunately, some of the methods for quantum cryptography that claim to be unbreakable can in fact be broken by sidestepping assumptions assumed in the proofs of their security. For example, to break the well known quantum cryptography method of Bennett and Brassard [140], Brandt [160] provided a method (experimentally demonstrated by Kim et al. [161]) that exploited entanglement of momentum with the phase of photons, making observations of the momentum portions to infer transmitted phases. It is not clear what other prior results in quantum cryptography could be broken by similar techniques, which places the field of quantum cryptography in some doubt. (Also, Lo, Chau [162] have recently argued that quantum bit commitment and ideal quantum coin tossing are impossible in certain cases that are not covered in the preceeding results.)

3.7.2. Distributed Quantum Networks Future hardware will have to be fast, scalable, and highly parallelizable. A quantum network is a network of QCs executing over a spatially distributed network, where quantum entanglement is distributed among distant nodes in the quantum network. Thus, using distributed entanglement, a quantum network distributes the parts of an entangled state to various processors, which can act on the parts independently. Pellizzari [163] proposes quantum networks using optical fibers; Cirac, Zoller et al. [164] and Bose, Vedral [165] show state transfer distribution can be done among distant nodes. For example, [164] uses a cavity QED device that traps atoms in multiple cavities and exchanges photons between

3.8. OTHER ALGORITHMIC APPLICATIONS OF QC

79

the cavities to establish the distributed entanglement. Various basic difficulties were overcome. They are explained below. How can one do state transfer distribution? Bennett et al. [166, 167] and Brassard [168] developed a technique known as teleportation to transmit arbitrary input states with perfect fidelity. It does this by separating the input state into classical and quantum components. The input can then be reconstructed from these components with perfect fidelity. How can one cope with communication errors and attenuation in a quantum network? Wootters, Zurek [169] proved that a single quantum cannot be cloned. (Note: Buzek, Hillery [170] recently claimed a universal optimal cloning of qubits and quantum registers in a distributed quantum network, but this seems inconsistent with the no-cloning theorem.) That no-cloning theorem implies that once a signal becomes attenuated in an optical fiber communication channel, then it cannot (generally) be amplified. It would at first appear that communication and quantum network links may be limited to distances of the order of the attenuation length in the fiber. However, the range of quantum communication could be extended using quantum repeaters that do quantum error correction, restoring the quantum signal without reading the quantum information. Ekert, Huelga et al. [171] extend the techniques of distributed quantum computation to noisy channels, and showed that for quantum memories and quantum communication, a state can be transmitted over arbitrary distances with bounded error, provided a minimum gate accuracy can be achieved—a constant factor of this error.

3.8. OTHER ALGORITHMIC APPLICATIONS OF QC The early literature in QC provided some examples of QC algorithms for problems constructed for the reasonable purpose of showing that QC can solve some problems more efficiently than conventional sequential computing models. Later, quantum algorithms were developed for variety of useful applications. See the texts on quantum algorithms: [27–34, 40].  Quantum Fourier Transforms. Drutsch, Jozsa [49] gave an O(n) time quantum algorithm for creating a uniform superposition of all possible values of n bits, which is a quantum Fourier transform over the finite field of size 2. Simon [172] used this quantum Fourier transform to give an efficient time quantum algorithm for determining whether a function over a finite domain is invariant under some XOR-mask. This provided one of the first examples of a quantum algorithm which efficiently solves an interesting problem that is costly for classical computation. Brassard, Hoyer [173] gave improvements to Simon’s algorithm. There have been a number of

80

CHAPTER 3: QUANTUM COMPUTING

efficient quantum algorithms for extensions of the quantum Fourier transform: to the approximate quantum Fourier transform (Coppersmith [174]), over various domains (Griffiths, Niu [175], Hoyer [176]), over symmetric groups (Beals [177]), and over certain nonabelian groups (Pueschel, Roetteler, Bet [178]). Vedral, Barenco, Ekert [179] give efficient quantum networks for elementary arithmetic operations using the quantum Fourier transform. Grigoriev [180] used the quantum Fourier transform to test shift-equivalence of polynomials.  Quantum Factoring. The most notable algorithmic result in QC to date is the quantum algorithm of Shor [181, 182] for discrete logarithm and integer factorization in polynomial time (with modest amplitude precision). (Also see a review of the algorithm by Ekert and Jozsa [183].) Shor’s algorithm uses an efficient reduction (due to Miller [184]) from integer factoring to the problem of approximately computing the period (length of a orbit) within an integer ring. Shor approximates the period by repeated use of a quantum Fourier transform over an integer ring and greatest common divisor computations. There has been further considerable work on Shor’s quantum factoring algorithm: Zalka [185] improved the time complexity; Beckman et al. [186] describe its execution on quantum networks with small size and depth; Obenland, Despain [187], Plenio, Knight [188] consider the feasibility of executing Shor’s quantum factoring algorithm on various quantum computer architectures. (The latter provide somewhat pessimistic lower bounds for the factorization time of large numbers on a quantum computer in the presence of decoherance errors.) [189] describes a 7-qubit demonstration of Shor’s factorization algorithm using nuclear magnetic resonance. Kitaev [190] gave an independent derivation of Shor’s factoring result using a reduction to find an abelian stabilizer.  Quantum Search. Another significant efficient QC algorithmic result is the algorithm pffiffiffiffi of Grover [191], which searches within a database of size N in time N . (An interesting property of Grover’s algorithm for search is its similarity to the quantum Zeno affect technique for p quantum measurement ffiffiffiffi [94, 95]. In particular, the algorithm also uses Oð N Þ stages of unitary operations, each quite similar to a stage of the quantum Zeno sensing method.) Grover refined his result to require only a single query [192] and to use almost any unitary transformation [193]; Zalka [194] showed Grover’s algorithm cannot be further asymptotically sped up and so is optimal for database search; and Pati [195] gave further improvements to the bounds. Biron et al. [196] extended Grover’s algorithm to arbitrary initial amplitude distribution. Cockshott [197] gave fast quantum algorithms for executing more general operations on relational databases, and Benjamin, Johnson [198] discuss the use of Grover’s algorithm and related quantum algorithms for other data processing problems. Farhi et al. [199] showed that Grover’s algorithm could not be extend to quickly determine

3.8. OTHER ALGORITHMIC APPLICATIONS OF QC

81

parity of N bits; in particular, they showed that any quantum algorithm for parity takes at least N/2 steps. Meyer [200] and Terhal, Smolin [201] propose quantum search algorithms that do not to require entanglement. Brassard et al. [202, 203] combine the algorithmic techniques of Grover and Shor to give a fast quantum algorithm for approximately counting (i.e., finding the number of matches in a database). While Grover’s algorithm is clearly an improvement over linear sequential search in a database, it appears less impressive in the case of an explicitly defined database which needs to be stored in volume N. Parallel computation can do search in a database of size N in time at most polylogarithmic with N (that is, in time OðlogOð1Þ NÞ) by relatively straightforward use of parallel search Moreover, Grover’s algorithm may not have a clear advantage even in the case of an implicitly defined database, which does not need to be stored, but instead can be constructed on the fly (e.g., that arising from NP search methods). In this case, Grover’s search algorithm can be used to speed up combinatorial search within a pffiffiffiffi domain of size N to a time bound of Oð N Þ. (Hogg [204], and Hogg, Yanik [205] investigate similar quantum search techniques for local and other combinatorial search problems.) In this case Grover’s algorithm appears to require only volume logarithmic in the search space size N. In contrast, parallel computation takes volume linear in the combinatorial search space, but takes just time polylogorithmic in the search space.  Quantum Simulations in Physics. The first application proposed for QC (Feynman [46]) was for simulating quantum physics. In principle, quantum computers provide universal quantum simulation of any quantum mechanical physical system (Lloyd [206], Zalka [207], Boghosian [208])). Proposed QC simulations of quantum mechanical systems include many-body systems (Wiesner [209]); many-body Fermi systems (Abrams, Lloyd [210]); multiparticle (ballistic) evolution (Benioff [211]); quantum latticegas models (Boghosian, Taylor [212]), Meyer [213, 214]); Ising spin glasses (Lidar, Biham [215]); the thermal rate constant (Lidar, Wang [216]; and quantum chaos (Schack [217]).  Quantum Learning. QC may have some interesting applications in learning theory and related problems. Bshouty, Jackson [218] describe learning Boolean formulas in disjunctive normal form (DNF) over the uniform distribution of inputs, using a quantum example oracle; Ventura, Martinez [219] describe a QC learning algorithm for learning DNF using a classical example oracle. Also, Yu, Vlasov [220] describe image recognition using QC, Tucci [221] investigates quantum Bayesian networks, and Ventura, Martinez [222] describe a quantum associative memory,  Quantum Robotics. Benioff [223] considers a distributed QC system with mobile quantum robots that can carry out carrying out measurements and physical experiments on the environment; as an example, Benioff gives an

82

CHAPTER 3: QUANTUM COMPUTING

algorithm for the problem of measuring the distance between a quantum robot and a particle on a 1D space lattice. Hogg [207] proposes the use of distributed QC to allow small-scale sensors and actuators to be controlled in a distributed manner. Further discussion of the applications of QC are given by Landauer [224, 225].  Winding Up Quantum Clocks. The precision of atomic clocks are limited by the spontaneous decay lifetimes of excited atomic states. An interesting application of QC proposed by Huelga [226] (also see Bollinger et al. [227]) is to extend these lifetimes by using quantum error correcting codes to inhibit the spontaneous decay. A similar idea can be used for improving the precision of frequency standards and interferometers.  Quantum Strategies. Meyer [228, 229] has proposed a class of generalized games that allow for quantum strategies and he proves that they provide an improvement over conventional mixed (randomized) strategies for certain games.

3.9. POSSIBLE TECHNOLOGIES FOR DOING QC Here we provide an overview of various experimental implementations of quantum computation; also see the texts [41–45]. As noted previously, any QC can be realized by a universal set of gates consisting of the 2-qubit XOR operation along with some 1-qubit operations. There are two basic approaches known to do QC. (A) Micromolecular QC. Here QC on n qubits is executed using n individual atoms, ions, or photons, and each qubit is generally encoded using the quantized states of each individual atom, ion, or photon. The readout (observation operation) is by measurement of the (eigen) state of each individual atom, ion, or photon. We enumerate a number of proposed micromolecular QC methods as follows:  Quantum Dots. Burkard et al. [230], Loss, Di Vincenzo. [231], and Meekhof et al. [232] describe the use of coupled quantum dots to do QC. ( [78] proposes quantum computation using Cooper pairs.)  Ion Trap QC. Cirac, Zoller [233], Pellizzari et al. [234], and James [235] proposed using a linear array of cold trapped ions (the ions are trapped by electromagnetic fields) whose energy states are used to store the qubits; vibrational modes between consecutive ions also can be used to store states of qubits. The coupling of the qubits is by electrostatic repulsion between the ions. Unitary transitions on superpositions can be executed via an associated array of lasers, each of which pulses a distinct ion; these induce electric dipole moments that determine the transitions. A group at the National Institute of Standards at Boulder, Colorado (Wineland et al.

3.9. POSSIBLE TECHNOLOGIES FOR DOING QC

83

[236, 237] King et al. [238], and Turchette et al. [239]) and a group at Los Alamos (Hughes [240], Hughes et al. [241], and James [242]) have experimentally demonstrated trapped ion QC. These and other researchers have addressed various key issues associated with quantum computation with trapped ions.  Deterministic entanglement of two trapped ions (Turchette et al. [239])  Decoherence bounds (Hughes et al. [240] and Plenio, Knight [244])  Measurement and state preparation, i.e., initialization of the collective motion of the trapped ions (Schneider et al. [245] and King et al. [238]),  Coherent quantum-state manipulation of trapped atomic ions (Wineland et al. [236, 237]),  Heating of the quantum ground state of trapped ions (James [246]) and quantum computation with ‘‘hot’’ trapped ions (Schneider et al. [247]).  Cavity QED. A group at Cal Tech (Turchette [248]) have experimentally demonstrated the use of trapped photons in a cavity QED system to execute 2-qubit XOR gates and thus in principle can do universal QC. The qubits are encoded by the circular polarization of photons interacting. The XOR unitary transitions on superpositions can be executed by resonance between interacting photons in the cavity; the coupling of qubits is via resonance between interacting photons using a Cesium atom also in the cavity, and the coupling is tuned by the spacing of mirrors in the cavity.  Photonics. Various groups (i.e., Chuang et al. [249, 250] and Torma, Stenholm [251]) have experimentally demonstrated QC using optical systems where qubits are encoded by photon phases, and universal quantum gates are implemented by optical components consisting of beamsplitters and phase shifters as well as nonlinear media (also see the linear optics QC proposed by Adami, Cerf [252]).  Heteropolymer. This is a polymer consisting of a linear array of atoms, each of which can be either in a ground or excited energy state. Teich et al. [253] first proposed classical (without quantium superpositions) molecular computations using heteropolymer. Later Lloyd [254] extended the use of heteropolymers to QC using the energy states to store the state of the qubits. The coupling of qubits may be via electric dipole moments that cause energy shifts on adjacent atoms. Unitary transitions on superpositions can be executed via pulses of a laser at particular frequencies; these induce electric dipole moments that determine the transitions.  Nuclear Spin. DiVincenzo [255] and Wei et al. [256, 257] proposed the use of nuclear spin to do QC; see the remarks following the discussion of bulk QC.  Quantum Propagation Delays. Castagnoli [258] proposed a way to do QC using retarded and advanced propagation of particles through various media.

84

CHAPTER 3: QUANTUM COMPUTING

Of these, ion trap QC, cavity QED QC, and photonics have been experimentally demonstrated up to a very small number of qubits (about three bits). The apparent intention of such micromolecular methods for QC is to have an apparatus for storing qubits and executing unitary operations (but not necessarily executing observation operations) which requires only volume linear in the number of qubits. One difficulty (addressed by Kak [259], and Murao et al. [260]) is purification of the initial state: If the state of a QC is initially in an entangled state, and each of the quantum gate transformations introduces phase uncertainty during the QC, then the effect of these perturbations may accumulate to make the output to the QC incorrect. A more basic difficulty for these micromolecular methods is that they all use experimental technology that is not well established; in particular, their approaches each involve containment of atomic size objects (such as individual atoms, ions, or photons) and manipulations of their states. A further difficulty of the micromolecular methods for QC is that apparatus for the observation operation—even if observation is approximated— seems to require volume growing exponential with the number of qubits, as described earlier in this paper. (B) Bulk (or NMR) QC. Nuclear magnetic resonance (NMR) spectroscopy is an imaging technology using the spin of the nuclei of a large collection of atoms. Bulk QC is executed on a macroscopic volume containing a large number of identical molecules in solution, each of which encodes all the qubits. The molecule can be chosen so that it has n distinct quantized spins modes (e.g., each of the n nuclei may have a distinct quantized spins). Each of the n qubits is encoded by one of these spin modes of the molecule. The coupling of qubits is via spin-spin coupling between pairs of distinct nuclei. Unitary operations such as XOR can be executed by radio frequency (RF) pulses at resonance frequencies determined in part by this spin-spin coupling between pairs of nuclei (and also by the chemical structure of the molecule). Bulk QC was independently proposed by Cory, Fahmy, Havel [261] and Gershenfeld, Chuang [22, 262]. Also see Berman et al. [266] and the proposal of Wei et al. [257] for doing NMR QC on doped crystals rather than in solutions, and see Kane [264] for another solid state NMR architecture for quantum computing using silicon.  Bulk QC. was experimentally tested (Jones et al. [265, 266]) and applied to demonstrate the following tasks: quantum search (Jones [267]), approximate quantum counting (Jones, Mosca [268]), Deutsch’s problem (Jones, Mosca [269]), and the Deutsch–Jozsa algorithm on 3 qubits (Linden, Barjat, Freeman [270]).  Advantages of Bulk QC. (i) it can use well established NMR technology and in particular macroscopic devices, The main advantages are (ii) the long time duration until decoherence (due to a low coupling with the environment) and (iii) scaling to more qubits than other proposed technologies for QC.

3.9. POSSIBLE TECHNOLOGIES FOR DOING QC

85

 Disadvantages of Bulk QC. A possible disadvantage of bulk QC is that it appears to allow only a weak measurement of the ensemble average that does not provide a quantum state reduction; that is, the weak measurement does not alter (at least by much) the superposition of states. Another disadvantage of bulk QC is that it may require (for a variety of reasons) macroscopic volumes and volumes which grow exponentially with the number of qubits. Macroscopic volumes may be required for measurement via conventional means. However, known quantum algorithms can still be executed even in this case (e.g., see Gershenfeld, Chuang [22, 262]). So the lack of strong measurement is not a major disadvantage. Also, bulk QC requires the initialization close to a pure state. If bulk QC is done at room temperature, the initialization methods of Cory, Fahmy, Havel [261] (using logical labeling) and Gershenfeld, Chuang [22, 262] (using spatial averaging) yield a pseudo-pure state, where the number of molecules actually in the pure state drops exponentially as 1/cn with the number n of qubits, for some constant c (as noted by Warren [271]). If we approximate the resulting measurement error by a normal distribution, the measurement pffiffiffiffi error is (with high 0 , for likelihood) at least a multiplicative factor of 1  c0 = Np ffiffiffiffi some constant c . n 0 To overcome this measurement error, we need 1=c 4c = N ; and so we require that the volume be at least N4ðcn =c0 Þ2 : Hence, for the output of the bulk QC to be (weakly) measured, the volume (the number N molecules) of bulk QC needs to grow exponentially with the number n of qubits. Recently, there have been various other proposed methods for initialization to a pure state:  Barnes [272] proposes the use of very low temperatures.  Gershenfeld, Chuang [22, 262] suggest the use of gradient fields.  Knill et al. [273] suggest a randomization technique they call temporal averaging.  Recent work of Schulman, Vazirani [274] provides polynomial volume for initialization, with the assumption of an exponential decrease in spin-spin correlations with the distance between the nuclei located within a molecule. (In particular, they assume that the statistical correlation between and two bits on a molecule falls of exponentially with the distance between these bits). Although their methods may provide a solution in practice, known inter-atomic interactions such as the spin-spin correlations are generally considered to be governed by potential force laws which decrease by inverse polynomial powers rather than by an exponential decrease. It has not yet been experimentally established which of these pure state initialization methods scale to a large number of qubits without large volume. (Note: Some physicists feel that it has not been clearly established whether (a) NMR is actually a quantum phenomenon with quantum superposition of basis states, or (b) if NMR just mimics a quantum phenomenon and is actually just

86

CHAPTER 3: QUANTUM COMPUTING

classical parallelism, where the quantum superposition of basis states is encoded using multiple molecules where each molecule is in a distinct basis state. If the latter is true (each molecule is in a distinct basis state) then the volume may grow grow exponentially with the number n of qubits, since each basis state may need to be stored by at least one molecule, and the number of basis states can be 2n. (See Williams, Clearwater [23]) Also, even if each molecule is in some partially mixed quantum state (see Zyczkowski et al. [275]), the volume may still need to grow very large.) In summary, some possible disadvantages of bulk QC that may make it difficult to scale are (i) the inability to do observation (strong measurement with quantum state reduction); (ii) the difficulty to do even a weak measurement without the use of exponential volume; (iii) difficulty (possibly now resolved) to obtain pure initial states without the use of exponential volume; and (iv) the possibility that bulk QC is not a quantum phenomena at all (an unresolved controversy within physics), and so may require use of exponential volume. It is interesting to consider whether NNR can be scaled down from the macroscopic to molecular level. DiVincenzo [255] and Wei et al. [256, 257] propose doing QC using the nuclear spins of atoms or electrons in a single molecule. The main advantages are (i) small volume and (ii) the long time duration until decoherence (an advantage shared with NMR). The key difficulty of this approach is the measurement of the state of each spin, which does not appear to be feasible by the mechanical techniques for detection of magnetic resonance usually used in NMR (which can only do detection of the spin for large ensembles of atoms).

3.10. RESOURCE BOUNDS In this chapter, we have discussed many applications of quantum computation that provide advantages over classical methods of computation. Certain applications of QC (e.g., quantum cryptography) require only a small or constant number of qubits, whereas other applications (e.g., factoring and database search) require a large number of qubits and moreover require an observation operation at least as the final step of the QC. For these advantages to be practical, we need to determine that there are no unfeasible, large resources required by QC. Hence we complete the chapter with a review of the resource bounds of quantum computing compared to the resources required by classical methods for computation. In particular, we will conclude that for the advantages of QC (with a large number of qubits) to be practical for applications requiring a large number of qubits, there needs to be determined (theoretical and practically) bounds on the volume required of observation operations. This seems to us a major missing element in the field of QC. The energy consumption, processing rate, and volume are all important resources to consider in computing devices. Conventional (classical) electronic supercomputers of the size of a work station operate in the range of 109 Joules

3.10. RESOURCE BOUNDS

87

per operation, at up to about 50 giga-ops per second, with memory of about 10 to 100 giga-bytes, and in a volume of about 10 cm2. The volume scales as the number of bits of storage.  Energy Bounds for QC. The conventional linear model of QC allows only unitary state transformations and so by definition is reversible (with the possible exception of the observation operation that does quantum state reduction). Benioff [48] noted that as a consequence of the reversibility of the unitary state transformations of QC, these transformations dissipate no energy. But this does not consider (i) the precision of the amplitudes to be preserved nor (ii) the expected time duration required to drive the operation to completion. Gea-Banacloche [276] and Ozawa [277] independently derived lower bounds on the energy needed to execute within a given precision of the amplitudes and in a given time, an elementary qubit logical operation on a quantum computer. They derived energy lower bounds depending inversely on the time duration for the operation and on the precision of the amplitudes to be preserved. Hence, for polynomial time quantum computations requiring polynomial relative precision, the lower bounds on energy are polynomial, though the constant factors could be a limitation for practical implementations. (Recall that Bernstein, Vazirani [50] proved that BQP computations can be done with unitary operations specified by only logarithmic bits of precision, which corresponds to relative precision e where e41=nOð1Þ :) These energy lower bound results were stated to be independent of the nature of the physical system encoding the qubits and under what the authors claimed normal circumstances in a wide variety of conditions for implementations of quantum computers. Nevertheless, the matter still appears to not be completely resolved, since there may be physical implementations of quantum computers that do not abide by their assumptions. Energy bounds for the quantum qubit logical operations require better understanding and study, particularly with respect to their dependence on the technology used.  Processing Rate of QC. In QC, the rate of execution unitary operations largely depends on the implementation technology (see Section 3.9); certain techniques can execute unitary operations in microseconds (e.g., bulk NMR) and some might execute at microsecond or even picosecond rates (e.g., photonic techniques for NMR). The time duration to do observation can also be very short, but it may be highly dependent on the size of the measuring apparatus and the required precision. (See the following discussion on the observation operation and its volume).  Volume Bounds for QC. We now consider (perhaps more closely than usual in the quantum literature) the volume bounds of QC. Potentially, the modest volume bounds of QC may be the one significant advantage over classical methods for computation. Due to the quantum parallelism (i.e., the superposition of the basis states allows each basis state to exist in parallel),

88

CHAPTER 3: QUANTUM COMPUTING

the volume would appear to be no more that the number of qubits. This may be true, but there are a number of substantial issues that need to be carefully considered. Recall the observation operation both provides a measurement of a qubit with a resulting state reduction. However, the QC literature has not yet carefully considered the volume bounds for the observation operation and as we shall see, it is not yet at all clear what the volume required. In spite of major works on the mathematical and physical foundations of quantum observation, the precise nature of quantum state reduction via a strong quantum measurement remains somewhat of a mystery. Two distinct approaches to the mathematical and physical foundations of observation have been developed: (a) the Copenhagen Formulation, where the observation is simply an assumed basic operation and is considered to be done by a macroscopic measuring device, and (b) the von Neumann Formulation [100, Chapter 4: Macroscopic Measurement], which views the measuring apparatus as well as the quantum system measured as both part of a quantum system. Hence the evolution of the system (and resulting experimental predictions) can be distinct from that predicted by the Copenhagen formulation of observation (which does not take this into account since the measuring apparatus is assumed in their formulation to be very large). See Cerf and Adami [18] for a comparison the Copenhagen and von Neumann formulations and see Hay, Peres [278] for an example of this difference. In summary, the Copenhagen and the von Neumann formulations for observation differ in the assumed context (macroscopic or microscopic measurement apparatus). (Note: Attempts to rectify the difference between the Copenhagen and the von Neumann formulation for observation are given in Hay, Peres [278] and in Zurek [279], but it appears not yet resolved.) The Copenhagen formulation for observation is generally used in the context of quantum physics experiments which use macroscopic measurement apparatus. However, the Copenhagen formulation does not seem to be applicable in the context of a microscopic measurement apparatus, which is so small that it is subject to quantum effects (and thus is within a unitary quantum system). So the Copenhagen formulation for observation may not appropriate for molecular size QC. Although the von Neumann formulation of observation is not relevant to the vast majority of physics experiments (since their experiments generally use large measuring apparatus and small number of degrees of freedom (qubits)), it appears to be appropriate for molecular size QC. It is possible that the volume for quantum observation apparatus grows very quickly with the number of qubits in the von Neumann formulation. In particular, no one has proved a upper bound on the volume for quantum observation (as a function of the number of qubits) assuming the von Neumann formulation. See the Appendix for a further discussion of the problem of determining volume bounds for the observation operation in QC.

3.12. APPENDIX: VOLUME OF OBSERVATION APPARATUS

89

3.11. SUMMARY AND ACKNOWLEDGMENTS We have have provided an overview of the field of quantum computing and surveyed its major algorithmic results and applications as well as physical implementations and their limitations. Some issues such as energy costs as well as volume of observation apparatus for quantum computing are still unresolved, and the later are further addressed in the Appendix. We would like to thank G. Brassard for his clear explanation of numerous results in the field of QC. Also, I would like to thank P. Shor and U. Vazirani for references and for illuminating discussions on quantum computation, particularly on the issue of volume bounds for quantum observation.

3.12. APPENDIX: VOLUME OF OBSERVATION APPARATUS FOR QUANTUM COMPUTING Here we discuss the challenge of providing volume bounds for observation apparatus when doing QC.

3.12.1. A Potentially Fallacious Proof of Small Volume First we note that one might be tempted to give a constructive proof that observation can be done on n qubits in small volume, along the following lines: (i) Basis Step. We begin with a simple, well established experimental method for observation of a single qubit in small quantum system with say n0 qubits for a constant n0. There are many other examples of experimentally verified methods for observation using macroscopic measurement apparatus. (For example, a number of proposed QC architectures (e.g., the Cirac and Zoller [233] 3, and Pellizzari et al. [234] proposed ion trap QC and Kane’s [264] silicon-based NMR QC) give specific descriptions of measuring apparatus that have been experimentally verified for observation of a single qubit within a quantum computing systems with a constant number of qubits. While their measuring apparatus is macroscopic, it still must have just some finite volume. (ii) Inductive Step. However, then we just scale up by using the same experimental apparatus to do observation on each of n qubits (that is, repeating the observation for each of the other qubits). This seems to result in a small volume (perhaps even linear size) apparatus for observation. The potential fallacy of this line of argument is: (a) In the basis step, the experiments of [230, 260] did not provide bounds on the errors (or fidelity) of the measurement as a function of the volume of the measuring apparatus. (b) The inductive step fails to take into account quantum effects involving both the measuring apparatus and the n qubits, as might be predicted by

90

CHAPTER 3: QUANTUM COMPUTING

the von Neumann formulation of quantum measurement in the case where the measuring apparatus is so small that it is subject to quantum effects. That is, there needs to be given, in addition to the experimental description (which is only established for n0 qubits): (iii) A mathematical analysis of the quantum effects (in the context of a closed unitary system) involving the measuring apparatus as the number n of qubits grows large. In particular, bounds on the errors (or fidelity) of the measurement need to be determined as a function of the size of the measuring apparatus. Without this crucial final element, the proof is certainly not complete. Since the observation operation is not reversible, such a proof (in the context of a closed unitary system) seem unlikely to be obtainable.

3.12.2. Possible Experimental Demonstrations of Measurement Another approach would be to test a proposed small-volume apparatus for observation on n qubits for moderate size n (say, in the range of a few hundred, which is required for a nontrivial factoring computation). But the experimental evidence of the volume bounds for observation is unclear, since the QC experiments have not yet been scaled to large or even moderate numbers (say dozens) of qubits, and there are few if any physics experiments for this case. (Shnirman, Schoen [120] describe the use of a single-electron transistor to perform quantum measurements; D’Helon, Milburn [280] describe quantum measurements with quantum computers; and Ozawa [281] describes methods for nondestructive (known as nondemolition) quantum measurements of certain quantum computations.) Hence, at this time that there appears to be neither a mathematical proof nor an experimental demonstration (for even a moderately large number of qubits n) that observation can be done in small volume (in a closed quantum system). Thus there is no evidence (either mathematical or experimental) at this time that QC using measurement scales to large numbers of qubits with small volume. We first consider a number of related questions concerning measurement and quantum state reduction:

3.12.3. Is a Quantum Observation Instantaneous? It appears not. Brune et al. [282] describe the progressive decoherence of the meter in a quantum measurement.

3.12.4. Is an Observation Always Reversible? It appears the answer is no (in a narrow mathematical sense of a state reduction), yes (for small closed state spaces), and no (in a practical sense for entanglements in a large state space).

3.12. APPENDIX: VOLUME OF OBSERVATION APPARATUS

91

 By the strict mathematical definition of the state reduction due to observation, an observation is not reversible in general. Under what conditions is a measurement reversible in the strict mathematical sense? That is, when can we measure classical information from a quantum source (yielding a set of pure states with their probabilities with a reduction of quantum entropy), but later be able to reverse this process to regenerate the entangled source state? Bennett et al. [104] show that this is possible in the very special case where the source states can be partitioned into two or more mutually orthogonal subsets. (Other necessary and sufficient conditions for measurements to be reversible have been proved in Bennett et al. [104]; Chuang, Yamamoto [283] describe how to regenerate a qubit if it has observable error.)  There is experimental evidence that the physical execution of some reductions via measurement are in fact reversible (at least in very small closed systems). Mabuchi, Zoller [284] have observed inversions of quantum jumps in very small quantum-optical systems under continuous observation, and Ueda [285] compares the notions of mathematical and physical reversibility.  On the other hand, in the case of entanglements in a large state space, even if a measurement is in principle reversible in a closed system due the reversible nature of the diffusion process, the likelihood of such a reverse to the original state, within a moderate (say polynomial in n) time duration, appears to drop exponentially with the number of qubits n. Gottfield [286] and Diosi, Lukacs [287] explain quantum state vector reduction via strong measurement as a physical process, e.g, state diffusion into the atoms of the measurement apparatus. (Also see Pearle [288, 289].) This diffusion due to reduction may be modeled by a system similar to a rapidly mixing Markov system in probability theory, which seems to provide a very low (dropping exponentially with n) likelihood for reversibility within a polynomial time duration. (Others have modeled measurement by a nonlinear interactions with the environment, which are irreversible.)

3.12.5. Should You Avoid Observation Operations? An alternative approach is to completely avoid observation operations on the basis that the observation operation is not actually essential to many quantum computations. (This seems somewhat surprising, given the extensive use of the observation operation in the QC literature for both algorithms and quantum error correction.) Bernstein, Vazirani [50] (by showing that any given observation operation can be delayed to future steps by use of the using XOR operation) proved that all observation operations can be delayed to the final step of a quantum computation. For a small eW0, let some particular qubit (of the linear superposition of basis states) be e-near classic if had the qubit been observed, the measured value would be a fixed value (either be 0 or 1) with e probability. Suppose the output of a QC consists of the observation of a subset S of the qubits; the resulting reduced superposition will be termed the output superposition.

92

CHAPTER 3: QUANTUM COMPUTING

Bernstein and Vazirani [50] and Brassard et al. [173, 202] observe that any QC can be repeated to insure the output qubits are e-near classic in the final output superposition after the repetitions. Note that if a QC with bounded amplitude precision is reduced by an observation, the output qubits yield the correct value with high likelihood. Hence we may consider simply not doing the observation reduction to a basis state in the final step; in place of this (reduced) output superposition we simply output the nonreduced quantum state superposition of the QC that exists just prior to the final observation step. This alternative approach can eliminate entirely the observation operation from many quantum computations, and so provides small volume, but has the drawback of providing a nonclassic output consisting of a nonreduced quantum state superposition. The potential difficulty with this approach is as follows: If this (nonreduced quantum state superposition) output is then processed by a classical computing machine, it may propagate unwanted quantum effects to the classical computing machine.

3.12.6. What about Approximate Observation Operations? An approach to this difficulty is to only do the observation operation approximately within accuracy e; this may suffice for many QC applications. However, even if the observation operation is done e-approximately by unitary operations, it appears to require a number of additional qubits n0 growing exponentially with the n, the original number of qubits of the QC. In fact, we know of no upper bound on n0 better than 2n log (1/e).

3.12.7. Why May the Volume Required by Observation Apparatus Not Be Small? We next consider whether it is reasonable to expect that a mathematical proof (or such experimental demonstrations) of small volume quantum observation will ever be done. We provide an informal argument that even an e-approximate observation cannot be done in polynomial time using small volume, where e is the inverse of a polynomial. (It should be emphasized that the following is not a formal proof in any sense.) Since for n qubits, the size of the basis state space grows as 2n in the general case, it seems reasonable to assume (e.g., where the physics of the strong measurement is modeled by a diffusion process [286–288] that is rapidly mixing) that the likelihood of reversibility within polynomial time bounds drops exponentially with the number n of qubits. Thus, in the context of polynomial time computations, the e-approximate observation is assumed irreversible with high likelihood. The argument will hinge on the assumption, made by conventional formulations of quantum computation, that quantum computation (including both unitary qubit operations as well as the nonunitary observation (or projection) operation) can be exectuted for any given number n qubits, which makes an implicit assumption that both unitary and nonunitary operations can be executed at any scale.

REFERENCES

93

Let us also assume that the number of qubits n is small (at most a few hundreds). For sake of contradiction, let us for the moment suppose that (i) quantum computing scales to at least moderate size (say a few tens of thousands of qubits), and (ii) an e-approximate observation operation can be done on one of n qubits by a microscopic measuring device of size n0 =nc, for a constant c, and operating within time polynomial in n. Since n is small, the measuring device is surely of sufficiently small size so that its physics is consistent with established quantum physics. (Observe that if quantum computing is to scale to at least moderate size n0 , then surely quantum effects need to hold for molecules of size n0 ). This implies that we need to view the apparatus for the observation as executing polynomial time unitary quantum computation, which is reversible, so the reverse of the observation also executes in quantum polynomial time. Hence we have an apparent contradiction, since we have assumed the e-approximate observation is not reversible in polynomial time. (Note: This argument does not require that the governing physical laws shift at some definite size from a quantum-mechanical paradigm to a classical paradigm; instead, the argument requires that if the quantum-mechanical paradigm is valid at size n then it also is valid at some what larger size n0 =nc.) Due to informal nature of this argument, it only provides partial evidence that (with the above assumption), QC with the observation operation does not scale to a large number of qubits within small volumes, and in particular that a polynomial time e-approximate observation operation requires very large volume and cannot be done at the micromolecular scale for moderate large n. We feel our above argument is far too informal to provide a resolution of the issue. It remains a major open problem in QC to provide a formal proof that either (i) there is large volume required for observation or (ii) there is not.

3.13. CONCLUSIONS This chapter provided an overview of the field of QC, including abstract models for QC. We have surveyed major potential applications of QC, for example, cryptography, speeding up combinatorial search and integer factorization were surveyed. Major technologies for experimental implementation of QC have been enumerated. Even after two decades of major research efforts, all prior QC demonstrations to date have been limited to very small number of qubits. Various key technical challenges and fundamental resource bounds for scaling QC to larger problem sizes have been reviewed. It remains to be demonstrated if these challenges can be overcome to allow QC to scale to problem instances of practical importance to combinatorial search and integer factorization.

REFERENCES Note: QCQC 98 is an acronym for Proceedings of 1st NASA Workshop on Quantum Computation and Quantum Communication (QCQC 98), Springer-Verlag, Feb 1998.

94

CHAPTER 3: QUANTUM COMPUTING

1. R. Landauer. Irreversability and heat generation in the computing process. IBM Journal of Research Development, 5(183): 1961. 2. C. H. Bennett. Logical reversibility of computations. IBM Journal of Research and Development, 17: pp 525–532, 1973. 3. C. H. Bennett and R. Landauer. Physical limits of computation. Scientific American, p 48, July 1985. 4. R. Landauer. The physical nature of information. Physics Letters A, 217: p 188, 1996. 5. T. Toffoli. In: J. W. de Bakker, J. van Leeuwen editors. Automata, Languages and Programming. New York: Springer-Verlag, p 632, 1980. 6. M. Li and P. Vitanyi. Reversibility and adiabatic computation: trading time and space for energy. Proceedings of the Royal Society of London, Series A, 452: pp 769–789, 1996. (Online preprint quant-ph/9703022) 7. C. H. Bennett. Time/space trade-offs for reversible computation. Siam Journal on Computing, 18 p 766, 1989. 8. A. Barenco, C. H. Bennett, R. Cleve, and D. P. DiVincenzo. Physical Review A, 51: p 1015, 1995. 9. C. H. Bennett and D. P. DiVincenzo. Progress towards quantum computation. Nature, Oct 1995. 10. C. H. Bennett and D. P. DiVincenzo. Quantum computing: towards an engineering era? Nature, 377: 1995. 11. A. Barenco. Quantum physics and computers. Contemporary Physics, 37: p 375, 1996. (Online preprint quant-ph/9612014) 12. P. Benioff. Quantum ballistic evolution in quantum mechanics: application to quantum computers. To be published in Physical Review A, 1996. (Online preprint quant-ph/9605022) 13. G. Brassard. New Trends in Quantum Computing. 13th Symposium on Theoretical Aspects of Computer Science, Grenoble. Lecture Notes in Computer Science: New York: Springer-Verlag, Feb 1996. (Online preprint quant-ph/9602014) 14. G. Brassard. New horizons in quantum information processing. Proceedings of the 25th Colloquim on Automata, Languages, and Programming, Aalborg, Denmark, May 1998. 15. S. Haroche and J. M. Raimond. Quantum computing: dream or nightmare? Physics Today, 49(8): p 51, 1996. 16. G. Brassard. Quantum information processing: the good, the bad and the ugly. In: S. Burton, Kaliski Jr., editor. Advances in Cryptology: CRYPTO ‘97, Volume 1294 of Lecture Notes in Computer Science: pp 337–341, Aug 1997. 17. J. Preskill. Quantum computing: pro and con. Submitted to Proceedings of the Royal Society London, A, 1997. (Online preprint quant-ph/9705032) 18. V. Scarani. Quantum computing. Accepted for publication in American Journal of Physics, 1998). (Online preprint quant-ph/9804044) 19. A. Steane. Quantum computing. Reports on Progress in Physics, 1998. (Online preprint quant-ph/9708022) 20. V. Vedral and M. B. Plenio. Basics of quantum computation. Invited basic review article for Progress in Quantum Electronics, 1998. (Online preprint quant-ph/9802065) 21. Taubes. All together for quantum computing. Science, 273: 1996.

REFERENCES

95

22. N. Gershenfeld and I. L. Chuang. Quantum computing with molecules. Scientific American, 278(6): pp 66–71 June 1998. 23. C. P. Williams and S. H. Clearwater. Explorations in Quantum Computing. New York: Springer-Verlag, 1997. 24. R. Brylinski and G. Chen. Mathematics of Quantum Computation (Computational Mathematics Series). Boca Raton, FL: CRC Press, Feb 2002. 25. J. Gruska. Quantum Computing. (Advanced Topics in Computer Science Series). New York: Osborne/McGraw-Hill, Mar 1999. 26. M. Hirvensalo. Quantum Computing (Natural Computing Series). Berlin: SpringerVerlag GmbH and Co., Dec 2003. 27. T. Beth and G. Leuchs. Quantum Information Processing, 2nd ed. Weinheim: WileyVCH, Mar 2005. 28. M. Brooks. Quantum Computing and Communications. London: Springer-Verlag., May 1999. 29. S. Imre and F. Balazs. Quantum Computing for Communications. Chichester, UK: Wiley, Jan 2005. 30. G. Leuchs. Quantum Information Technology. Weinheim: Wiley-VCH, Mar 2003. 31. C. Macchiavello, G. M. Palma, and A. Zeilinger. Quantum Computation and Quantum Information Theory. Singapore: World Scientific Publishing, Jan 2001. 32. M. L. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information (Cambridge Series on Information and the Natural Sciences). Cambridge, UK: Cambridge University Press, Oct 2000. 33. W. P. Schleich and H. Walther. Elements of Quantum Information. Weinheim: WileyVCH, Jan 2007. 34. V. Vedral. Introduction to Quantum Information Science (Oxford Graduate Texts Series). Oxford, UK: Oxford University Press, Sep 2006. 35. G. Van Assche. Quantum C