The Map of Quantum Computing - Quantum Computing Explained

Video is sponsored by Qiskit, more details later in the video.

From the first idea of a quantum computer in 1980 to today, there has been huge growth in the quantum computing industry, especially in the last 10 years. With dozens of companies and startups spending hundreds of millions of dollars in a race to build the world’s best quantum computers.

For most of us, it’s quite hard to get our heads around the world of quantum computing, and a lot of information about it glosses over important details. This video aims to clear all this up, and if you watch the whole thing, you’ll have a very good overview of all the different kinds of quantum computing, how they work, and why so many people are investing in the quantum computing industry. This is the map of quantum computing.

Quantum computers solve problems in a different way to the computers we are familiar with, which, from now on, I’ll be referring to as classical computers. Quantum computers have certain advantages over normal computers for certain problems, which comes from their ability to be in a huge number of states at the same time, whereas classical computers can only be in one state at a time. To understand this, and to understand how quantum computers work, you need to understand three things: superposition, entanglement, and interference.

The building blocks of a classical computer are called bits, and the building blocks of a quantum computer are called quantum bits, or qubits for short, and they work in fundamentally different ways. A classical bit is kind of like a switch that can either be a 0 or a 1, which you are probably already familiar with as binary or binary information. When we measure a bit, we just get back the state that it’s currently in, but we’ll see this isn’t true of qubits.

A qubit is more complicated. For a useful visualization, you can think of them as an arrow pointing in 3D space. If they point up, they are in the 0 state, and if they point down, they are in the 1 state, just like a classical bit, but they also have the option to be in a thing called a superposition state, which is when the arrow points in any other direction. This superposition state is a combination state of 0 and 1. Now, when you measure a qubit, the output it gives will still end up being either a 0 or a 1, but which one you get depends on a probability, which is set by the direction of the arrow. If the arrow is pointing more upwards, you are more likely to get back a 0 than a 1, and if it is pointing downwards, you are more likely to get a 1 than a 0, and if it is exactly on the equator, you’ll get either state with a 50% probability. So that’s the effect of superposition explained, now we’ll move on to entanglement.

In a classical computer, the bits are independent from each other. The state of one bit is not influenced by the state of any of the other bits. But in quantum computers, the qubits can be entangled with each other, which means they become part of one large quantum state together. For an example, let’s look at two qubits, which are each in different superposition states, but aren’t entangled yet. You can see the probabilities next to them, and these probabilities are currently independent of each other. But when we entangle them, we have to throw away those independent probabilities and calculate a probability distribution of all of the possible states we can get out: either 00, 01, 10, or 11. The important point here is, because the qubits are entangled, if you change the direction of the arrow on one qubit, it changes the probability distribution for the whole system, so the qubits are no longer independent of each other; they are all part of the same large state. And this is true no matter how many qubits you have.

You’ll also note that for one qubit, you have a probability distribution over 2 states. For two qubits, you have a probability distribution over 4 states. For three qubits, you have a distribution over 8 states, and this keeps on doubling each time you add another qubit. In general, a quantum computer of n qubits can be in a combination of 2^n states. So I’d say this is the core difference between classical computers and quantum computers. Classical computers can be in any state you want, but can only be in one state at a time, whereas quantum computers can be in a superposition of all of those states at the same time. But you may wonder how being in this superposition state can be useful in a computer. Well, for that, we need the final component: interference.

To explain the effect of interference, we need to go back and look at my picture of a qubit, technically called a Bloch sphere. A qubit doesn’t actually look like this; this is just a really nice way of visualizing the state of a qubit. In reality, the state of a qubit is described by a more abstract entity known as a quantum wavefunction. Wavefunctions are the fundamental mathematical description of everything in quantum mechanics, which I’ve described in more detail in a previous video. When you have many qubits entangled together, all of their wavefunctions are added together into an overall wavefunction describing the state of the quantum computer. This adding together of wavefunctions is the interference, because, just like with say, ripples of water, when we add waves together, they can constructively interfere and add together to make a bigger wave, or destructively interfere to cancel each other out. The overall wavefunction of the quantum computer is what sets the different probabilities of the different states, and by changing the states of different qubits, we can change the probabilities that different states will come out when we measure the quantum computer. Remember that even though the quantum computer can be in a superposition of millions of states at the same time, when we measure it, we only get a single state out. So when you are using a quantum computer to solve a computation problem, you need to use constructive interference to increase the probability of the correct answer, and use destructive interference to decrease the probabilities of the incorrect answers, so that when you measure it, the correct answer will come out.

