Wed, Jan 05
Computing with parallel universes
Slides

 Course overview
 The experimental origins of quantum mechanics
 Quantum computing hype

Computational efficiency and computational models (deterministic, randomized, quantum) and contrasting behaviors for problems like integer multiplication, primality testing, and factorization
Relevant video lecture: ” Parallel Universes”

Basic structures of quantum computation 
Mon, Jan 10
Qubits
Lecture recording
Scribe notes
Suggested reading:
N&C 1.21.3, Mermin 1.11.2

Summary

Superpositions: Consider a system that can be in one of two states and . Our first principle of quantum mechanics
says that if a quantum system can be in two basic states, then it can also be in any superposition of those states.
A superposition is of the form where and are complex numbers and .
(Recall that if , then .)
A qubit is a unit vector in that we think of as superposition of the
two basic states and .
Here are some possible qubit states:

More generally, the state of dimensional quantum system is described by a unit vector
which we think of
as a superposition of the basic states .
So we can think of as the standard basis for .

Braket notation: In Dirac’s notation,
a vector of the form is a column vector, and is shorthand for the conjugate tranpose vector .
One then writes the inner product of two vectors as
where is the complex conjugate.

Measurements: Suppose we have a state and an orthonormal basis of .
We can express in this basis as
Our second principle of quantum mechanics asserts
that when we measure in this basis, the state collapses to with probability .
Note that since is an orthonormal basis, we have
where the latter inequality follows since is a quantum state (and thus a unit vector).
Example:
Consider the orthornormal basis defined by

If we measure the state in this basis, we will obtain the state with
probability and the state with probability .

If we measure the state in the basis, we will obtain the state
with probability
and we will obtain the state with probability
Related videos:

Wed, Jan 12
Single qubit transformations
Lecture recording
Scribe notes
Suggested reading:
N&C 1.3, Mermin 1.3

Summary

Our third principle of quantum mechanics is that one can perform any unitary operation on a qudit state .

A unitary operation is a linear map that preserves the length of vectors.
Such maps can be described as complex matrices with the property that .
Equivalently, these are matrices whose rows form an orthornomal basis of (equivalently,
whose columns form an orthonormal basis of ).

As an example, for some angle , one can consider the rotation matrix

For instance, If we take , then and
.

Another unitary operation is the reflection
This is called “X” for historical reasons. It’s also known as the quantum NOT or the swap operator
since it satisfies and .

You should check: If we want to change the basis into , we can use the unitary operator .

Since we can use unitary operations to map any orthonormal basis of to any other orthonormal basis,
we don’t need the ability to measure in an arbitrary basis .
If we let be the matrix with as the columns, then satisfies
, hence we can start with a state , map it to ,
measure in the standard basis , and then apply to the collapsed state.
You should check: This is equivalent to measuring in the basis .
In other words, the outcome state is with probability .

In lecture, we saw how to use small rotations to implement the ElitzurVaidman quantum bomb detection algorithm.
Related videos:

Wed, Jan 19
Composite quantum systems
Suggested reading:
N&C 1.3; Mermin 1.41.6

Summary

We have seen that the quantum mechanical operations allowed on a quantum state are given by
the unitary matrices .

In the case , examples of singlequbit gates include the real rotation matrices
the quantum NOT gate
and the Hadamard gate

We can encode a twoqubit state as a vector using the basis

Let us consider three different ways of representing the qubit controlled NOT gate :

We can write it as the matrix

Equivalently, we can express its action on an orthornormal basis:
The first bit is the control bit, and it is simply copied to the output.
If the first bit is , we leave the second bit unchanged.
But if the first is , we perform a NOT on the second bit.

Finally, we can write it in the quantum circuit notation:
Note the suggestive notation: The first bit is passed through unchanged, while the second bit
becomes the XOR of the first two bits.

Another qubit gate is the swap gate:
As the name suggests, this swaps the first and second qubits:

If we have two qubits and we want to apply a gate to them, we
need a way of representing the composite state as a vector in .
This will be the tensor product .
Our fourth principle of quantum mechanics asserts that
if and are two quantum states, then their joint quantum system is described
by the state . Recall that the tensor product of two vectors
and is the vector given by .

Examples:
Note that we have used the shorthand , etc.
We have also used bilinearity of the tensor product:

This allows us to evaluate arbitrary quantum circuits. For instance, consider:
Applying a Hadamard gate to the first qubit yields .
The tensor product rule tells us that the joint state of the two qubits after the Hadamard gate is given by
Now we can apply the gate. By linearity, we can consider its action on each piece and , hence
the output of the circuit is the state

