The Mathematics of Quantum Computers | Infinite Series

Video Statistics and Information

Video
Captions Word Cloud
Captions
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]
Info
Channel: PBS Infinite Series
Views: 535,599
Rating: 4.9125533 out of 5
Keywords: math, mathematics, infinite, series, infinite series, pbs, education, quantum, computers, quantum computers, quanta, gates, shor's algorithm, cryptography, qubit, digit, bit, schroedinger's cat, superposition, quantum gate, wave function, vector
Id: IrbJYsep45E
Channel Id: undefined
Length: 12min 35sec (755 seconds)
Published: Thu Feb 16 2017
Reddit Comments

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.

👍︎︎ 14 👤︎︎ u/TheAlgorithmist99 📅︎︎ Feb 16 2017 🗫︎ replies

Really good video, except the unitary matrix 7 minutes in isn't actually a unitary matrix.

👍︎︎ 33 👤︎︎ u/methyboy 📅︎︎ Feb 16 2017 🗫︎ replies

I'm surprised how good the PBS channels are, I would recommend (almost) any of them whole-heartedly.

👍︎︎ 10 👤︎︎ u/242242 📅︎︎ Feb 17 2017 🗫︎ replies

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).

👍︎︎ 7 👤︎︎ u/nerkbot 📅︎︎ Feb 17 2017 🗫︎ replies

Superb video!

👍︎︎ 7 👤︎︎ u/drupol 📅︎︎ Feb 16 2017 🗫︎ replies

That's a pretty awesome youtube channel, subbed

👍︎︎ 4 👤︎︎ u/lift_heavy64 📅︎︎ Feb 17 2017 🗫︎ replies

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.

👍︎︎ 6 👤︎︎ u/groundhogmeat 📅︎︎ Feb 17 2017 🗫︎ replies

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

👍︎︎ 2 👤︎︎ u/OriginalPostSearcher 📅︎︎ Feb 16 2017 🗫︎ replies

Finally someone explains superposition correctly.

Not sure why she didn't just say "pure state", it's just as intuitive as "basic state" IMO.

👍︎︎ 4 👤︎︎ u/matho1 📅︎︎ Feb 17 2017 🗫︎ replies
Related Videos
Note
Please note that this website is currently a work in progress! Lots of interesting data and statistics to come.