Now, how you do this is the realm of quantum algorithms, and the whole motivation behind quantum computing is that, theoretically, there are a bunch of problems that you can solve on a quantum computer that are thought to be intractable on classical computers. Let’s take a look at them. There are many quantum algorithms, too many to describe in this video, so we’ll just focus on the most famous and historically important: Shor’s algorithm.

If you have two large numbers and you multiply them together, there is a very fast, efficient, classical algorithm for finding the answer. However, if you start with the answer and ask, what are the original numbers that multiply together to make this number? It is a lot more difficult. This is known as factorization, and these numbers are called factors, and the reason finding them is so hard is because the search space of possible factors is so large. And there is no efficient classical algorithm for finding the factors of large numbers. For this reason, we use this mathematical property for internet encryption: secure websites, emails, and bank accounts. If you know these factors, you can easily decrypt the information, but if you don’t, you’d need to find them first, which is intractable on the world’s most powerful computers. Which is why, in 1994, when Peter Shor published a fast quantum algorithm that can efficiently find the factors of large integers, it caused quite the stir. This is the moment that a lot of people started to take the idea of quantum computing seriously, because it was the first application to a real-world problem with potentially huge real-world security implications.

But when I say a ‘fast’ quantum algorithm, how fast, and how much faster than a classical computer would it be? To answer these questions, we need to take a little detour into the world of quantum complexity theory. Quantum complexity theory is a subfield of the world of computational complexity theory, which deals with the categorization of algorithms, sorting them into bins according to how well they run on computers. The categorization is based on how much harder it is to solve the problem as the problem gets larger. Here, any problem inside the P box is easy to solve with a classical computer, but anything outside it means we don’t have efficient classical algorithms to solve them, and factoring large numbers is one of these. But there is a box, BQP, which is efficient for a quantum computer, but not a classical computer. And these are the problems that quantum computers will be better than classical computers at solving.

As I said, complexity theory looks at how difficult it is to solve a problem as the problem gets larger. So, if you factorize a number with 8 digits, then you add another digit on, how much harder is it to factor the new number compared to the old one? Is it twice as hard? Exponentially harder? And what is the trend as you add more and more digits? This is called its complexity or scaling, and for factorization, it is exponential. Anything with the N in the exponent is exponentially hard. These exponential problems are the problems that really screw you over as the problems get bigger, and in the world of computer science, you can win respect and renown if you find a better algorithm to solve these hardest problems. One example of this was Shor’s algorithm, which took advantage of the special features of quantum computers to create an algorithm that could solve integer factorization with a scaling much better than the best classical algorithm. The best classical algorithm is exponential, whereas Shor’s algorithm is polynomial, which is a huge deal in the world of complexity theory and computer science in general, because it turns an intractable problem into a problem that can be solved.

Solved, that is, if you have a working quantum computer, which is what people are working on building. But you don’t need to worry about the security of your bank account yet, because today’s quantum computers are not able to run Shor’s algorithm on large numbers yet. I’ve estimated they would need about a million qubits to do so, but so far, the most advanced universal quantum computers have around 100. Also, people are working on what’s known as post-quantum encryption schemes, which don’t use integer factorization, and another technology from the world of quantum physics can help here too: a cryptographic scheme known as quantum cryptography.