This is called the Bell state. Its importance lies in the fact that it’s entangled, i.e., there is
now way to write for single qubit states
.
Indeed, suppose we could write .
Notice that the product of the first and last entries of the latter vector is , and this is also equal
to the product of the two middle entries. Since that property doesn’t hold for , no such
decomposition is possible.
A composite state that cannot be written as a tensor product of joint states is said to be entangled.

Let’s try one more: (You should verify the calculations!)
After the first two Hadamard gates, the system is in the state
Now applying the first controlledNOT gate to the first two qubits yields the state
Finally, applying the second controlledNOT bit to the second two qubits yields the state

Recall that and 2bit gates are universal for classical computation (Problem 1 on HW1),
and , 2bit , and gates are universal for randomized computation (Problem 2 on HW1).
Here’s a very useful fact: Single qubit gates and the 2qubit gate are universal for quantum computation,
in the sense that every unitary can be approximated arbitrarily well by a circuit on
input qubits consisting
only of such gates. (Note: This doesn’t tell us anything about the size of such a circuit!)
Related videos:

Mon, Jan 24
Operations on subsystems and partial measurements
Suggested reading:
N&C 2.2, Mermin 1.71.12

Summary

Tensor products:

Note that the defining characteristic of the tensor product is multilinearity, which simply means
that for vectors , the expression
is linear in each vector so that, for instance,
Note that this is just like how normal multiplication distributes over addition. But do note that tensor products are definitely
not commutative: The vectors and are not equal unless .

Given matrices , we can form
the tensor product
One can think of this object in various way, e.g., we can meaningfully write
thinking of this as a multidimensional array of numbers.
It is most useful to think of it as a linear map taking vectors in
to vectors in , where the map is applied just as you would expect:

Unitaries acting on subsystems: Recall this quantum circuit from the previous lecture.
Just before the last gate, the 3qubit state is
The last gate acts only on the last two qubits, but we need to define its action
on a 3qubit state. Our fifth principle of quantum mechanics tells us how to
applying a unitary to a subsystem affects the entire state.
Note that, by linearity, we need only understand its action on each of the basis states , , , and .
Recall that . The fifth princple says that to apply the gate to the last two bits,
we just act in that component of the tensor product:
Equivalently, in order to apply to the last two qubits, we apply the matrix
to the entire 3qubit state, where is the identity matrix on the first qubit.
Thus this circuit outputs the state

Note that there is no reason that the needs to act on “adjacent” qubits (adjacency here is just an artifact
of how we drew the circuits). We could equally well consider a circuit where the final gate acts on
the first and third qubits:
You should check that the output state is
It is a coincidence that these two circuits give the same output on input .
(It is not true that they give the same output for every input.)

Partial measurements:
Suppose that we have a 2qubit state
Suppose also that Alice takes the first qubit, Bob takes the second, and then Alice
measures her qubit in the basis. The new joint state is given by the Born rule,
which agrees with the standard notion of conditional probabilities.
With probability , Alice measures outcome “0” and
the joint state collapses to
and with probability , Alice measures outcome “1”
and the joint state collapses to
Related videos:

Basics of quantum information 
Wed, Jan 26
Bell's theorem and the EPR paradox
Suggested reading:
N&C 2.6

Summary

The CHSH game can be described as follows:
There are three participants: Alice, Bob, and a Referee. The Referee chooses
two uniformly random bits and sends to Alice and to Bob.
Alice outputs a bit and Bob outputs a bit , and their goal is to achieve the outcome
It is easy to check that for any of the 16 pairs of strategies for Alice and Bob,
described by functions , there must be at least one choice
that fails to achieve the goal \eqref{eq:goal}.
Thus the maximum success probability for Alice and Bob is at most .

Even if Alice and Bob have shared random bits, they cannot achieve better than .
Indeed, let be a string of random bits, then
for every fixed choice of , we have
So this still holds whene we average over the random string .

It turns out that if Alice and Bob share an EPR pair ,
then they can do strictly better than just by using shared randomness: They can achieve success probability

The protocol is as follows:

Alice:

Bob:

:
Bob measures his qubit in the basis and outputs or , respectively.
Equivalently, this is the standard basis rotated by .

:
Bob measures his qubit in the basis and outputs or , respectively.
Equivalently, this is the standard basis rotated by .

For example, let’s analyze the success
probability in the case . Since , we need , i.e.,
we need the measurement outcomes or .
With probability , Alice measures and Bob’s qubit collapses to the state .
Then the probability he measures is .
With probability , Alice measures and Bob’s qubit collapses to the state .
Then the probability he measures is .
Hence the overall success probability is .

