Quantum computers
don't exist yet. At least, not physically. But if we peek into the
world of mathematics where they do exist, we can
learn how they might work. Let's break down the mathematics
of a quantum computer in three parts. First, what is a
quantum computer doing? Second, how do we represent
it mathematically? And third, why is quantum
computing so amazing? Part one, what is a
quantum computer doing? The fundamental unit of a
classical computer is a bit. Bits have two states, 0 and 1. Computer take in
a string of bits-- in this example, it's a
string of eight bits-- and use logic gates to switch
some of the bits, like this. OK. That's kind of a crude
description of a computer, but it works for our purposes. Quantum computers use qubits, a
portmanteau of quantum and bit, which is kind of funny because
bit is a portmanteau of binary and digit. Anyway, like a bit, a qubit
can be in state 0 or state 1. And like a classical
computer, the initial program for a quantum computer is just
a string of zeros and ones. But while a quantum
computer is running, it's qubits can also be in
infinitely many superpositions between 0 and 1. When a qubit is in
a superposition, it has some probability of being
in state 0 and some probability of being in state 1. You can think of a superposition
as being a limbo state partway between 0 and 1. But superpositions are fragile. If we look at it or
try to measure it, the qubit will collapse into
a basic state, either 0 or 1. You might know this from
the famous Schrodinger's cat thought experiment. Before opening the
box, the mythic cat is in a superposition
of alive and dead. But when you observe
the cat, it is forced to pick a state,
alive or dead, not both. A quantum computer
is essentially full of Schrodinger's cats. Actually, qubits are
not made of cats. Qubit materials are usually
things like electrons, where spin up
corresponds to state 0 and spin down
corresponds to state 1. But I've digressed. That's the realm of physics. Let's see an example of
a quantum computation with two qubits. There's four basic states,
0 0, 1 0, 0 1, and 1 1. These are the states the two
classical bits can be in. But there are also
infinitely many states formed by superpositions
or combinations of these basic states. Each operation of a
quantum computation is performed by a quantum gate,
which, like a classical gate, changes the state
the qubits are in. Let's start our quantum
computation in 0 0 and then apply a quantum gate. Now the qubits are
in a superposition. There's a 1/2 probability
or 50% chance of being 0 1 and a 1/2 probability
of being 1 0. Ignore the square roots. I'll explain them in a minute. The particular superposition
position it's in is a result of the quantum
gate we chose to apply. Here's one more
quantum gate, changing the state of our computation. At the end of the
quantum computation, we observe or
measure the system. But we can't see these
delicate superpositions. Remember, a superposition
is like a limbo between basic states. When you observe the
computation and look at it from the perspective
of these basic states, it must pick one,
collapsing the wave function and revealing a
single basic state. In this case, it
collapsed to state 0 1. If you run the same
computation repeatedly, the final result will
be 0 1 half the time, it will be 1 0 1/6 of the
time, and 1 1 1/3 of the time. That's what the numbers in
the superposition tell you. The probability that
the superposition will collapse into each basic state. So if you run the
computation 100 times, roughly 50 times it'll
result in the state 0 1, 17 times it will
result in state 1 0, and 33 times it will
result in state 1 1. This allows you to recover the
probabilities and therefore the final superposition
of the computation. This doesn't seem very
efficient with two qubits. But as we'll see later, it
can save you a lot of time with more qubits. So what's the math
behind all this? Part 2, mathematical
representation. A vector can be a
pretty abstract concept in mathematics. But for our purposes,
we'll just say a vector is a list of
numbers and the dimension of that vector is the number
of numbers in the list. Here's an important caveat. For now, to help us get
through the first part of the explanation,
we'll only work with non-negative real numbers. But actual qubits use negative
or even complex numbers. But I'll get back to that later. One qubit is represented as
a two-dimensional vector. This is state 0. And this is state 1. And this is a superposition. Here's the reason
for the square roots. We can visualize the vector
on a circle like this. The horizontal component is the
square root of the probability of being in state 0. And the vertical component
is the square root of the probability
of being in state 1. By the Pythagorean theorem,
the length of the vector is 1. Each point on the unit
circle is a quantum state. A classical computer can
only point up or right, but a quantum computer uses
much more of the circle. What about two qubits? It takes a
four-dimensional vector to represent the
four possible states. Here's the earlier
computation in vector form. The formula for the length
of a two-dimensional vector easily generalizes to the
formula for the length of a four-dimensional vector. So as we said before, all
the quantum state vectors have length 1. The two-dimensional
vectors pointed to a spot on the unit circle
in two-dimensional space. And these
four-dimensional vectors point to a spot
on the unit sphere in four dimensional
space, which makes it awfully hard to visualize. If you have N qubits, there
are two to the N basic states. So the quantum
state is represented by a vector on a sphere in 2
to the N dimensional space. Quantum gates change
the system's state. So they move the state
vector around the sphere. Mathematically,
this is represented with a unitary matrix. Don't worry if you haven't
learned about matrices. For our purpose, a matrix,
specifically a unitary matrix, is a block of numbers
that describes how vectors move around the sphere. When we multiply it by the
starting vector, 1 0 0 0, we get back a new vector, which
represents our second state. Each quantum gate is a
different unitary matrix, changing the vector
which represents the state of the qubits. OK. Here comes the caveat
I mentioned earlier. We just apply this quantum
gate to the state 0 0, represented by this vector,
and got this state as a result. But if we apply the
same gate to state 1 0, represented by this vector,
we get this state as a result. What's funny about that? The superposition has
negative numbers in it, and that's totally OK. To get the probability
that the qubit collapses into each basic state, we
just take the absolute value of the numbers. In fact, not only can
these numbers be negative, they can actually
be complex numbers. So if complex numbers
are familiar to you, notice that the
state of N qubits is actually represented
on a sphere in two to the N complex
dimensions, which has twice the dimensionality
of the sphere in two to the N real dimensions. If you're not familiar with
complex numbers, don't worry. It's not necessary
for this video. OK, aside over. But what's the value of
all this quantum computing? Part 3. Why quantum computing
is so amazing. To answer that, let's look
at this six qubit quantum computation. It's computing using a sphere
in 64-dimensional complex space because 2 to the 6th is 64,
which sounds complicated. But here's the important part. It only took four steps
to find this state. If we wanted to find
the same state using a classical computer, it
could take thousands of steps. Why? The classical
computer can only be in one basic state
at a time, so it has to follow one branch
down the tree at a time. But the quantum computer
processes an entire level of the tree each step,
so this computation only takes four steps. When a quantum computer
is in a superposition, it's processing a bunch of
classical states in parallel. But remember what we
talked about earlier. The quantum
computation will only return one state, which is
determined probabilistically based on its final
superposition. This means we may have to run
the computation a few times to gain the
information required, but it's still way
less than trying to compute it classically. This small example doesn't
really convey how big of a deal it is that quantum computers
take exponentially less time than classical computers. Probably the most famous example
of this is Shor's algorithm. Finding the prime factors
of this huge number could take years with
a classical computer. But with a quantum
computer, it would probably just take a few minutes. Data encryption
and security depend in part on how difficult it
is to factor big numbers. And quantum computers
might ruin that. But for now, your data is safe. No one has actually
built a quantum computer. The problems of physical
implementation are tricky. Like quantum decoherence, which
means that the environment is constantly threatening to
measure and therefore collapse the delicate quantum state
before the equation is solved. But as we just saw, the
math is on solid footing and ready for the future. See you next time on
"Infinite Series." Hi, guys. I wanted to thank everybody
who wrote a program computing Goodstein sequences. We got so many responses. And they were so awesome. There were programs in Python,
Haskell, Mathematica, Java. You guys rock. So what else do people
leave in the comments? Well, Cybernetic asks,
what branch of math does this fall under? That's a good question. So ordinals are usually
studied by set theorists. And independence results, what
things rely on what axioms, what can and cannot prove
by certain axioms, well, that falls under logic. And set theory is
a kind of logic. So it's all sort of wrapped
up in set theory and logic. Eric Saumur
commented that when I asked you guys to try
making your own Goodstein sequence starting
from any number, he started with the number zero. Because like any good
computer scientist, he was trying all of the cases. So he's right. To be more precise,
I probably should have said try any number
bigger than three. All right. It's a little
unrelated to the video, but BobC left a comment
talking about Francis Su's recent speech on
mathematical flourishing. It's really good. I highly recommend it. OK, that's all for now. [MUSIC PLAYING]
You should check Scott Aaroson's blog for more interesting things related to Quantum Computing and read his book, "Quantum Computing Since Democritus", to get an in-depth treatment.
Really good video, except the unitary matrix 7 minutes in isn't actually a unitary matrix.
I'm surprised how good the PBS channels are, I would recommend (almost) any of them whole-heartedly.
This is a nice video, especially when so many people have misconceptions about quantum computers.
Some comments about factoring and encryption:
The hardness of factoring on a classical computer remains mysterious. There are sub-exponential factoring algorithms and it is believed to be easier than NP-hard. Even in a world where P ≠ NP, polynomial-time factoring might still be possible.
The current most popular encryption schemes (like RSA) rely on the hardness of factoring, and quantum computers will break those (Shor's algorithm). However there are many other encryption schemes for which fast quantum algorithms are not known. And we don't know fast quantum algorithms for NP-complete problems. Quantum computers wouldn't necessarily doom all encryption (unlike if P = NP).
Superb video!
That's a pretty awesome youtube channel, subbed
The book "Quantum Computing for Computer Scientists" is really great. Formal enough that it has actual proofs (or sketches) and problems/programming assignments. But not so formal that it takes 3 chapters to prove 2 + 2 = 4.
X-Post referenced from /r/physics by /u/BlazeOrangeDeer
The Mathematics of Quantum Computers | Infinite Series
I am a bot. I delete my negative comments. Contact | Code | FAQ
Finally someone explains superposition correctly.
Not sure why she didn't just say "pure state", it's just as intuitive as "basic state" IMO.