I have taught a course on quantum computing a few times, mostly to CS students who have no background in quantum mechanics. The way I proceed is to
* First introduce classical reversible computation. I model it using linear algebra, meaning classical n-bit states are 2^n length binary vectors, and the gates are 2^n x 2^n binary matrices acting on theses states. Exponential, yes, but a faithful model. The critical feature here is that you already need the tensor product structure. Rather than some unique feature of quantum.
* Introduce probabilistic classical computation. Now the states/vectors have real entries in [0,1] and obey the L1 norm (the critical feature). Similarly, the gate matrices.
* Now, argue that quantum computing just requires the same linear algebriac structure but we (1) work over the complex number field, (2) norm is L2.
The reason I like this development is that it takes at least some of the mystery out of quantum mechanics. It is not a strange model of computation, completely divorced from classical. Just a variant of it, that happens to be the one the universe runs on.
Peter Shor does discuss classical computation in two lectures, but from just the notes it seems detached from the rest of the course.
Unfortunately no. I have some course notes that I was putting together during the last iteration of the course, but they are in no way ready for public release. And while many other introductions draw a connection between classical and quantum, I haven't seen any that follow the same radical development as mine.
Scott Aaronson does follow a similar line of thinking in this Quantum Computing Since Democritus lectures [1]. He talks about the p-norm aspect, but doesn't talk about the tensor product structure. And I think for good reason. The way I teach is good for learning, but it is not how you would ultimately think about the link between classical and quantum computing, once you become an expert. Then you should think in terms of complexity theory or in terms of axiomatic relations between classical and quantum theories or information theory principles etc.
There is also David Mermin's book, which has a section on a similar sort of reasoning. I don't recommend it as a self-learning book because it has no exercises.
An example of a textbook which starts from the discrete, linear-algebra form of QM (using the Stern-Gerlach spin experiment) is "Quantum Mechanics: A Paradigms Approach" by David McIntyre of Oregon State University. It's not quite like what's described here, but much closer to it than the more traditional way of teaching QM (using differential equations).
I'm curious, why L2 norm? Each qubit lives in C^2, does it not? I've only ever seen quantum computing formulated over finite dimensional Hilbert spaces (though to be fair it was only in a math context, no real physics there)
We can't have a why, because the claim that the norm is L2 is axiomatic [1]. However, as the sibling comment notes, we can argue from consistency. Would any other norm give us a sensible theory? Or we can put quantum theory in a larger framework of theories and discuss why the L2 norm makes more sense within that framework. Scott Aaronson discusses some of these idea in his lecture [2].
It's kind of a crappy paper and the explanations are mediocre at best, but it provides a decent survey of the main physical implementations in language that is simple to follow.
Just like a physical bit, qubits are basically an abstraction over an analog world; they can be implemented in any physical medium you can make a quantum measurement with.
Most current implementations are "trapped ion" computers. This is exactly what it sounds like, an ion trapped in an electromagnetic field. However, people are working on many systems, including:
There is a common perspective that the physical world is computation. That doesn't mean that it's a simulation, only that information is being processed in a way that is very analogous to computation, and it is very useful for seeing it as such.
The world we live in is quantum in nature, and so it is very useful to think of the entire universe as a giant quantum computer.
In fact, one of the primary use cases for building a physical quantum computer we can program is the "simulation" of natural quantum systems, though that begins to stretch the word "simulation."
I'm not sure why you're so accusatory in this comment, but if you want to understand this better, I would recommend "Programming the Universe" by Seth Lloyd
On behalf of my fellow English majors, may I just say: What??
I love Hacker News because it exposes me to a great deal of things like this. I intend to do as deep a dive I can muster into the provided lecture notes. But boy howdy, are certain topics I encounter here humbling.
If I were fully honest with myself I would avoid a certain subset of the content on hn. Sometimes I think it only fuels my impostor syndrome.
I am sure there are areas which you know a lot about, which I know nothing about. And conversely for every pair of people in the world.
I spend plenty of my time dealing with my own imposter syndrome, often because there are many people in my own field who know far far more about it than I do. Peter Shor, the OP, for instance. But its fine. You do what enjoy and best at, and find satisfaction in doing it. That is the way to live.
Every new concept requires a mapping to metaphors and/or analogies. And when the mapping is mismatched between learner and author's content, elucidation hangs in the balance. Thus, the expertise of lecturers lies in expertise of public speaking coupled with mapping concepts to the intended audience.
QC and general relativity are daunting topics that don't lend themselves well to short-form, self-paced content. These are topics that need foundational perquisites and subject matter experts to catechize. It would be like hopping out of a helicopter mid K2 without any training or acclimatization and expecting to summit. Start smaller and work your way up one step or idea at a time. :)
Pattern recognition and analogy are my secret weapons, for sure. I'm really only a good engineer because I'm good at organizing and communicating my thoughts. It's the only reason I've made it so far in my career -- definitely not any innate propensity for "hard" cs concepts. I faked it til I made it, and now I'm pretty darn good at it.
I think in my particular case the concepts around quantum ____ are so abstract I'm unable to find anything to liken it to. It certainly doesn't help I lack any substantial background in mathematics.
Hopefully one day I'll get there. Or maybe I'm already there and not there at the same time! Who knows!?
trying to elaborate on the OP a little by avoiding math terminology:
part 1 here is essentially the idea of logic circuits. you can write these down in terms of large vectors of 0s and 1s, and operations transforming them as large matrices -- which is useful because it takes familiar ideas (to a CS student) and casts it using mathematical formalisms that are later required for weird quantum stuff.
this could be unfamiliar if you haven't learned about matrix/vector multiplication. but ultimately it's just a different way of talking about combinations of AND/OR/NOT on truth values.
part 2 just says, go from vectors of 0s and 1s to probabilities between 0 and 1. the "L1 norm" (aka Manhattan or taxicab distance) in this situation just means that all the values together have to sum up to 1, the way probabilities do. this includes part 1 as a special case, and extends it naturally.
part 3 is indeed where the weird quantum stuff comes in. no easy explanation, you do have to get an idea of how complex numbers work. but again, the familiar logic circuits of part 1 are still a special case. the "L2 norm" for real numbers is just the regular straight-line distance -- I can't provide a good intuition for complex numbers though.
I read your first comment and it could’ve easily been mine. Currently a software developer but I started off in journalism.
I love, love, love learning but I feel like I have some… granite wall of impenetrability when it comes to quantum computing. I simply cannot figure it out. I’m a very adept person and a quick learner, but everything about quantum theory just leaves me feeling like a complete idiot.
When it's somewhat irrelevant to focus on the hard things, which are more appealing, I find it's frustrating not being motivated to solve the more pressing, easier issues because they're not "fun"
True, but in some cases , it’s just a case of pedagogical mismatch . May I recommend https://www.scottaaronson.com/democritus/lec9.html
? I have cribbed from this endlessly when explaining quantum computing , and it’s certainly my goto talk for explaining quantum computing.
Here's a brief example paired to some of the nomenclature in the parent post:
Linear algebra are equations that do not have exponential independent variables. For example (a,b,c,d,e) are constants: aw + bx + cy + dz = e. You won't find an x^2, z^3, etc. Everything is of order 1.
"classical n-bit states are 2^n length binary vectors": Binary is 1's and 0's. A binary vector is a list of them where each entry is a particular dimension. 2-bit state vector will have 2^2 entries. <1, 0, 1, 1> is 2-bit state binary vector.
"gates are 2^n x 2^n binary matrices": A matrix is a table of values that map one vector to another vector, i.e. a transformation.
|a b|
|c d|
Is a 2x2 matrix. If the matrix is binary then a,b,c,d can only be the values 0 or 1. A matrix is just a condensed notation of a set of linear equations. Let's make a vec x (aka input) and vec Y (aka output) where subscripts indicate the dimension (entry) of the vector (list): vec x = <x_0, x_1, x_2, ...>, and vec Y = <y_0, y_1, y_2, ...>.
If matrix A is the 2x2 matrix above, then vec x * matrix A = vec y is a set of two linear equations:
a * x_0 + b * x_1 = y_0
c * x_0 + d * x_1 = y_1
The math is pretty easy if it is 1's and 0's everywhere. A 2-state vector and matrix will then be:
<x_0, x_1, x_2, x_3> * |a b c d| = <y_0, y_1, y_2, y_3>
|e f g h|
|i j k l|
|m n o p|
(apologies the matrix is probably not going to render nicely, it is a 4x4). This is just the equations:
a * x_0 + b * x_1 + c * x_2 + d * x_3 = y_0
e * x_0 + f * x_1 + g * x_2 + h * x_3 = y_1
i * x_0 + j * x_1 + k * x_2 + l * x_3 = y_2
m * x_0 + n * x_1 + o * x_2 + p * x_3 = y_3
A "gate" is a chain of transformations that result in some computation. For classic computation that's just binary. Most silicon chips are made of NAND gates: NOT(X AND Y). Most other gates can be created from combinations of NAND gates. For quantum computation this will not be just binary 1 and 0 as the output, hence...
"Introduce probabilistic classical computation: Now the states/vectors have real entries in [0,1] and obey the L1 norm (the critical feature). Similarly, the gate matrices.":
Now the entries in vectors and matrices are not just 0 and 1, but any real value between and including 0 and 1. This is important for statistics because it can represent the likelihood of something happening. 0% to 50% to 100% and everything in between.
The L1 norm turns a vector of numbers into just one number. L1 is particularly easy: just add up the absolute value of all numbers (all numbers are positive here anyways). ||vec x|| = x_0 + x_1 + x_2 + ...
"Now, argue that quantum computing just requires the same linear algebriac structure but we (1) work over the complex number field, (2) norm is L2.":
Now entries in the vectors are complex numbers. Complex numbers are a pair of real numbers that have a different multiplication transformation. Complex numbers have the form z = <z_0, z_1>. Adding complex vec e and vec g is straight forward, add the pairs of components: <e_0 + g_0, e_1 + g_1>. Multiplication of complex vec e * complex vec g is <e_0g_0 - e_1g_1, e_0g_1 + e_1g_0>. This is also just linear algebra.
Complex numbers are these 2 dimensional vectors, but being just "numbers" themselves, they have a short-hand notation: z=x + iy. "i" is not a variable and not a constant. It represents a second dimension to the number. To quickly do the matrix math, any time you have "i * i" replace it with -1 and you will have done the matrix multiplication. For example:
"i" may be some other symbol, like "j" depending on whatever math dialect is being used. Complex numbers are algebraically closed, which basically means if you make an equation out of them, the solutions will also be in the set of complex numbers. This is not the case for real numbers, e.g., the solutions to x^2 +1 = 0 are not real numbers, they are complex numbers. Complex numbers model rotations/spinning/something "periodic" as simple algebra, which is very important for trigonometry and sinusoids, making them a nice tool for a lot of disciplines.
L2 is another measure of vectors. L1 can be thought of as a calculation of a vector's perimeter (add up all the dimensions). L2 is a calculation of distance. L2 is adding up the squares of all dimensions and taking the square root (i.e., Pythagorean's theorem but generalized). Linear algebra, L2 norm, etc. all work out nicely for complex numbers.
"The reason I like this development is that it takes at least some of the mystery out of quantum mechanics. It is not a strange model of computation, completely divorced from classical. Just a variant of it, that happens to be the one the universe runs on."
The above are all classic topics in advanced high school and undergraduate math, and important to ~every discipline of engineering. Linear algebra, real numbers, complex numbers, statistics, measurements (L1, L2), etc. all have really nice geometric properties that can improve understanding, which I can't do justice here.
The other important part to remember is that all these ideas took hundreds of years to discover and be refined. Highly recommend diving into them though because they are a lot of fun. They should be pretty accessible from online texts and videos.
Cheers
edit: I can't believe how shitty the formatting options are on HN.
Thank you for this. I skimmed it while on a call, and this seems like a really good breakdown. I look forward to absorbing it with my full attention later.
To download all of the pdfs into the current directory:
wget -r -np -nd -l 1 -A pdf https://math.mit.edu/~shor/435-LN/
(There might be more elegant ways, but this does the job.)
-r, --recursive specify recursive download.
-np, --no-parent don't ascend to the parent directory.
-l, --level=NUMBER maximum recursion depth (inf or 0 for infinite).
-A, --accept=LIST comma-separated list of accepted extensions.
-nd, --no-directories Do not create a hierarchy of directories
Quantum Computing made sense to me for the first time, when I came across Umesh Vazirani's MOOC on Coursera. It is not there anymore. It can be found on YouTube.
When learning classical computing, I have done the following things that gave me a deeper understanding of how things work.
1. Learned logic gates and built(in simulators) small circuits which can do addition/multiplication.
2. Used a 8085 board to write assembly programs for search/sort etc.
3. Learnt C programming and Operating systems(primarily Linux)
4. Learnt higher level programming languages and paradigms(OOP, compilation, etc).
What set of courses/topics would lead to a similar level of understanding in the quantum domain? I have learnt about the quantum gates, but I do not have to context to understand how they fit in the larger picture.
You can wing it in classical domain by tinkering and reading source code aided with just school level algebra but it does not translate to quantum algorithms really. They will remain impenetrable until you invest into mastering mathematical concepts behind it, so most of the courses you need would be intermediate level math. Linear algebra, calculus, probability theory, some bits of number theory…
Quantum gates/circuits are everything - unlike classical computing there is no abstraction built on top. The circuits are built and configured in a classical computer and then the configuration is loaded into the quantum computer.
Why not try playing around with some quantum circuits via qiskit, you can actually run them on a real quantum computer for a few cents with Amazon braket.
I have not reviewed these, but this course used to be co-taught by Peter Shor and Seth Lloyd.
Peter Shor was smarter, but a bad teacher.
Seth Lloyd was a much better teacher.
Together, the two made a good team. There's an obsession with finding the most famous person to teach, but on the whole, I'd pick Seth's lecture notes over Peter's any day.
These courses are usually taught by CS departments assuming a CS background. Anyone aware of corresponding courses for people with a physics background?
This one from Dan Boneh at Stanford is a good intro to cryptography (you can see that it's old as "crypto" (in the URL) was the abbreviation for cryptography still back then...)
* First introduce classical reversible computation. I model it using linear algebra, meaning classical n-bit states are 2^n length binary vectors, and the gates are 2^n x 2^n binary matrices acting on theses states. Exponential, yes, but a faithful model. The critical feature here is that you already need the tensor product structure. Rather than some unique feature of quantum.
* Introduce probabilistic classical computation. Now the states/vectors have real entries in [0,1] and obey the L1 norm (the critical feature). Similarly, the gate matrices.
* Now, argue that quantum computing just requires the same linear algebriac structure but we (1) work over the complex number field, (2) norm is L2.
The reason I like this development is that it takes at least some of the mystery out of quantum mechanics. It is not a strange model of computation, completely divorced from classical. Just a variant of it, that happens to be the one the universe runs on.
Peter Shor does discuss classical computation in two lectures, but from just the notes it seems detached from the rest of the course.