So that was a look at just one quantum algorithm, but there are many more, each with different levels of speedup. Another notable example is Grover’s algorithm, which can search unstructured lists of data faster than the best classical algorithm. But I should be careful here to make sure I don’t mischaracterize classical computers. They are very versatile devices, and there is nothing to say that someone may find a very clever classical algorithm that could solve the hardest problems like integer factorization more efficiently. People think it is very unlikely, but it is not ruled out. Also, there are problems that we can prove are impossible to solve on classical computers, called non-computable problems, like the halting problem, but these are also impossible to solve on a quantum computer. So computationally, classical computers and quantum computers are equivalent to each other; the differences all come from the algorithms that they can run. You can even simulate a quantum computer on a classical computer and vice versa. But simulating a quantum computer on a classical computer gets exponentially harder to do the more qubits you are trying to simulate. This is because classical computers struggle to simulate quantum systems, but because quantum computers are already quantum systems, they don’t have this problem, which brings me to my favourite application of quantum computers: quantum simulation.

Quantum simulation is simulating things like chemical reactions or how electrons behave in different materials with a computer. Here, quantum computers also have an exponential speedup over classical computers, because classical computers really struggle to simulate quantum systems. Now, I’ve made a whole other video about quantum simulation, which you can watch here, but basically, simulating quantum systems with as few as 30 particles is difficult even on the world’s most powerful supercomputers. We also can’t do this on quantum computers yet, but as they mature, a main goal is to simulate larger and larger quantum systems. These include areas like the behaviour of exotic materials at low temperatures, like understanding what makes some materials superconduct, or study important chemical reactions to improve their efficiency. One example aims to produce fertilizer in a way that emits way less carbon dioxide, as fertilizer production contributes to around 2% of global carbon emissions. Other potential applications of quantum simulation include improving solar panels, improving batteries, developing new drugs, chemicals, or materials for aerospace. In general, quantum simulation would mean that we would be able to rapidly prototype many different materials inside a quantum computer and test all their physical parameters, instead of having to physically make them and test them in a lab, which is a much more laborious and expensive process. This could be a lot faster and save a huge amount of time and money.

It is worth reiterating that these are all potential applications of quantum computers, because we don’t have any quantum computers that can solve real-world problems better than our normal computers yet. But these are the kinds of problems quantum computers would be well suited to. Other applications outside of quantum simulation are optimization problems, machine learning and AI, financial modelling, weather forecasting and climate change, which, I’ll be honest, I don’t really understand how this would work, and finally, cybersecurity, which I think just boils down to Shor’s algorithm, which I already described.

Now, we need to be a little careful about the potential of hype here, as a lot of the claims of what quantum computers will be good for come from people who are actively raising money to build them, and so it makes sense for them to piggyback on topical subjects in their pitches. But my take on it is that historically, when a new technology has come along, the people of the time aren’t the best at being able to tell what it’s going to be used for. For example, the people who invented the first computers never dreamed of the internet and all of the things on it. And this is likely to be the same for quantum computers. But for me, the application that I can really understand the value of is quantum simulation, which is why I've focused on it in this video.

Anyway, so far, I’ve described how quantum computers work and what problems they can solve. But most of what I’ve talked about so far is theoretical. For the rest of the video, I want to focus on reality. How are people actually building quantum computers, and what can they actually do? Now, it’s worth mentioning here that some physicists are skeptical that it will ever be possible to build quantum computers at the scale needed to solve real-world problems, but people working on all of the following certainly don’t agree.

Now, quantum computing is often portrayed as if it is a single thing. But inside the world of quantum computers, there are a large range of approaches to turning different kinds of quantum systems into quantum computers, and there are two layers of nuance I need to talk about. First of all, are the models of quantum computing: the overall approach to manipulating a collection of qubits. And then there’s the physical implementations: the actual quantum objects you build your qubits from, like a superconducting loop, or individual atoms or photons. We’ll start with the models of quantum computing.

It is interesting that there are different models of quantum computing, because this is not something we see with classical computers. Practically all the computers we use today work in the same way. They have a bunch of bits holding the binary information of ones and zeros, and we can do operations on these bits using logical gates, which are basically simple operations that flip a bit, called a NOT gate, or compare bits, like giving you a 1 if two bits are both zero, and a 0 if they are anything else; this is called a NOR gate. Interestingly, you can build a full general-purpose computer from just bits and NOR gates.

