Quantum Computing

Sarah Lawrence College
Fall 2019


Those who are not shocked when they first come across quantum theory cannot possibly have understood it.

—Niels Bohr

Course Description

Physicists and philosophers have been trying to understand the strangeness of the subatomic world as revealed by quantum theory since its inception back in the 1920s, but it wasn't until the 1980s—over half a century after the development of the theory—that computer scientists first began to suspect that quantum physics might hold profound implications for computing as well, and that its inherent weirdness might possibly be transformed into a source of immense computational power. This dawning realization was followed soon afterward by key theoretical and practical advances, including the discovery of several important algorithms for quantum computers that could potentially revolutionize (and disrupt) the cryptographic systems protecting practically all of our society's electronic banking, commerce, telecommunications, and national security systems. Around the same time, researchers succeeded in building the first working quantum computers, albeit on a very small scale. Today the multidisciplinary field of quantum computing lies at the intersection of computer science, mathematics, physics, and engineering, and is one of the most active and fascinating areas in science, with potentially far-reaching consequences for the future. This course will introduce students to the theory and applications of quantum computing, from the perspective of computer science. Topics to be covered will include bits and qubits, quantum logic gates and reversible computing, Deutsch's algorithm, Grover's search algorithm, Shor's factoring algorithm, quantum teleportation, and applications to cryptography. No advanced background in physics, mathematics, or computer programming is necessary, beyond a basic familiarity with linear algebra. We will study the quantitative, mathematical theory of quantum computing in detail, but will also consider broader philosophical questions about the nature of physical reality, as well as the future of computing technologies.

Prerequisite: familiarity with linear algebra, or equivalent mathematical preparation.

Instructor

Prof. Jim Marshall
Office: Ilchman Science 100
Phone: 2673 (from off campus: 914-395-2673)
Email: j + my last name + @sarahlawrence.edu

Class Meeting Time

Textbook

Quantum Computing for Computer Scientists
Noson S. Yanofsky and Mirco A. Mannucci

Attendance

On-time attendance is absolutely required for all class meetings and conferences. I realize that occasionally you may need to miss class, but missing more than 2 classes or more than 1 conference will put you in danger of losing credit in the course. If you are unable to attend class or conference due to illness, please contact me about it as soon as possible. If you must miss class or conference for any other reason, please let me know well in advance. No make-up conferences will be scheduled under any circumstances, except possibly if you have a really compelling reason (e.g. medical emergency). Examples of unacceptable reasons include "I forgot!", "I got held up and couldn't make it!", "I thought this was B week!", "I had to pick up my best friend at the airport!", and "I fell asleep on the couch and woke up at 8 pm!"

Email

I will often send out announcements to the class through email, so you are expected to check your Sarah Lawrence email account at least once per day. I will use your @gm.slc.edu address because it is reliable and easy to remember. You should also check the course web pages frequently. I will be happy to answer your questions by email and will try to respond as quickly as possible to messages that pertain to the course.

Getting Help

At times you may find some of the course material to be quite daunting. But don't be discouraged! If you find it difficult, most likely so does the rest of the class. This is just a normal part of the learning process. You are strongly encouraged to come see me as soon as possible whenever you are having difficulty with the material. If you are confused about something, don't stay that way! Staying confused will only make things worse later. Come talk to me as soon as possible so that we can clear up the problem. I'll be more than happy to schedule an appointment. Ask me about it in class, email me, or leave a message on my voice mail. You can also try to catch me on the fly, though I can't always guarantee that I'll have time to meet with you right then.

Academic Honesty

The highest level of academic integrity is expected of every student. You are strongly encouraged to discuss ideas and approaches to solving problems, on a general level, with your fellow classmates, but you are not allowed to share your actual problem solutions or program code with others. All submitted work must be exclusively your own. Effective learning is compromised when this is not the case. The only exception is if I have given you explicit permission to work together on an assignment with a partner.

When in doubt, credit the people or sources from whom you got help. This also goes for any help obtained via the internet. If you are ever unsure about what constitutes acceptable collaboration, just ask. You are also responsible for carefully reading the College's official Policy on Academic Integrity in your Student Handbook. Failure to abide by these rules is considered plagiarism, and will result in severe penalties, including possible failure in the course. Please do not put me, yourself, or anyone else in this unpleasant situation!