2 of 42

Logistics

Lecture: Tuesday, Thursday 10-11.20am, CSE2 G01

Office hours – starting week 2 (but one of them should start this week)

Andrea: Tuesday 4-5 (starting week 2)
Others: TBA

Offline discussion: on Ed Discussion (let me know if you didn’t receive invitation)

3 of 42

Logistics

Homeworks: posted on course webpage each Tuesday�(due following Wednesday at 11.59pm). First one due April 8.

Submissions: Gradescope (let me know if you didn’t receive invitation)

Grading:

6 homeworks: 48%
1 midterm (take home): 20%
1 final (in class): 32%�

Recordings: on canvas

Handwritten notes of whiteboard: posted on course webpage

4 of 42

Policies

Collaboration on homeworks: encouraged, but write up solutions individually (don’t use AI or search online for solutions)

Late submissions:

5 token for 24 hours late submission, no questions asked (can use at most 3 on the same homework, but cannot be used on the midterm)�

Midterm: take-home, with access to lecture notes

Final: in class, closed book (no advice sheet)

The lecture right after midterm will review solutions. You can get back 1/3 of the lost points on the midterm if you submit corrected/completed solutions by the following Wednesday.

5 of 42

Rough overview of the course

First half focuses on Quantum Information

Second half focuses on Quantum Computation

Familiarize with the “language”
Some fascinating examples: Quantum Key Distribution, Non-Local Games & Entanglement..

Circuit model of quantum computation
Famous quantum algorithms: Grover Search, Shor’s factoring..

Heads up: this is a ”theory” class! (some quantum programming component towards the end, but 95% theory: you will be solving problems with pen and paper, and there will be many proofs)

6 of 42

This lecture

What is quantum computation?

Double-slit experiment

Complex numbers & Linear Algebra review

7 of 42

What is Quantum Computation?

A new paradigm for computation that is based on

the laws of quantum mechanics

Why bother?

8 of 42

Why bother?

Chemistry:

Optimization/Machine Learning:

Simulating dynamics of quantum systems

Cryptography:

Speeding up unstructured search

Speeding up Linear Algebra

On the negative side.. breaking most of today’s encryption!

On the positive side.. Realizing cryptographic functionalities that are �impossible to achieve classically!

Many potential applications:

Exponential speedup

Generally only polynomial speedup

Shor’s algorithm

“..if you want to make a simulation of nature, you’d better make it quantum mechanical” �– Richard Feynman

Most promising domain is chemistry. A crucial part of developing new drugs and new proteins is to understand how molecules behave. At a fundamental level molecules are quantum systems. Simulating the behaviour/dynamics of quantum systems is something is computationally very expensive, intractable in many cases. Perhaps unsurprisingly, quantum computers seem to be very good at is simulating the dynamics of quantum systems. This is a problem for which (in some formal sense) they achieve an exponential speedup over best-known classical algorithms. Actually, simulating quantum systems was the original motivation that led Richard Feynman to ”dream up” the concept of a quantum computer. He thought that if we are attempting to simulate quantum systems we should do it using a quantum computer.

9 of 42

Why bother?

Philosophical implications!

Randomness vs Determinism

Non-locality vs locality

One universe vs many universes..

10 of 42

Why bother?

It’s a beautiful field that is rapidly developing

- many challenges and discoveries ahead.

Current quantum devices are on the cusp of �demonstrating quantum advantage (or have already done so depending on who you ask)!

. . .

Source

Case 1: Ping pong ball

Observations:

Each ball hits the detector at a single point
Balls land in front of �the first or the second slit

Source

Case 2: Water wave

28 of 42

Source

Case 2: Water wave

29 of 42

Source

Case 2: Water wave

30 of 42

Case 2: Water wave

Observations:

Wave hits the detector at many points
We see an “interference” pattern

35 of 42

Source

Case 3: Photon

36 of 42

Source

Case 3: Photon

Observations:

Each photon hits the detector at a single point
We still see an “interference” pattern!

How is this possible?

37 of 42

Case 3: Photon

Observations:

Each photon hits the detector at a single point
We still see an “interference” pattern!

How is this possible?

1. The photons are “interfering” with one another?

No! Actually we still see the interference pattern

even when we really send the photons one by one!

2. Each photon is “interfering with itself”??

If so then, just like a water wave,

each photon must be passing through both slits..?

38 of 42

Source

Case 3*: Photon, with a camera

“left”

“right”

Observations:

The interference pattern disappears!
The photon behaves as in Case 1!

(or electron)

39 of 42

Double-slit experiment recap

Quantum mechanics is the theory that can explain all of this absurdity!

Case 1: Ping-pong ball

Case 2: Water wave

Case 3: Photon

Case 3*: Photon,� with a camera

Each ball hits the detector at a single point
Balls land in front of the first or the second slit

Wave hits the detector at many points
We see an “interference” pattern

The interference pattern disappears!
The photon behaves as in Case 1!

Each photon hits the detector at a single point
We still see an “interference” pattern!

40 of 42

Looking ahead

Quantum computation is about orchestrating interference �in such a way that the “interference pattern’’ tells us something useful, �e.g. the solution to a problem!

41 of 42

Looking ahead

The simplest quantum mechanical system has two degrees of freedom/configurations.

The state of the quantum system can be in a “superposition” of the two.

Examples of quantum systems:

Photon in double-slit experiment

Degrees of freedom: “left” or “right”

Electron spin

Degrees of freedom: “up” or “down”

Photon polarization

Degrees of freedom: “vertical” or “horizontal”

42 of 42

Looking ahead

The simplest quantum mechanical system has two degrees of freedom/configurations.

The state of the quantum system can be in a “superposition” of the two.

Examples of quantum systems:

Photon in double-slit experiment

Degrees of freedom: “left” or “right”

Electron spin

Degrees of freedom: “up” or “down”

Photon polarization

Degrees of freedom: “vertical” or “horizontal”

In this course, we will take an abstract view:

A quantum system with two degrees of freedom is a qubit!