In quantum computing, there is a similar model called the gate model, or circuit model, which is the most popular and most understood model of quantum computing. In the circuit model, you have your collection of qubits, which are entangled with each other, and then you have a bunch of gates, which can perform operations on small numbers of these qubits, which change the states of the qubits without measuring them. A quantum algorithm is built from a sequence of gates applied to the qubits in a certain order, and then a measurement at the end, when you get the final state, which hopefully is the answer to the problem you are trying to solve. Simplistically, you can think of these gates as operations on the qubits that rotate the arrows to point in different directions. And these operations change the probability of the final state of each qubit when it is finally measured.

Now, there’s more to this, which I don’t have time to explain here, but if you want to learn more about them and do some quantum computing yourself, I highly recommend the educational website and YouTube channel called Qiskit. They are kindly sponsoring this video, and honestly, they are the best resource for people who want to learn more about quantum computing and get some actual hands-on experience. Basically, Qiskit is a software framework funded by IBM to make it easier for people to get into the world of quantum computing. Everything there is free to access, and the code is all open source. There is an online textbook which teaches you all the basics, so if you don’t have a quantum physics background, that is no problem at all; you can learn everything you need there. Their Qiskit YouTube channel is also full of excellent tutorials and lectures; I’ll link to all of this below. And in terms of quantum algorithms, you can run through examples of quantum circuits using their online tools. And if you want to run your own quantum programs, you can download their open-source SDK and run them on IBM hardware, either on classical simulators of quantum computers, or on actual real-world quantum computers, for free. And the SDK is not only tied to IBM hardware. I used to work at another quantum computing company called D-Wave, and there is an interface to their computers in the SDK as well, if you want to learn about their approach called quantum annealing, and many other companies are available too. Personally, I’ve been using their website to learn gate model quantum computing deeper, because my background is in quantum annealing, and I’m super happy that this educational resource exists, and is free to use, so please check that out if you want to dig deeper. Finally, I just want to state that I’ve had complete editorial control over the content of this video, and my goal is always to be as objective as I can. I just want to make sure you know that Qiskit is funded by IBM, who are building quantum computers, and I used to work for D-Wave, who are making other quantum computers, just for transparency, so you know everyone’s backgrounds.

Right, back to the models of quantum computing. We’ve already looked at the circuit model, but closely related to it is measurement-based or one-way quantum computing, which involves setting up an initial entangled state, and then measuring qubits one by one during the computation, and mathematically, this has been shown to be equivalent to the circuit model.

Now let’s look at the models I’m most familiar with: adiabatic quantum computing and quantum annealing. Adiabatic quantum computing works in a very different way to the circuit model. In adiabatic quantum computing, you are taking advantage of one of the fundamental behaviours in physics: the fact that every system in physics always moves towards the minimum energy state. This is a very general principle, and adiabatic quantum computing takes advantage of this by posing the problems you want solved in such a way so that the minimum energy state of the quantum system is the answer to the problem. You can picture this as an energy landscape, where each point on the landscape is one of the potential outputs of the computer. In adiabatic quantum computing, you start off with a flat landscape, and gradually introduce the energy landscape of your problem, where the answer to your problem is the lowest position on the map. If you do this slowly enough, the quantum computer will always stay in the lowest energy state, so that when you measure it, you are most likely to get the correct answer. I should mention that I’m having to simplify things a bit here to make it easier to understand, but it gives you the right picture of what is going on. In reality, I would need to talk about Hamiltonians and eigenstates, but that’s beyond the scope of this video. Even though adiabatic quantum computing is so different to the circuit model, they have been shown to be mathematically equivalent, and problems can be mapped from one to the other. And they are both something called a universal quantum computing scheme, which means that theoretically, they can simulate any quantum system.

Strongly related to adiabatic quantum computing is quantum annealing, which is not a universal quantum computing scheme, but works on the same principle as adiabatic quantum computing, with the system finding the minimum energy state of an energy landscape that you give it. The reason it is not universal is because it doesn’t have the full degrees of freedom to represent any quantum state, but even with this limitation, it can still be used to solve certain energy landscape problems like optimization problems and simulate certain quantum systems. An example is spin glasses, which are grids of magnetic fields connected to each other. And quantum annealing is a stepping stone to building a universal adiabatic quantum computer.

