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]