As an exercise, you should try repeating the analysis from lecture for the other three cases.
For the case where , it helps to verify first that the EPR pair can equivalently be written as

In the early 1980s, experiments acheived .

In 2014, it was verified at large scales (1.3km).

The famous Tsirelson inequality shows that no
quantum strategy can do better than .

Some philosophical discussion around the EPR paradox and Bell’s theorem
Related videos:

Mon, Jan 31
The NoCloning Theorem and quantum teleportation
Suggested reading:
N&C 12.1 & 1.3.7; Mermin 2.1 & 6.5

Summary

Nocloning Theorem: There is no quantum operation that starts with a state and outputs two copies .
More formally, there is no quantum circuit that takes as input a qubit
along with ancilliary bits and outputs a state
where the first two qubits are copies of .
Note that a successfully copies the control bits and when the other input is :
On the other hand, fails to copy :
As we know, this is not a tensor product state. To successfully clone, we wanted to get the state

Proof of the NoCloning Theorem:
Suppose we have a quantum circuit without intermediate measurements that clones an input qubit. (We will see later in the course that
measurements can always be deferred to the end of a quantum computation. This is called the
Principle of Deferred Measurement.)
Consider its operation on ,, and :
where are some arbitrary states depending on the input. Then since the circuit must correspond
to multiplication by a unitary matrix, it must act linearly, and by and , its output on must be equal to
But this can never be equal to the RHS of since
(Two see that these two states cannot be equal, considering measuring the first two qubits.)

The NoCloning Theorem implies that it is impossible to learn the amplitudes of a qubit since
if we knew and , we could build a circuit that, on input , would output .
And then we could make as many copies of as we wanted. Just for review, note that the following
single qubit unitary gate maps to :

Quantum tomography studies the best way to learn a quantum state
given many copies .

Quantum teleportation: This is the idea that if Alice and Bob share an EPR pair ,
then Alice can “teleport” an arbitrary qubit state to Bob by sending him only two bits of classical information.
Here is a sketch: Alice has the qubit state and the first qubit of the EPR pair ,
and Bob has the second qubit of .
Alice first applies a gate to her two qubits and the state evolves as
She then applies a Hadamard gate to her first qubit, giving the state
Alice now measures her two qubits, giving each of the four outcomes with probability .
Bob’s state collapses to one of the four options above, and when he receives the message from Alice,
it tells him which unitary he can apply to convert his state to !
For example, if the messages is , he just applies the identity. If the message is , he applies the unitary
, etc.
Related videos:

Wed, Feb 02
Quantum coins and onetime pads

Summary

A scheme for quantum money: The NoCloning Theorem suggests that we might be able to achieve true “copy protection”
using properties of quantum states. As an example, we can try to design a scheme for making “coins” that can
be verified as real, but not copied.

In class we studied the Wiesner scheme, where the bank chooses uniformly at random
a serial number and a string and constructs the state
The coin is then the pair .