The last model we are going to look at is called topological quantum computing, which is currently the most theoretical model of quantum computing, because it builds its qubits from an entity in physics called a Majorana zero-mode quasi-particle, which is a type of non-abelian anyon. Which is a bit of a mouthful and obviously quite confusing, but the important term here is quasi-particle. Quasi-particles aren’t fundamental particles like atoms, electrons, or photons; quasi-particles are created from the collected behaviour of many particles together, and end up having particle-like properties despite not being actually real. The clearest example of this is an electron hole: if you have a grid of electrons with a gap in the middle, as the electrons fill in the gap, it looks like this hole moves in the opposite direction. This hole isn’t real; it’s just a hole, but you can treat it like a particle with particle-like properties. In condensed matter physics, there are a large range of different kinds of quasi-particle, and a Majorana zero-mode quasi-particle is an entity that has been theoretically predicted, but there is still significant debate over whether they’ve actually been experimentally observed or not. Now, the reason why physicists are excited about this model is because these quasi-particles are predicted to be a lot more stable than other qubits, because they are made from parts which are physically separated from each other. This is good, because the main source of failure in a quantum computer is noise, which comes from rogue forms of energy creeping into the quantum computer, making the qubits drift away from where they should be and causing errors. But these quasi-particles are special because they are protected from the noise by an energy gap. Basically, what this means is it takes a certain energy to bring the parts of the Majorana particle back together, so any perturbations of noise which have a lower energy than that energy gap is not felt by the quasi-particle. This might have been a bit confusing, but that’s okay; I’m still getting my head around them too, but that was just the best boiled-down description I could come up with.

Okay, so that rounds up the different models of quantum computation, but how do you actually build them? There are a huge range of different physical implementations of quantum computers because there are so many different quantum systems that you could potentially build them from. The requirements to build a qubit is actually fairly simple: all you need is a two-state quantum system, where one state will represent 0 and the other will represent 1. The most obvious example of this is the spin of a particle: the spin can be up or down, but as we shall see, there are many properties of particles we can use. In fact, there are too many for me to list them all, so I’m just going to focus on the implementations that are the most widely used and have been the most successful so far. But no matter what the approach is, they all face a similar set of obstacles, which we need to take a look at first.

In general, it’s really hard to control quantum systems, because if you have got any slight interaction with the outside world, the information starts leaking away. This is called decoherence. You want your qubits to be entangled with each other, but don’t want them to be entangled with anything else. But the trouble is, your qubits will be made of physical stuff, and you will need other physical stuff nearby to control and measure them, and your qubits are dumb; they’ll entangle with anything they can. So, you need to design your qubits very carefully to protect them from entangling with the environment. Then, you need to shield your qubits from any kind of noise: things like cosmic rays, or radiation from things like phone calls, or heat energy, or any other kind of rogue particle. Unfortunately, some amount of decoherence and noise is inevitable in any physical system, and is impossible to eliminate completely. And it gets worse the more qubits you have entangled with each other. This is the big open question still hanging over the whole field of quantum computing: is it ever possible to make a working quantum computer with a large number of qubits, or will decoherence and noise ruin everything? There are strong opinions on both sides, and I guess we won’t know for sure until we actually build them.

One plan to deal with decoherence and noise is quantum error correction. This is an error correction scheme to make fault-tolerant quantum computers by using many entangled qubits together to represent one noise-free qubit. How many you need depends on how good the qubits are, but estimates are in the range of 100 to 1000 physical qubits to make one fault-tolerant qubit. Which is a lot of qubits. And this brings us to another major obstacle: scalability. For each qubit, you need to have a bunch of wires to manipulate and measure it. For a small number of qubits, this is all manageable, but as the number of qubits increases, the amount of extra stuff you need increases linearly, which is a massive engineering problem. So, any quantum computer design needs to somehow be able to entangle all of the qubits, and then control and measure them in a scalable way.

So those are all the problems with building a real quantum computer. Let’s take a look at the different approaches scientists are pursuing.

