Quantum Class 1, Mon 2021-08-30
Table of contents
1 Misc
1.1 Syllabus
Read the syllabus, accessible from the top bar.
1.2 Gradescope
We'll use Gradescope for submitting homeworks and possibly projects. I synced it with LMS on as of 8/29.
1.3 Iclicker
We may use the new version of iclicker for in-class quizzes.
1.4 My research
I do parallel geometry algorithms on large problems for CAD and GIS. See my home page. If this is interesting, talk to me. Maybe you can do something that leads to a jointly-authored paper.
1.5 Changes from last year
New textbooks.
More non-IBM material.
No piazza.
Class is in person.
1.6 Optional text
Quantum Computing for Computer Scientists 1st Edition
I used this last year. This is nice but is 20 years old, and so omits some things. However I'll refer to it a little.
I encourage you to read several books, and pick and choose.
2 Quantum Computing: An Applied Approach, chapter 1
-
Quantum computer: uses properties of quantum mechanics to compute
world is quantum.
compare to classical computer.
-
quantum properties
superposition
entanglement
-
state: complete math description of state.
a complex vector.
classical analog: e.g., position of a particle.
-
superposition: linear combo of states is a legal state.
the weights are complex numbers.
everything in quantum mechanics uses complex numbers.
superposition does not work classically.
-
measurement of a state $\Psi$:
this discussion assumes some specific set of basis vectors.
you can use different basis systems to represent the same vector, and rotate between them.
$\Psi$ is a linear combo of the basis vectors.
the measurement is also defined wrt that basis.
it changes $\Psi$ state randomly to one of the basis vectors.
the observed output of the measurement is that basis vector.
the probability of $\Psi$ changing to a particular basis vector is the modulus squared of the weight of that basis vector.
define $z^c$ to be the complex conjugate of $z$.
if $\Psi= \alpha\psi_1+\beta\psi_2$, where $\alpha^2+\beta^2=1$ then the probability of $\Psi$ changing to $\psi_1$ is $\alpha^c\alpha$. (the Born rule)
$\alpha^c\alpha$ is called the modulus squared.
important: measuring changes the system.
see the polarization example in the book
A qubit $q$ is a quantum analog to a classical bit.
the quantum analog to classical bits 0 and 1 are $|0\!\!>$ and $|1\!\!>$.
-
q's state is a superposition (linear combo) of those two basis states:
$q = a|0\!\!> + b|1\!\!>$ ,
where the weights $a$ and $b$ are complex numbers, and $ | a | ^2 + | b | ^2 = 1$.
Note the weird notation (Dirac notation). In $|0\!\!>$, $|$ is like a left bracket and $>$ like a right one.
It is wrong to think that $q$ is really in one of the two states, but you don't know which one. This is the hidden variable theory. It has been proved experimentally to be false.
-
$q$ is really in both states simultaneously.
Alice laughed. "There's no use trying," she said: "one can't believe impossible things." "I daresay you haven't had much practice," said the Queen. "When I was your age, I always did it for half-an-hour a day. Why, sometimes I've believed as many as six impossible things before breakfast." - Through the Looking-Glass, and What Alice Found There (1871), by Lewis Carroll (Charles Lutwidge Dodgson).
You cannot observe its state, unless it is $|0\!\!>$ and $|1\!\!>$, in which case you observe $0$ or $1$. This is the classical case.
-
Otherwise you observe it with a measurement operator that transforms it to either $|0\!\!>$ and $|1\!\!>$, with probabilities
$| a | ^2$ and $| b | ^2$, respectively.
$a$ and $b$ are complex.
That measurement changes $q$; it no longer has its old value.
You cannot reclaim the old value.
-
There are many possible measurement operators available.
You can choose which to apply to $q$.
That prevents you from applying the others to $q$, because you don't have $q$ available any more.
Heisenberg uncertainty: measuring, say, position, prevents you from accurately measuring momentum.
$q$, that is, $q$ 's value, can be considered to be a vector of length two: $$\begin{pmatrix} a | 0\!\!> \\ b | 1\!\!> \end{pmatrix} $$ or simply $$\begin{pmatrix}a\\b\end{pmatrix}$$.
You operate on $q$ with a matrix multiplication: $q_2 = M q$.
Unless $M$ is a measurement operator, it is invertible, so you can go backwards.
-
Examples of 1-qubit gates
not
square root of not
rotation, phase shift
No cloning: You cannot copy a qubit, but can move it.
-
The life cycle of a qubit:
Create a qubit with a classical value, 0 or 1.
Operate on it with matrices, which rotate it to have complex weights.
Measure it by randomly projecting it onto a basis vector.
So far, not very powerful.
-
a quantum state $\Psi$ usually has many qubits.
compare to a classical byte with 8 classical bits.
-
However the different qubits in $\Psi$$ might be entangled.
This is very weird and powerful.
Entanglement means that if you measure one qubit then what you observe restricts what would be observed when you measure the other qubit.
Even if the two qubits are 1000 mi apart. This has been experimentally observed.
However that does not let you communicate.
2.1 Entanglement
Crazy counterintuitive idea that's the basis for quantum speedup.
-
Classical metaphor for entanglement:
Start with a piece of paper.
Tear it into two halves.
Put each half into an envelope, seal them, and mix them up, so that you can't tell which half is in which envelope.
Address and mail one envelope to a friend in Australia, and the other to a friend in Greenland.
When the Australian opens his envelope, he knows what the Greenlander will find in his.
However that doesn't let the Australian send any info to the Greenlander, or vv.
This has been demonstrated with real qubits transported 1000 miles apart.
Entanglement means that if you measure one qubit then what you observe restricts what would be observed when you measure the other qubit.
However that does not let you communicate.
The preceding metaphor is wrong in that it has a hidden variable, the unobserved half-paper state. That does not happen in quantum physics. With qubits, the states are not fixed until one is observed. I'm trying to get the idea across.
2.2 Reversibility of Quantum Computation (p9)
#. All operators used in quantum computation other than for measurement must be reversible. - textbook.
Contrast to classical operators like and and or.
3 Chapter 2: history
Read it on your own, but here are some additions:
The property list on p15 is controversial and seems designed to exclude D-Wave.
Like for classical computation, the main ideas of quantum computing were proposed before actual machines could be built.
4 Chapter 3: Qubits, Operators and Measurement
(from the text callout 3.1) qubit: a two-level quantum mechanical system.
state at any given time is a vector in a 2-D complex Hilbert space.
4.1 Two qubit operators
Now, let $q$ be a system with two qubits, i.e., a 2-vector of qubits.
$q$ is now a linear combo of 4 basis values, $ | 00\!\!>$, $ | 01\!\!>$, $ | 10\!\!>$, $ | 11\!\!>$.
$q = a_0 | 00\!\!> + a_1 | 01\!\!> + a_2 | 10\!\!> + a_3 | 11\!\!> $
where $a_i$ are complex and $ \sum | a_i | ^2 = 1$.
$q$ exists in all 4 states simultaneously.
If $q$ is a vector with n component qubits, then it exists in $2^n$ states simultaneously.
This is part of the reason that quantum computation is powerful.
A measurement operator applied to $q$ will rotate it to a basis {00, 01, 10, 11}, so that it will be observed in one of those four cases, with probabilities $ | a_i | ^2$.
You operate on $q$ by multiplying it by a 4x4 matrix operator.
The matrices are all invertible (except for measurement matrices), and all leave $ | q | = 1$.
You set the initial value of $q$ by setting its two qubits each to 0 or 1.
How this is done depends on the particular hw.
-
I.e., initially, $q_1 = \begin{pmatrix}a_1 | 0\!\!> \\b_1 | 1\!\!> \end{pmatrix}$ and $q_2 = \begin{pmatrix}a_2 | 0\!\!> \\b_2 | 1\!\!> \end{pmatrix}$, and so
$$q = \begin{pmatrix} q_1 \\ q_2 \end{pmatrix} = \begin{pmatrix} a_1 a_2 | 00 \!\!> \\ a_1 b_2 | 01 \!\!> \\ a_2 b_1 | 10 \!\!> \\ b_1 b_2 | 11 \!\!> \end{pmatrix}$$.
The combined state is the tensor product of the individual qubits.
In this case, you could separate out the individual qubits again.
However, sometimes after operating on the combo (i.e., multiplying by a matrix), you cannot any more separate out the result into a tensor product of individual qubits.
For $n$ qubits, the tensor product is a vector with $2^n$ elements, one element for each possible value of each qubit.
Each element of the tensor product has a complex weight.
You transform a state by multiplying it by a matrix.
The matrix is invertible.
The transformation doesn't destroy information.
When you measure a state, it collapses into one of the basis states. (aka component states)
You don't need to bring in consciousness etc. The collapse happens because the measurement causes the state to interact with the outside world.
The probability of collapsing into a particular state is the squared magnitude of its complex weight.
For some sets of weights, particularly after a transformation, the combined state cannot be separated into a tensor product of individual qubits. In this case, the individual qubits are entangled.
That is the next part of why quantum computation is powerful.
Entanglement means that if you measure one qubit then what you observe restricts what would be observed when you measure the other qubit.
However that does not let you communicate.
The current limitations are that IBM does only a few qubits and that the operation is noisy.
5 Class 2
Chapter 3 and on. Feel free to read ahead.
6 Homework 1
is online, due Thurs.
7 Videos to watch for Thurs
Watch A Beginner’s Guide to Quantum Computing, 18 min, by Dr. Talia Gershon, IBM Research.