Non-Standard Computing
Purpose of Course showclose
Learning Outcomes showclose
- Describe abstracted finite-memory program, a finite state automaton, and regular language.
- List and explain the characteristics of universal Turing transducers.
- Describe the computational idea behind the DNA-based computer.
- Explain the differences between bio-electronic, biochemical, and biomechanical computers.
- Describe the functional principles of genetic algorithms and list their limitations.
- Define the cellular automaton and the cellular neural network, and show examples of how they compute.
- Describe how logic gates may be constructed for quantum bits.
- Describe a simple model for a quantum computer based on a classical computer.
- Describe an algorithm which makes use of quantum parallelism.
Course Requirements showclose
√ Have access to a computer.
√ Have continuous broadband Internet access.
√ Have the ability/permission to install plug-ins or software (e.g. Adobe Reader or Flash).
√ Have the ability to download and save files and documents to a computer.
√ Have the ability to open Microsoft files and documents (.doc, .ppt, .xls, etc.).
√ Be competent in the English language.
√ Have read the Saylor Student Handbook.
√ Have completed the Cell Biology (BIO301) course. It is also recommended that you have completed the courses in “The Core Program” of the Computer Science discipline (CS101 through CS405).Unit Outline show close
Expand All Resources Collapse All Resources
-
Unit 1: Review: Theory of Computation
In the first part of this unit, the student will learn about representing information, the concept of languages, the notion of programs, and the concept of non-determinism. Then, we will get an overview of the mathematical systems of finite-state transducers and grammatical characterizations of the languages that finite-memory programs accept. The last part of the unit covers the mathematical systems of Turing transducers. Also, we will discuss the relationship between determinism and non-determinism in Turing transducers.
Unit 1 Time Advisory show close
Unit 1 Learning Outcomes show close
-
1.1 General Concepts
- Reading: Ohio State University: Eitan Gurari’s An Introduction to the Theory of Computation: “Chapter 1: General Concepts”
Link: Ohio State University: Eitan Gurari’s An Introduction to the Theory of Computation: “Chapter 1: General Concepts” (HTML)
Instructions: Read the introductory webpage titled “General Concepts." Then, click on the hyperlinks for each section 1.1-1.5, and read each webpage in its entirety. From this reading, you will learn about strings and the role that strings have in representing information. This reading relates the concept of languages to the notion of strings and introduces grammars for characterizing languages. Also, this text deals with the notion of programs and the concept of non-determinism in programs. This reading covers subunits 1.1.1 through 1.1.3 of this course.
Terms of Use: Please respect the copyright and terms of use displayed here.See a broken link? Please let us know!
- Reading: Ohio State University: Eitan Gurari’s An Introduction to the Theory of Computation: “Chapter 1: General Concepts”
- 1.1.1 Alphabets, Strings, and Representations
- 1.1.2 Formal Languages and Grammars
- 1.1.3 Programs
-
1.2 Finite-Memory Programs
- Reading: Ohio State University: Eitan Gurari’s An Introduction to the Theory of Computation: “Chapter 2: Finite-Memory Programs”
Link: Ohio State University: Eitan Gurari’s An Introduction to the Theory of Computation: “Chapter 2: Finite-Memory Programs” (HTML)
Instructions: Please read the “Finite-Memory Programs” webpage, and then click on each hyperlink for sections 2.1-2.6. Read each section in its entirety to learn about the mathematical systems of finite-state transducers. This reading also provides grammatical characterizations for the languages that finite-memory programs accept. This reading covers subunits 1.2.1 through 1.2.3 of this course.
Terms of Use: Please respect the copyright and terms of use displayed here.See a broken link? Please let us know!
- Reading: Ohio State University: Eitan Gurari’s An Introduction to the Theory of Computation: “Chapter 2: Finite-Memory Programs”
- 1.2.1 Motivation
- 1.2.2 Finite-State Transducers
- 1.2.3 Finite-State Automata and Regular Languages
-
1.3 Recursive Finite-Domain Programs
- Reading: Ohio State University: Eitan Gurari’s An Introduction to the Theory of Computation: “Chapter 3: Recursive Finite-Domain Programs”
Link: Ohio State University: Eitan Gurari’s An Introduction to the Theory of Computation: “Chapter 3: Recursive Finite-Domain Programs” (HTML)
Instructions: Please read the introductory webpage titled “Recursive Finite-Domain Programs.” Then, click on each hyperlink for sections 3.1-3.6, and read each section in its entirety to learn about the notion of recursion in programs and recursive finite-domain programs, which are characterized by finite-state transducers. A grammatical characterization for recursive finite-domain programs is provided in section 3.3. This reading covers subunits 1.3.1 through 1.3.3 of this course.
Terms of Use: Please respect the copyright and terms of use displayed here.See a broken link? Please let us know!
- Reading: Ohio State University: Eitan Gurari’s An Introduction to the Theory of Computation: “Chapter 3: Recursive Finite-Domain Programs”
- 1.3.1 Recursion
- 1.3.2 Pushdown Transducers
- 1.3.3 Context-Free Languages
-
1.4 General Programs
- Reading: Ohio State University: Eitan Gurari’s An Introduction to the Theory of Computation: “Chapter 4: General Programs”
Link: Ohio State University: Eitan Gurari’s An Introduction to the Theory of Computation: “Chapter 4: General Programs” (HTML)
Instructions: Please read the introductory page titled “General Programs.” Then, click on the hyperlinks for sections 4.1-4.7, and read each webpage in its entirety. Section 4.1 is about the mathematical systems of Turing transducers as a generalization to pushdown transducers. In section 4.2, you will learn about the relationship between the general class of programs and Turing transducers. Section 4.3 considers the relationship between determinism and non-determinism in Turing transducers. Section 4.4 shows the existence of a Turing transducer, called a universal Turing transducer, which can be programmed to compute any computable function. This reading covers the topics outlined in subunits 1.4.1 through 1.4.4 of this course.
Terms of Use: Please respect the copyright and terms of use displayed here.See a broken link? Please let us know!
- Reading: Ohio State University: Eitan Gurari’s An Introduction to the Theory of Computation: “Chapter 4: General Programs”
- 1.4.1 Turing Transducers
- 1.4.2 Programs and Turing Transducers
- 1.4.3 Non-Determinism versus Determinism
-
1.4.4 Universal Turing Transducers
- Assessment: The Saylor Foundation's "CS411: Unit 1 Quiz"
Link: The Saylor Foundation's "CS411: Unit 1 Quiz"
Instructions: Please take this Unit 1 quiz. When you are done, check your work against the Saylor Foundation's "CS411: Unit 1 Quiz Answer Key" (PDF). This quiz should require less than one hour to complete.The Saylor Foundation does not yet have materials for this portion of the course. If you are interested in contributing your content to fill this gap or aware of a resource that could be used here, please submit it here.
- Assessment: The Saylor Foundation's "CS411: Unit 1 Quiz"
-
Unit 2: Molecular Computation
The first part of this unit covers the structure and manipulation of DNA for computational purposes. Then, we discuss the development of biocomputers and biologically derived materials to perform computational functions. In order to understand biocomputers better, we list some elementary concepts and building blocks of supramolecular chemistry. The last part of the unit shows a video about the workings of a DNA computer.
Unit 2 Time Advisory show close
Unit 2 Learning Outcomes show close
-
2.1 DNA-Based Computation
- Reading: G. Sweety Peter’s “DNA-Based Computation”
Link: G. Sweety Peter‘s “DNA-Based Computation” (HTML)
Instructions: Read the webpage to learn about the structure and manipulation of DNA, about the operations of DNA sequences, and about DNA computing models. Make sure you understand the shortcomings of DNA computation. This reading covers subunits 2.1.1 through 2.1.5.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.See a broken link? Please let us know!
- Reading: G. Sweety Peter’s “DNA-Based Computation”
- 2.1.1 The Structure and Manipulation of DNA
- 2.1.2 Operations of DNA Sequences
- 2.1.3 The Case for DNA Computing
- 2.1.4 Models and Formats of DNA Computation
- 2.1.5 Pitfalls of DNA Computing
-
2.2 Biocomputers
- Reading: Wikipedia: “Biocomputers”
Link: Wikipedia: “Biocomputers” (PDF)
Instructions: Read this webpage to learn about the development of biocomputers and biologically derived materials to perform computational functions. Pay particular attention to the differences among bio-electronic, biochemical, and biomechanical computers. This reading covers subunits 2.2.1 through 2.2.7.
Terms of Use: The article above is released under a Creative Commons Attribution-Share-Alike License 3.0 (HTML). You can find the original Wikipedia version of this article here (HTML).See a broken link? Please let us know!
- Reading: Wikipedia: “Biocomputers”
- 2.2.1 Scientific Background
- 2.2.2 Biochemical Computers
- 2.2.3 Biomechanical Computers
- 2.2.4 Bioelectronic Computers
- 2.2.5 Engineering Biocomputers
- 2.2.6 Economical Benefit of Biocomputers
-
2.2.7 Notable Advancements in Biocomputer Technology
- Reading: Biocomputers
The Saylor Foundation does not yet have materials for this portion of the course. If you are interested in contributing your content to fill this gap or aware of a resource that could be used here, please submit it here.
- Reading: Biocomputers
-
2.3 Supramolecular Systems
- Reading: Wikipedia: “Supramolecular Chemistry”
Link: Wikipedia: “Supramolecular Chemistry” (PDF)
Instructions: Read this webpage to learn about the concepts and building blocks of supramolecular chemistry. Please pay particular attention to section five “Applications,” which provides examples of how supramolecular chemistry is used. This reading covers subunits 2.3.1 through 2.3.3.
Terms of Use: The article above is released under a Creative Commons Attribution-Share-Alike License 3.0 (HTML). You can find the original Wikipedia version of this article here (HTML).See a broken link? Please let us know!
- Reading: Wikipedia: “Supramolecular Chemistry”
- 2.3.1 Concepts in Supramolecular Chemistry
- 2.3.2 Building Blocks of Supramolecular Chemistry
- 2.3.3 Applications
-
2.4 Bio-molecular Computing of Finite-State Automata
- Assessment: The Saylor Foundation's "CS411: Unit 2 Quiz"
Link: The Saylor Foundation's "CS411: Unit 2 Quiz"
Instructions: Please take this Unit 2 quiz. When you are done, check your work against the Saylor Foundation's "CS411: Unit 2 Quiz Answer Key" (PDF). This quiz should require less than one hour to complete.The Saylor Foundation does not yet have materials for this portion of the course. If you are interested in contributing your content to fill this gap or aware of a resource that could be used here, please submit it here.
- Web Media: Videolectures.net: Yasubumi Sakakibara’s “Bio-Molecular Computing of Finite-State Automata”
Link: Videolectures.net: Yasubumi Sakakibara’s "Bio-Molecular Computing of Finite-State Automata" (YouTube)
Instructions: Watch this video to learn what a DNA computer is and to see some examples of how a DNA computer works. Please take notes as you watch the video and review portions of the video as necessary to make sure you understand each concept. This should take approximately 3 hours of study time.
Terms of Use: This video is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License. It is attributed to videolectures.net and the original version can be found here.See a broken link? Please let us know!
- Assessment: The Saylor Foundation's "CS411: Unit 2 Quiz"
-
Unit 3: Genetic Algorithms
In this unit, we start with an overview of genetic algorithms. Then, we show a practical example of genetic algorithms that demonstrate the application of event classification and feature selection. Also, we show a video about computational systems that have been used for natural selection on complex artificial problems.
Unit 3 Time Advisory show close
Unit 3 Learning Outcomes show close
-
3.1 Introduction to Genetic Algorithms
- Reading: www.rennard.org: Jean-Philippe Rennard’s “Introduction to Genetic Algorithms”
Link: www.rennard.org: Jean-Philippe Rennard’s “Introduction to Genetic Algorithms” (HTML)
Instructions: Read this webpage for general overview of genetic algorithms. This reading covers subunits 3.1.1 through 3.1.3.
Terms of Use: The linked material above has been reposted by the kind permission of Jean-Philippe Rennard, and can be viewed in its original from here. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.See a broken link? Please let us know!
- Reading: www.rennard.org: Jean-Philippe Rennard’s “Introduction to Genetic Algorithms”
- 3.1.1 Evolution and Optimization
- 3.1.2 Evolution and Genetic Algorithms
- 3.1.3 Functioning of a Genetic Algorithm
- 3.1.4 Adaptation and Selection: the Scaling Problem
-
3.2 Genetic Algorithm Classifiers
- Reading: McGill University: Gabriel Kevorkian and Marko Milek’s “Genetic Algorithm Classifiers”Link: McGill University: Gabriel Kevorkian and Marko Milek’s “Genetic Algorithm Classifiers” (HTML and Java)
Instructions: Please read this entire study of genetic algorithms (7 pages). Click on the “Next” button at the bottom of the text to move on to each subsequent webpage. Also, go through the example by clicking on the 'Algorithm' and 'Applet' links at the top of the webpage. The example demonstrates specific application of event classification and feature selection. This reading covers subunits 3.1.1 through 3.1.3 of this course.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.See a broken link? Please let us know!
- Reading: McGill University: Gabriel Kevorkian and Marko Milek’s “Genetic Algorithm Classifiers”
- 3.2.1 Introduction
- 3.2.2 Classifiers
- 3.2.3 Algorithm
-
3.3 Evolutionary Algorithms
- Web Media: Videolectures.net: Adam Prügel-Bennett’s "Evolutionary Algorithms”
Link: Videolectures.net: Adam Prügel-Bennett’s "Evolutionary Algorithms" (YouTube)
Instructions: Watch this video on computational systems that have been used for natural selection on complex artificial problems. There have been some successes, but the complexity of artificially evolved systems remains short of the complexity one easily finds in biology. You may benefit from viewing certain sections of this video more than once; repeat watching any sections of the video that are hard to follow. It may also help to take notes as you view this video. This should take approximately 2 hours of study time.
Terms of Use: This video is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License. It is attributed to videolectures.net and the original version can be found here.See a broken link? Please let us know!
- Web Media: Videolectures.net: Adam Prügel-Bennett’s "Evolutionary Algorithms”
-
3.4 Another Example: A Genetic Algorithm for Text Classification Rule Induction
- Web Media: Videolectures.net: Adriana Pietramala, Veronic L. Policicchio, Pasquale Rullo, and Inderbir Sidhu’s "A Genetic Algorithm for Text Classification Rule Induction”
Link: Videolectures.net: Adriana Pietramala, Veronic L. Policicchio, Pasquale Rullo, and Inderbir Sidhu’s "A Genetic Algorithm for Text Classification Rule Induction" (YouTube)
Instructions: Watch the video about genetic algorithm for the induction of rule-based text classifiers. You may benefit from viewing certain sections of this video more than once; repeat watching the sections of the video that are hard to follow. This should take approximately 1 hour of study time.
Terms of Use: This video is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License. It is attributed to videolectures.net and the original version can be found here.See a broken link? Please let us know!
- Assessment: The Saylor Foundation's "CS411: Unit 3 Quiz"
Link: The Saylor Foundation's "CS411: Unit 3 Quiz"
Instructions: Please take this Unit 3 quiz. When you are done, check your work against the Saylor Foundation's "CS411: Unit 3 Quiz Answer Key" (PDF). This quiz should require less than one hour to complete.The Saylor Foundation does not yet have materials for this portion of the course. If you are interested in contributing your content to fill this gap or aware of a resource that could be used here, please submit it here.
- Web Media: Videolectures.net: Adriana Pietramala, Veronic L. Policicchio, Pasquale Rullo, and Inderbir Sidhu’s "A Genetic Algorithm for Text Classification Rule Induction”
-
Unit 4: Computation in Cellular Automata: Selected Review
In the first part of this unit, we provide the description of one dimensional cellular automaton and study some rules by which cellular automaton evolved. Then, we will discuss some properties of the regular language sets generated by a finite number of steps of cellular automaton evolution. Also, we show Stephen Wolfram's classes of cellular automaton behavior. Next, we show the standard cellular neural network model and its potential applications. In the end of the unit, we will study complex systems, such as living organisms, the brain, society, the economy, etc. Complex systems are part of computer science and a computer scientist invents algorithmic processes and formulates suitable abstractions to model complex systems to predict its behavior. Complex systems depend on a huge number of details making them nearly irreducible, so that they cannot be described in terms of a small number of variables.
Unit 4 Time Advisory show close
Unit 4 Learning Outcomes show close
- 4.1 Computation Theory of Cellular Automata
-
4.1.1 Introduction
- Reading: Stephenwolfram.com: Stephen Wolfram's Computation Theory of Cellular Automata: “Introduction”
Link: Stephenwolfram.com: Stephen Wolfram's Computation Theory of Cellular Automata: “Introduction” (HTML)
Instructions: Read the description of one dimensional cellular automaton. Please make sure to carefully review the examples and figures given.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.See a broken link? Please let us know!
- Reading: Stephenwolfram.com: Stephen Wolfram's Computation Theory of Cellular Automata: “Introduction”
-
4.1.2 Construction of Finite Time Sets
- Reading: Stephenwolfram.com: Stephen Wolfram's Computation Theory of Cellular Automata: “Construction of Finite Time Sets”
Link: Stephenwolfram.com: Stephen Wolfram's Computation Theory of Cellular Automata: “Construction of Finite Time Sets” (HTML)
Instructions: Read the webpage in its entirety to learn how cellular automaton evolved. Be sure that you understand the examples and figures provided before moving on to other readings.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.See a broken link? Please let us know!
- Reading: Stephenwolfram.com: Stephen Wolfram's Computation Theory of Cellular Automata: “Construction of Finite Time Sets”
-
4.1.3 Properties of Finite Time Sets
- Reading: Stephenwolfram.com: Stephen Wolfram's Computation Theory of Cellular Automata: “Properties of Finite Time Sets”
Link: Stephenwolfram.com: Stephen Wolfram's Computation Theory of Cellular Automata: “Properties of Finite Time Sets” (HTML)
Instructions: Read the webpage in its entirety for a discussion about some properties of regular language sets generated by a finite number of steps of cellular automaton evolution. Please pay careful attention to the examples and figures provided.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.See a broken link? Please let us know!
- Reading: Stephenwolfram.com: Stephen Wolfram's Computation Theory of Cellular Automata: “Properties of Finite Time Sets”
-
4.1.4 Evolution of Finite Time Sets
- Reading: Stephenwolfram.com: Stephen Wolfram's Computation Theory of Cellular Automata: “Evolution of Finite Time Sets”
Link: Stephenwolfram.com: Stephen Wolfram's Computation Theory of Cellular Automata: “Evolution of Finite Time Sets” (HTML)
Instructions: Read the webpage about several types of cellular automaton behavior. Pay attention to classes of cellular automaton behavior defined by dynamical systems theory.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.See a broken link? Please let us know!
- Reading: Stephenwolfram.com: Stephen Wolfram's Computation Theory of Cellular Automata: “Evolution of Finite Time Sets”
-
4.1.5 Some Invariant Sets
- Reading: Stephenwolfram.com: Stephen Wolfram's Computation Theory of Cellular Automata: “Some Invariant Sets”
Link: Stephenwolfram.com: Stephen Wolfram's Computation Theory of Cellular Automata: “Some Invariant Sets” (HTML)
Instructions: Read the webpage in its entirety for information on limiting sets of configurations generated by many steps of cellular automaton evolution.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.See a broken link? Please let us know!
- Reading: Stephenwolfram.com: Stephen Wolfram's Computation Theory of Cellular Automata: “Some Invariant Sets”
-
4.2 Cellular Neural Network
- Reading: Scholarpedia: Tamás Roska and Giovanni E. Pazienza's “Cellular Neural Network”
Link: Scholarpedia: Tamás Roska and Giovanni E. Pazienza's “Cellular Neural Network” (HTML)
Instructions: Read the website to learn about standard CNN model, the potential applications of a Cellular Neural/Nonlinear Network, and biological and technological motivations for computational models. This reading covers subunits 4.2.1 through 4.2.3.
Terms of Use: The linked material above has been reposted by the kind permission of Tamás Roska and Giovanni E. Pazienza, and can be viewed in its original from here. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.See a broken link? Please let us know!
- Reading: Scholarpedia: Tamás Roska and Giovanni E. Pazienza's “Cellular Neural Network”
- 4.2.1 Standard CNN Model
- 4.2.2 CNN - Universal Machine and Cellular Wave Computing
- 4.2.3 Biological and Technological Motivations
-
4.3 Strong Random Correlations in Complex Systems
- Web Media: Videolectures.net: Imre Kondor’s "Strong Random Correlations in Complex Systems”
Link: Videolectures.net: Imre Kondor’s "Strong Random Correlations in Complex Systems" (YouTube)
Instructions: Watch this video about the complex systems (living organisms, the brain, society, the economy, etc.), which depend on a large number of details making them nearly irreducible, so that they cannot be described in terms of a small number of variables. Repeat watching any sections of the video that are hard to follow. When necessary, pause the video to take the notes. This should take about 3 hours of study time.
Terms of Use: This video is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License. It is attributed to videolectures.net and the original version can be found here.See a broken link? Please let us know!
- Web Media: Videolectures.net: Imre Kondor’s "Strong Random Correlations in Complex Systems”
-
4.4 Similarity and Differences by Finite Automata
- Web Media: Videolectures.net: Tamás Gaál’s "Similarity and Differences by Finite Automata”
Link: Videolectures.net: Tamás Gaál’s "Similarity and Differences by Finite Automata" (YouTube)
Instructions: Watch this video about the similarity and differences between finite automata, kernels, morphological analyzers, compilers, and image processors. You may benefit from viewing certain sections of this video more than once; repeat watching the sections of the video that are hard to follow. It may also help to take notes as you watch the video. This should take approximately 3 hours of study time.
Terms of Use: This video is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License. It is attributed to videolectures.net and the original version can be found here.See a broken link? Please let us know!
- Assessment: The Saylor Foundation's "CS411: Unit 4 Quiz"
Link: The Saylor Foundation's "CS411: Unit 4 Quiz"
Instructions: Please take this Unit 4 quiz. When you are done, check your work against the Saylor Foundation's "CS411: Unit 4 Quiz Answer Key" (PDF). This quiz should require less than one hour to complete.The Saylor Foundation does not yet have materials for this portion of the course. If you are interested in contributing your content to fill this gap or aware of a resource that could be used here, please submit it here.
- Web Media: Videolectures.net: Tamás Gaál’s "Similarity and Differences by Finite Automata”
-
Unit 5: The Theory of Quantum Computation: An Introduction
In this unit, we start with the review of basic logic elements. Then, we will study quantum notation and how arbitrary logic gates may be constructed for quantum bits. Next, we show a description of a simple model for a quantum computer based on a classical computer. The second part of this unit consists of video lectures by David Deutsch. These lectures cover an introduction to quantum theory, the quantum theory of computation, physical systems, and the simplest quantum physical system. Also, in the lectures you can see a single-photon interference experiment and learn how to analyze pairs of interacting quantum systems. Other topics include the Schroedinger picture, density matrices, state vectors, pure states, the Schroedinger equation, and the Deutsch algorithm.
Unit 5 Time Advisory show close
Unit 5 Learning Outcomes show close
-
5.1 Quantum Computation
- Reading: The University of York’s Department of Computer Science: Samuel L. Braunstein's “Quantum Computation: a Tutorial”
Link: The University of York’s Department of Computer Science: Samuel L. Braunstein's “Quantum Computation: a Tutorial” (HTML or PDF)
Instructions: From the site, click on the link for “Quantum computation tutorial” to open the HTML version. You may also access the PDF version of this resource from this website. Read the webpage about a survey made by Keyes in 1988 and reversible computation. Then, review the basic logic elements and FANOUT and ERASE gates. This reading covers subunits 5.1.1 through 5.1.4.
Terms of Use: The linked material above has been reposted by the kind permission of Samuel L. Braunstein, and can be viewed in its original from here. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.See a broken link? Please let us know!
- Reading: The University of York’s Department of Computer Science: Samuel L. Braunstein's “Quantum Computation: a Tutorial”
- 5.1.1 Computing at the Atomic Scale
- 5.1.2 Reversible Computation
- 5.1.3 Classical Universal Machines and Logic Gates
- 5.1.4 FANOUT and ERASE
-
5.1.5 Computation without ERASE
- Reading: The University of York’s Department of Computer Science: Samuel L. Braunstein's “Computation without ERASE”
Link: The University of York’s Department of Computer Science: Samuel L. Braunstein's “Computation without ERASE” (HTML or PDF)
Instructions: From the site, click on the link for “Quantum computation tutorial” to open the HTML version and scroll down to access the above listed section. You may also access the PDF version of this resource from this website. Read the material from the webpage to see why primitive ERASE is not absolutely essential in computation.
Terms of Use: The linked material above has been reposted by the kind permission of Samuel L. Braunstein, and can be viewed in its original from here. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.See a broken link? Please let us know!
- Reading: The University of York’s Department of Computer Science: Samuel L. Braunstein's “Computation without ERASE”
-
5.1.6 Quantum Notation and Logic Gates for Quantum Bits
- Reading: The University of York’s Department of Computer Science: Samuel L. Braunstein's “Elementary Quantum Notation” and “Logic Gates for Quantum Bits”
Link: The University of York’s Department of Computer Science: Samuel L. Braunstein's “Elementary Quantum Notation” and “Logic Gates for Quantum Bits” (HTML or PDF)
Instructions: From the site, click on the link for “Quantum computation tutorial” to open the HTML version and scroll down to access the above listed sections. You may also access the PDF version of this resource from this website. Read the material on the webpage to learn about quantum notation and how arbitrary logic gates may be constructed for quantum bits.
Terms of Use: The linked material above has been reposted by the kind permission of Samuel L. Braunstein, and can be viewed in its original from here and here. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.See a broken link? Please let us know!
- Reading: The University of York’s Department of Computer Science: Samuel L. Braunstein's “Elementary Quantum Notation” and “Logic Gates for Quantum Bits”
-
5.1.7 Model Quantum Computer and Quantum Code
- Reading: The University of York’s Department of Computer Science: Samuel L. Braunstein's “Model Quantum Computer and Quantum Code”
Link: The University of York’s Department of Computer Science: Samuel L. Braunstein's “Model Quantum Computer and Quantum Code” (HTML or PDF)
Instructions: From the site, click on the link for “Quantum computation tutorial” to open the HTML version and scroll down to access the above listed section. You may also access the PDF version of this resource from this website. Read the webpage for a description of a simple model of a quantum computer based on a classical computer instructing a machine to manipulate a set of spins.
Terms of Use: The linked material above has been reposted by the kind permission of Samuel L. Braunstein, and can be viewed in its original from here. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.See a broken link? Please let us know!
- Reading: The University of York’s Department of Computer Science: Samuel L. Braunstein's “Model Quantum Computer and Quantum Code”
-
5.1.8 Quantum parallelism: Period of a Sequence
- Reading: The University of York’s Department of Computer Science: Samuel L. Braunstein's “Quantum Parallelism: Period of a Sequence”
Link: The University of York’s Department of Computer Science: Samuel L. Braunstein's “Quantum Parallelism: Period of a Sequence” (HTML or PDF)
Instructions: From the site, click on the link for “Quantum computation tutorial” to open the HTML version and scroll down to access the above listed section. You may also access the PDF version of this resource from this website. Read the webpage for a description of an algorithm which makes use of the quantum parallelism.
Terms of Use: The linked material above has been reposted by the kind permission of Samuel L. Braunstein, and can be viewed in its original from here. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.See a broken link? Please let us know!
- Reading: The University of York’s Department of Computer Science: Samuel L. Braunstein's “Quantum Parallelism: Period of a Sequence”
-
5.1.9 Factoring Numbers and Prospects
- Reading: The University of York’s Department of Computer Science: Samuel L. Braunstein's “Factoring Numbers” and “Prospects”
Link: The University of York’s Department of Computer Science: Samuel L. Braunstein's “Factoring Numbers” and “Prospects” (HTML or PDF)
Instructions: From the site, click on the link for “Quantum computation tutorial” to open the HTML version and scroll down to access the above listed sections. You may also access the PDF version of this resource from this website. Read the two webpages to see an example of factoring a number and to learn about the prospects for quantum computation.
Terms of Use: The linked material above has been reposted by the kind permission of Samuel L. Braunstein, and can be viewed in its original from here and here. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.See a broken link? Please let us know!
- Reading: The University of York’s Department of Computer Science: Samuel L. Braunstein's “Factoring Numbers” and “Prospects”
- 5.2 Lectures on Quantum Computation
-
5.2.1 The Qubit
- Lecture: Hewlett-Packard: David Deutsch’s Lectures on Quantum Computation: "Lecture 1: The Qubit”
Link: Hewlett-Packard: David Deutsch’s Lectures on Quantum Computation: "Lecture 1: The Qubit" (Windows Media Player)
Instructions: Click on the hyperlink titled “Click to Launch Lecture 1” to download the video. Watch this video lecture about the introduction to quantum theory, the quantum theory of computation, physical systems, observations, and the simplest quantum physical system, the qubit. Repeat watching the sections of the video that are hard to follow. When necessary, pause the video to take the notes. This should take approximately 3 hours of study time.
Terms of Use: Please respect the copyright and terms of use displayed on the web page above.See a broken link? Please let us know!
- Lecture: Hewlett-Packard: David Deutsch’s Lectures on Quantum Computation: "Lecture 1: The Qubit”
-
5.2.2 Interference
- Lecture: Hewlett-Packard: David Deutsch’s "Lecture 2: Interference”
Link: Hewlett-Packard: David Deutsch’s "Lecture 2: Interference" (Windows Media Player)
Instructions: Select the “click on to launch” hyperlink to download the video. Watch this video to see a single-photon interference experiment. Repeat watching the sections of the video that are hard to follow. When necessary, pause the video to take the notes. This should about take 2 hours of study time.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.See a broken link? Please let us know!
- Lecture: Hewlett-Packard: David Deutsch’s "Lecture 2: Interference”
-
5.2.3 Measurement
- Lecture: Hewlett-Packard: David Deutsch’s "Lecture 3: Measurement”
Link: Hewlett-Packard: David Deutsch’s "Lecture 3: Measurement" (Windows Media Player)
Instructions: Select the “click on to launch” hyperlink to download the video. Watch this video to learn how to analyze pairs of interacting quantum systems. You may benefit from viewing certain sections of this video more than once; repeat watching the sections of the video that are hard to follow. It may also be useful to take the notes as you watch the video. This should take approximately 2 hours of study time.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.See a broken link? Please let us know!
- Lecture: Hewlett-Packard: David Deutsch’s "Lecture 3: Measurement”
-
5.2.4 The Schroedinger Picture
- Lecture: Hewlett-Packard: David Deutsch’s "Lecture 4: The Schroedinger Picture”
Link: Hewlett-Packard: David Deutsch’s "Lecture 4: The Schroedinger Picture" (Windows Media Player)
Instructions: Select the “click on to launch” hyperlink to download the video. Watch this video about the Schroedinger picture, density matrices, state vectors, pure states, and the Schroedinger equation. This video may require multiple viewings. Repeat watching the sections of the video that are hard to follow. Also, pause the video, when necessary, to take the notes. This should take about 2 hours of study time.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.See a broken link? Please let us know!
- Lecture: Hewlett-Packard: David Deutsch’s "Lecture 4: The Schroedinger Picture”
-
5.2.5 A Quantum Algorithm
- Lecture: Hewlett-Packard: David Deutsch’s "Lecture 5: A Quantum Algorithm”
Link:Hewlett-Packard: David Deutsch’s "Lecture 5: A Quantum Algorithm" (Windows Media Player)
Instructions: Select the “click on to launch” hyperlink to download the video. Watch this video to learn about the Deutsch algorithm. This video may require multiple viewings. You may benefit from reviewing sections of this video multiple times; repeat watching any sections of the video that are hard to follow. When necessary, pause the video to take the notes. This should take approximately 2 hours of study time.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.See a broken link? Please let us know!
- Lecture: Hewlett-Packard: David Deutsch’s "Lecture 5: A Quantum Algorithm”
-
5.2.6 Grover's Search Algorithm
- Lecture: Hewlett-Packard: David Deutsch’s "Grover's Search Algorithm”
Link: Hewlett-Packard: David Deutsch’s "Lecture 6: Grover's Search Algorithm" (Windows Media Player)
Instructions: Select the “click on to launch” hyperlink to download the video. Watch this video to learn how to use quantum computation to search through N possibilities in a time proportional to the square root of N. You may benefit from viewing this video more than once. Repeat watching the sections of the video that are hard to follow. When necessary, pause the video to take the notes. This should take about 2 hours of study time.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.See a broken link? Please let us know!
- Assessment: The Saylor Foundation's "CS411: Unit 5 Quiz"
Link: The Saylor Foundation's "CS411: Unit 5 Quiz"
Instructions: Please take this Unit 5 quiz. When you are done, check your work against the Saylor Foundation's "CS411: Unit 5 Quiz Answer Key" (PDF). This quiz should require less than one hour to complete.The Saylor Foundation does not yet have materials for this portion of the course. If you are interested in contributing your content to fill this gap or aware of a resource that could be used here, please submit it here.
- Lecture: Hewlett-Packard: David Deutsch’s "Grover's Search Algorithm”
-
Final Exam
- Final Exam: The Saylor Foundation's CS411 Final Exam
Link: The Saylor Foundation's CS411 Final Exam
Instructions: You must be logged into your Saylor Foundation School account in order to access this exam. If you do not yet have an account, you will be able to create one, free of charge, after clicking the link.See a broken link? Please let us know!
- Final Exam: The Saylor Foundation's CS411 Final Exam
Questions? Consult the FAQ's!