Superconducting quantum computers are currently the most popular approach. A superconducting qubit is made from superconducting wires with a break in the superconductor called a Josephson junction. The most popular type of superconducting qubit is called a transmon, where the two-level system is encoded in pairs of the electric charge moving across the junction, specifically the frequency at which charges oscillate back and forth across the junction. But there have been other designs that use the magnetic flux in a loop of wire, or the phase across a wire as a two-level system, known as flux qubits or phase qubits.

Physicists have also looked at ways of making qubits out of fundamental entities like atoms, or electrons, or photons.

Next are quantum dot quantum computers or silicon spin quantum computers. Here, I’m using quantum dot quantum computers to collect a range of qubit designs built from semiconductors, things like silicon. Here, the qubits are made from electrons or even groups of electrons, and the two-level system is encoded into the spin or charge of the electrons. On the chip, there’s a small area where the electron is restricted to, is called a quantum dot, and operations on the qubits are performed through voltages on the chip, or microwaves or magnetic fields. As well as silicon, people have also used other semiconducting materials like gallium arsenide, silicon carbide, and also diamond, amongst others, which all have different properties.

Next, we have linear optical quantum computing. Optical quantum computers use photons of light as the qubits, and they operate on these qubits using optical elements like mirrors, waveplates, and interferometers. At scale, this has been accomplished by printing these elements into integrated photonics chips. The two-level system in an optical quantum computer can have different designs, either a superposition of different paths a single photon takes through the chip, or a superposition of different numbers of photons present in a path. And these can be manipulated by applying a voltage to a path.

Now, onto trapped ion quantum computers, which use charged atoms as qubits. These atoms are ionized, having a missing electron, which makes them electrically charged and means they can be levitated and moved about with electromagnetic fields. Here, the two-level state that encodes the qubit are two specific energy levels of the atom, which can be manipulated or measured with microwaves or laser beams.

Next, we have color center or nitrogen vacancy quantum computers, which are similar to trapped ion quantum computers in that the qubits are made from atoms, but instead of being trapped in an electromagnetic field, they are embedded in a gap of the material, like nitrogen embedded in diamond or silicon carbide. There are a few different ways to make these, but typically, the qubits are the nuclear spins of the embedded atoms, and they are entangled together with electrons.

The final approach is called neutral atoms in optical lattices. In this approach, the qubits are atoms, and the design uses cold atom physics, capturing neutral atoms like cesium into an optical lattice, which is a crisscrossed arrangement of laser beams, which form energy wells shaped kind of like an egg box. These atoms are cooled down with lasers to a few millionths of a Kelvin, and there are a number of ways to encode the two-level system the qubit is built from: either the hyperfine energy level of the atom or excited states, and they can also make use of Rydberg atoms. And the atoms can be controlled and entangled with each other with lasers. They can also be used as quantum simulators, as well as quantum computers. In fact, a 10,000-atom quantum simulator has been made, but this doesn’t look like a universal quantum computer.

These are the main approaches I’m going to cover in this video, but it is not an exhaustive list. Some other qubit designs include: electron-on-helium qubit, cavity quantum electrodynamics, magnetic molecule, molecular spins, NMR quantum computers. But these have not been built at the same scale as the other approaches I mentioned in more detail.

So that was the map of quantum computing, and that should give you an excellent overview of the field. As you can see, there are many different approaches to building a quantum computer, and what is so interesting is that it’s not yet clear which approach will win out in the long run. Now, one thing I haven’t covered in this video are the companies and startups and which approach they are using, along with their current best quantum computers, and their roadmaps into the future. But this is what I’ll look at in my next video, so keep your eyes peeled for that. You don’t need to subscribe or anything, but check back in a couple of weeks if you think you’d be interested.

And like all my maps, this map of quantum computing is available to buy at my store dosmaps.com, or to download as a digital image for educational purposes. Links to all of that in the description below. Quick note though, due to logistics, we can only get the map of quantum computing to you after the holidays, but everything else in my store is ready to go. We also have many educational posters and a range of engaging kids books about science called Professor Astro Cat, so if you are looking for some gifts that will help your loved ones learn about science, check that out. Dosmaps.com.

Finally, a massive thank you to all my Patreon supporters. As you can probably tell, I put a huge amount of work into these map videos, and the support on Patreon is invaluable. Thank you. And I’ll see you soon!