# CS411: Non-Standard Computing

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.

This unit will take approximately 37 hours to complete.

☐    Subunit 5.1: 18 hours

☐    Subunit 5.1.1: 2 hours

☐    Subunit 5.1.2: 2 hours

☐    Subunit 5.1.3: 2 hours

☐    Subunit 5.1.4: 2 hours

☐    Subunit 5.1.5: 2 hours

☐    Subunit 5.1.6: 2 hours

☐    Subunit 5.1.7: 2 hours

☐    Subunit 5.1.8: 2 hours

☐    Subunit 5.1.9: 2 hours

☐    Subunit 5.2: 18 hours

☐    Subunit 5.2.1: 3 hours

☐    Subunit 5.2.2: 3 hours

☐    Subunit 5.2.3: 3 hours

☐    Subunit 5.2.4: 3 hours

☐    Subunit 5.2.5: 3 hours

☐    Subunit 5.2.6: 3 hours

☐    Unit 5 Assessment: 1 hour

Unit5 Learning Outcomes
Upon successful completion of this unit, the student will be able to:

• Explain how reversible computation works.
• Describe conceptually FANOUT and ERASE gates.
• Define the elementary quantum notation.
• Describe how arbitrary 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 the quantum parallelism.
• Conceptually describe the simplest quantum physical system, the qubit.
• Describe a single-photon interference experiment.
• Explain the Schroedinger equation.
• Explain the workings of the Deutsch algorithm and Grover’s search algorithm.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.