The bank verifies the coin by measuring every qubit of in either the basis (for ) or
the basis (for ) and checking that the answer is equal to .
(See Homework #3.)

We saw that in this scheme, the bank should not return coins that have been verified as valid, since otherwise there
is a clever attack to learn the state . The attack is similar to detecting the ElitzurVaidman bomb.
Let be a rotation by angle .
Choose a sufficiently large even number and take .
The attacker tries to learn each qubit of in succession. Consider . The attacker introduces an auxiliary qubit
that starts in the state, so the system is .
Then the attacker repeats the following times:

Consider the the four cases:

If , a single round yields the state
When the bank measures the second qubit in the basis,
it detects fraud with probility (for small),
and otherwise measures and the state collapses to the initial state .
If fraud is not detected for rounds, the resulting state is .

If , a single round yields the state
When the bank measures the second qubit in the basis,
it detects fraud with probility (for small),
and otherwise measures and the state collapses to the initial state .
If fraud is not detected for rounds, the resulting state is .

If , a single round yields the state
When the bank measures the second qubit in the basis,
it always gets the correct outcome , and the state collapses to .
In the next round, we first apply , yielding . The bank measures
the second qubit correctly, and the state collapses to .
Therefore after rounds (recall that is even!), the resulting state is .

If , a single round yields the state
When the bank measures the second qubit in the basis,
it always gets the correct outcome , and the state collapses to .
After rounds, we have applied a rotation by , hence the resulting state is .

If we are not caught cheating, then after all rounds, we can measure the first bit in the basis
and with certainty determine whether or .
Our chance of being caught is at most .
By slighty modifying the protocol (exercise: what’s the modification?), we can also test whether .
If neither of these is true, we know that we can measure in the and determine
its value with certainty.
So we can determine with a probability of at most of getting caught.
Now repeat this for every qubit . We determine all the values with at most a chance of getting caught.
So by setting (say), we can successfully learn with less than a half percent chance we are caught.
(And then we can make as many copies of as we like!)
Related videos:

Quantum algorithms 
Mon, Feb 07
BernsteinVazirani
Suggested reading:
Mermin 2.12.4

Summary

Definition: If is a function from bits to bits, then a quantum circuit
implementing is one that maps
Here, represents the bitwise exclusiveor operation.
The first register is on qubits, and the third register is on qubits.
The additional qubits are called ancillas.
The size of the circuit is the number of basic quantum gates.

If is computed by a classical circuit with gates, then there is a quantum
circuit implementing that uses only gates.

Suppose we have a function with only a single output bit.
We say that a quantum circuit signimplements , if it maps

If denotes a standard implementation of (as in \eqref{eq:standard}), then we can
construct a sign implementation as:
In other words, instead of taking in \eqref{eq:standard}, we use .
The result is:
Then after applying , we apply a Hadamard gate followed by a NOT gate to transform into .

The BernsteinVazirani problem: Here we are given a function and promised that
for some hidden vector . The goal is to learn by evaluating .

This can be done classically by using queries, since ,
where is the vector with a in the th coordinate and zeros elsewhere.
And it is not hard to see that this is the smallest possible number of queries
that will always recover .

Here is a quantum circuit that evaluates only once (with its input in superposition!) and outputs the
hidden vector with certainty:
This output of the circuit can be summarized as ,
where is an fold tensor product of Hadamard matrices,
and is a signimplementation of .

Analysis: After the first set of Hadamard gates, the overall state is
After applying , the result is
To apply to this state, it helps to observe that for ,
Therefore applying to \eqref{eq:sup15} gives
Now note that for any fixed value of , we have
This equality holds because if , then , and regardless of the value of ,
we have . On the other hand, if , then ,
and , meaning that the terms corresponding to and have
opposite signs and cancel out.
Therefore the output of the circuit \eqref{eq:sup16} is precisely , revealing the hidden string .

Wed, Feb 09
Simon's algorithm
Suggested reading:
Mermin 2.5

Summary

Simon’s problem: Consider a function that is periodic in the
sense that for some with , it holds that
where is bitwise XOR, and moreover, we assume that .
The problem is: Given access to a quantum circuit implementing , to determine
using as few copies of as possible.

If we are only given a classical circuit computing , it turns out this problem
is pretty difficult: At least copies of are needed to build a probabilistic
circuit that recovers with high probability.

Simon’s algorithm allows us to do this with a quantum algorithm that requires only copies of ,
an exponential improvement!

To accomplish this, we prepare the state

Then we measure the qubits in the answer register. By definition of periodic, each possible value
occurs twice, since . The probability of measuring is , and then our state
collapses to

After discarding the measured register (which is unentangled with the input register), we are left with the state
. Clearly if we knew both and , then we could
take their bitwise XOR and recover .

Now we apply the Quantum Fourier transform again to this state, obtaining

When we measure this qubit, the outcome is a uniformly random string such that .

Suppose we sample such strings satisfying .
If these vectors are linearly independent over , then the system of linear equations
has exactly two solutions (over ): and , and we can find the solution
by (classical) Gaussian elimination.

Claim: With probability at least , it holds that are linearly
independent over , meaning that with probability at least , we recover the hidden period .

Proof: If are linearly independent, then they span
a dimensional subspace in , which has vectors, hence
and
Related videos:

Mon, Feb 14
The quantum Fourier transform
Suggested reading:
N&C 5.15.2

Summary

The Quantum Fourier transform
Define and given with ,
encode as the quantum state
Then applying gives ,
where
In other words, implements the Fourier transform over .
Equivalently, maps the Fourier basis
to the computational basis , where
and we similarly encode
In this notation, we can write .

The Quantum Fourier transform over
We use to denote the integers modulo . Given with
, we can similarly encode as a quantum state:
Now the Fourier basis is given by the functions
where is a primitive th root of unity.
These functions can similarly be encoded as quantum states:
You should verify that the vectors actually form
an orthonormal basis of .
The quantum Fourier transform is given by the unitary map
where we have used the fact that the complex conjugate of is .

An efficient implementation of the quantum Fourier transform over
Assume now that for some and define .
The Fourier transform over could be implemented using only quantum gates.
A related implementation is possible over . We need to implement the unitary change of basis:
Let us write in binary . Then we have
and we can write this as the tensor product
Let us write this as ,
and then it suffices to produce a circuit where the output wires carry each .

The case . It is instructive to do this for a fixed value, say . Then we have
where in the last line we are just giving names to each piece of the tensor product
that we would like to produce on the output wires.
Starting with , we have
since the other terms in the exponent vanish modulo 16.
Note that , hence we have
Similarly, we have
so we can write
Let be a qubit “controlled gate”
in the sense that
Note that this is specified by the matrix
Then we can write (check this!):
Continuing this way yields a circuit for all output wires:

In the general case, the number of gates needed is .
If one wants to implement the circuit approximately (but sufficient, e.g., for Shor’s algorithm),
it is possible to use only  and qubit gates.
Related videos:

Wed, Feb 16
Shor's algorithm I: Period finding
Suggested reading:
N&C 5.3

Summary
 Consider and let denote the integers modulo .

Suppose we have a function that is periodic in the sense that
and our goal is to find the period $L$.

Recall that we assume is implemented by a circuit with the behavior:

We will use a variant of Simon’s algorithm, as follows:

First we prepare the state

Then we measure the second register, obtaining an outcome , and the state collapses to
Note that since has period , it must be that divides and the number of colors used is ,
and each color is used times. So we see each
with probability .

Finally, we discard the second register (note that it is unentangled with the first register), yielding the state
where is given by

Now we use the Quantum Fourier transform from the previous lecture to compute
and we measure the register, yielding the measurement outcome with probability .

Computing the Fourier transform yields
In other words, the outcome of the measurement is a uniformly random number , i.e., a random multiple of .
Note that from we can compute .
By running the whole algorithm twice, we find two random multiples and , and it holds that
thus with constant probability we recover , from which we can compute the period .

This still works even if we only assume that is almost periodic in the sense that
where now addition is not taken modulo (so it is not required that divides ).
In this case, Fourier sampling has the following guarantee: With probability at least , we see
where is chosen uniformly at random,
and denotes the closest integer to .

Wed, Feb 23
Shor's algorithm II: Factoring
Suggested reading:
N&C 5.35.4

Summary
 We show how periodfinding leads to an algorithm for factoring. The reduction is entirely classical.
 Suppose are distinct prime numbers and . Given an bit number as input, we want to find and .
 To do this, we saw that it suffices to find a nontrivial squareroot of modulo .
 On Homework #4, you will show that the following works with probability :
 Choose uniformly at random.
 Define by , where we take and .
 If is the order of modulo , then
will be almost periodic.
 Now we use the quantum periodfinding algorithm from the previous lecture to find .
 If is even, then our candidate for a nontrivial squareroot of is the number .
On the homework, you will show that with probability at least , it
holds that is even and .

The last part of the lecture was devoted to finding in the case when the function is almost periodic.
(We saw how to do this already when is exactly periodic.)
Recall that in this case, with probability at least , we obtain for
a uniformly random .

Therefore we have
for some integer .
Now we construct the continued fraction expansionof ,
which produces a sequence of approximations to .
Lemma: If , then occurs as one of the
convergents in the continued fraction expansion of .
This is why we choose where , to ensure that (with room to spare).
 So we get the fraction in lowest terms. If , then we can use that to recover .
Since is uniformly random, it will be prime with probability at least
by the Prime Number Theorem.

Mon, Feb 28
Grover's algorithm
Suggested reading:
N&C 6.16.2

Summary
 Given a function , we would like to find an such that .

Recall that is the sign oracle implementation of , where

The Grover iteration is given by the unitary
where .
You should check that is a unitary matrix, and that it can be efficiently
implemented on a quantum computer because
where is defined by for .

Define and the states
Then we can write the uniform superposition as

It turn outs that remains in the plane spanned by , so this is
also true for for all .
This is true because
hence is a reflection around the axis (in the plane).
Moreover,
for any vector that is orthogonal to , so this operator is a reflection about .

We conclude that maps the plane to itself and is the composition of two reflections.
That means is rotation, and we can calculate that if
then
hence in the plane, is a rotation by angle . Therefore:

Since ,
it holds that for , we have .
Hence we can choose appropriately so that
in which case, when we measure, we have at least a 10% chance of sampling an such that .

We can accomplish this even if we only know that for some .
Hence we can try until we find an such that . The number of queries we need
will be on the order of

Quantum information theory 
Wed, Mar 02
Quantum probability

Lecture notes from The art and science of PSD matrices:

Mon, Mar 07
Quantum information

Lecture notes from The art and science of PSD matrices:

Wed, Mar 09
Partial trace and the Holevo bound

