Quantum Computing Explained
Recently, I was randomly researching about quantum computing as we all do at some point during our day out of boredom. After two weeks of research, I decided to write this article in order to get some credit out of it.
First of all, if you don’t have some understanding of primary computer science terms like bits, logical operations and algorithms; this article may not be your cup of tea. Do not get discouraged though, this post will not be computation-heavy and I tried to keep things as simple as possible.
Secondly and more importantly, this post is heavily based on quantum theory. The first part of the article is dedicated to explaining quantum terms because it is impossible to understand quantum computing without understanding how quantum mechanics work in the first place. Naturally, it requires a high-level understanding of classical physics.
This is not an after-school special but I strongly believe that every good software engineer should have a solid background in mathematics and physics. Unfortunately, this is a rare skill even among computer science graduates since writing good code has become the only priority in their careers over time. Our modern education system is designed to nurture good citizens that are successful at fulfilling their daily tasks, instead of inciting curiosity among people to explore new horizons. That being said, I hope I am capable of creating some spark in the minds of at least a few of you.
In order to understand how quantum computers work, we first need to understand how computers work. Computer chips consist of transistors. A transistor is a semiconductor material that can act like an on/off switch. Semiconductor materials have a mixed electrical conductivity value and using the switch a transistor can either allow the electrons to flow through the material or not. This conductivity value corresponds to the bits; 1 means that the switch is on and 0 means that the switch is off.
These are pretty basic stuff and most of you probably skipped through them. There is one more question to answer: How did the idea of quantum computers emerge? The answer is hidden in Moore’s Law. Gordon Moore anticipated that the computation power (the number of transistors) for a fixed-size chip doubles every 18 months in 1965. And it was correct until around 2010.
As transistors get smaller, it becomes harder to make them even smaller. Physical limits restrain us. Today, transistors are smaller than viruses. But the difficulty of shrinking the transistors is not the only problem. As transistor sizes get closer to the size of the atoms, electrons no longer behave and the rules of the physical world no longer follow Newtonian mechanics.
Oh shit, here comes the hard part!
Quantum Physics
The premise of the quantum theory is that subatomic particles do not behave the same way as the entities we observe in our daily lives from the macro perspective. Electrons behave highly unstable by their nature, in terms of our experience of the observable world — just like my crazy ex-girlfriend. There is a famous double-slit experiment to demonstrate the electrons’ movement pattern.
Imagine a block with two parallel slits with a screen behind it as in the image below. If you were to shoot bullets through the slits, you would expect to see two rectangular strips of bullet holes on the screen. However, when scientists did this experiment with an electron beam gun, they observed an interference pattern of waves. The same behaviour can be observed using a light source instead of electrons.
This is called wave-particle duality, classical physics’ inability to fully express the behaviour of the subatomic particles neither as particles nor waves. How does this duality connect to our subject? Well, when you shrink down the transistor size too much, electrons pass through the blocking material by losing some energy, taking advantage of their wave-like behaviour. A process called quantum tunnelling.
Quantum tunnelling sets a natural boundary on the minimum size of the transistors. Therefore, the technology we use today will keep losing its advancement pace and at some point, it will stop. Thus, the search for alternative methods like quantum computers arose. Before we understand quantum computers, we need to understand two more concepts: superposition and quantum entanglement.
Superposition
Superposition links to the wave behaviour of the electrons. What it says is basically an electron can be at more than one position at a time. And you cannot tell where it is until you actually measure it. They have taught you that electrons orbit around the nucleus in high school. In reality, they are not orbiting but everywhere around with different probabilities. Confused? Stop trying to imagine it and start thinking mathematically, otherwise, it doesn’t make any sense.
Electron’s position is actually defined by a wave frequency formula and it can be at different positions at a certain time but the possibility of being at a position is not the same for all possible positions. You can measure the position or the speed (momentum) of the electron but you cannot measure both at the same time because on such tiny scales, interacting with the system for measurement changes the state of the electrons.
When you finally measure the position of the electron, only one of these possible positions is observed randomly. Until you measure it, there is no way of telling where it actually is. Einstein did not like the idea of randomness and said in his famous quote “God does not play dice with the universe.” He thought that there should be some hidden elements that we are missing but this randomness is proven with different experiments. Our double-slit experiment is one such. If we were to shoot a single electron and measure where it ended up, we would have detected it at a single location like a particle. But when we repeat it multiple times and trace all the particles, we end up with a wave pattern, which means that each electron goes through both slits like a wave.
It is natural that this all sounds very weird to you and you are not alone. There is a famous thought experiment proposed by Erwin Schrödinger. Imagine a closed box with a live cat. There is a flask of poison in the box and a radioactive element that can cause the flask to get broken and kill the cat (sadistic bastard). Superposition proposes that until you open the box, there is no way of telling whether the cat is alive or dead and it is both alive and dead at the same time. Then he quit his job to become a biologist.
Quantum Entanglement
If you are asking yourself “what the hell am I reading”, this part is not going to make it any easier. We will only talk about computers after this one, I promise. Quantum entanglement is a weird phenomenon in which particles become connected in a way that a particle’s behaviour cannot be described independently from the state of the others.
Put more simply, when two electrons become entangled, their properties become connected. If one of them goes up, the other one goes down. When one of them spins from left to right, the other one spins from right to left. It means that one electron’s state is dependent on the state of the other one. And this property holds even when they are separated by light years of distance on opposite sides of the universe. They are eternally connected like pirouetting dancers in a cosmic ballet.
Quantum entanglement has been a major problem since it conflicts with well-established principles of physics. If two electrons are in an entangled state, if you measure the state of one of the electrons, you can immediately know the state of the other. Einstein did not like this idea either and called it “spooky action at a distance” (I like this guy). Recent experiments have consistently shown that there is backing evidence for quantum entanglement. For more information, you can refer to Bell Experiment.
Some researchers proposed that it might be possible to transfer information instantly using entanglement, even faster than at light speed. This idea is called superluminal communication and it is a highly speculative subject. There is no backing evidence for the idea though and it is quite unlikely since there is no causality between the entangled particles and all changes occur simultaneously.
If you have persevered this far, we will be strictly talking about quantum computing from this point forward. If you understood this far, the rest of this post should be a breeze.
Quantum Computers
You may wonder do we really need this much information to understand quantum computers. The answer is yes, unfortunately, you do. In this section we will describe how quantum computers work, using what we learned from superposition and entanglement.
Qubits
Qubits are the new bits. A bit can have only two values: 0 or 1. A qubit works differently. It also can either be 0 or 1 but it is in a superposition state between those values until we measure it. There are infinitely many values between 0 and 1 and it is not possible to know at which state it will end up until the actual measurement. So, unlike classical bits, we have to perform a measurement in order to determine the value of a qubit but once we do the measurement, qubits work exactly like classical bits.
You probably wonder how the value of a qubit is measured. Unfortunately, the mathematics defining the measured value of a qubit is far too complex for our practical needs. The value of the qubit is represented by a complex number, known as a wave function, which describes the probability of the qubit being in a particular state. The measurement operation performed by a specific hardware causes the qubit to collapse in one of its eigenstates, either |0> or |1> .
Differently from bit operations, one or more qubits can be entangled with each other. Qubit entanglement is not exactly the same as quantum entanglement, but it is achieved through quantum gates. When they are in an entangled state, the outcomes of the qubits become correlated. This does not mean that each qubit is performing the same calculation, it just means that the result of each calculation is dependent on the state of the other qubits.
The process of performing multiple calculations at once by placing a large number of qubits into an entangled state is called quantum parallelism. It is similar to parallel programming but its effectiveness is vastly increased by the ability to compute all possible values of a function at once.
Qubit entanglement also enables us to perform quantum teleportation, the process of transferring the state of a qubit to others instantly without moving the qubit itself. As explained in the entanglement section, this is achieved by measuring the state of one of the qubits. So next time you see a sci-fi movie with teleportation, throw your cup at the screen screaming we can teleport information, not Benedict Cumberbatch.
Quantum Gates
Quantum Gates are the sparkly orange doors that appear in the Marvel movies. Just kidding, they are the quantum computing versions of logical gates and they are utterly boring. Just like and, or, xor gates manipulate the state of the bits, quantum gates manipulate the state of the qubits. For example, a gate called Pauli-X works like the not gate on classical computing and it flips the state of the cubit from |0> to |1> or vice versa.
Not all gates sound that familiar though. A Hadamard gate, for example, puts the qubit into a superposition state. A SWAP gate, on the other hand, takes two qubits as input and interchanges their states. Or a CNOT gate can be used to create an entanglement state between qubits.
Unlike bits, qubits have more than two possible states, so there are more things that can be done with them. There are more than 10 different types of quantum gates, which we do not need to through one by one to understand the general idea. The important thing to realize is that, without a smart intervention, qubits produce random results due to the randomness of the superposition state. So having more possibilities also complicates the matter of programming by introducing extra challenges.
Performance
Qubits can store more information than classical bits due to using the power of superposition and entanglement. A single qubit can be both |0> and |1> . For a two-qubit system, we can store four bits of information as |00> , |01> , |10> and |11> . So the amount of information that can be represented by n qubits is equal to 2ⁿ.
An example problem that can be solved by quantum computers is searching an unsorted database. Classical computing solves the problem in n/2 steps, where n is the number of entries. A quantum computer can solve the problem in √n. So if you have a table with 1.000.000 entries, classical computing will take 500.000 steps whereas a quantum computer requires only 1000 steps. An algorithmic comparison is meaningless because they don’t use the same computing mechanisms.
A few years ago, Google announced that they have solved a specific computation problem in 200 seconds that would require 10.000 years for the world’s greatest supercomputer to solve. They named this achievement Quantum Supremacy (whatever that means) and it is published in Nature magazine.
I’m getting tired… But I kept the most interesting part to the end.
Algorithms and Applications
If you are anything like me, you should be feeling a little sceptical about quantum computers at this point. Are they really that superior to classical computers? Certainly, there is some hype among the community about quantum computing. Popular opinion is that quantum algorithms work much faster than classical algorithms we use today, by courtesy of quantum parallelism. However, the hype mainly stemmed from a lack of knowledge. The real answer depends on the problem you are trying to solve.
Quantum computing has certain advantages over classical computing in particular areas like parallelization and simulation. But they are not capable of doing everything that our computers do. Moreover, they are very unpractical and fragile since qubits have a tendency to interact with the environment and get corrupted. It is not possible to use them for our practical needs for the time being.
Let’s see some of the possible application areas for quantum computers before wrapping this up.
Random Number Generation
We have random number generation in classical computing, but it is not truly a random number generation. They are generated by algorithms that appear random but in reality, the values you acquire are calculated according to a formula using a predetermined seed. If you know the seed, you can calculate all the values in the series. If you want to learn more about random number generation, you can read my previous post using the link.
What about in real life? Imagine you are tossing a coin. We say that whether we get heads or tails is random, but is it really random? If we were able to calculate all the inputs to the system from the force applied by the coin-tossing finger to the angle of the throw, from the speed of the wind to the distance to the ground, we could calculate exactly what will be the result of the coin. This is called chaos theory or the infamous Butterfly Effect and it says that if we could define all the initial conditions of a sensitive system, we could know exactly what will happen. Nature is deterministic in the terms of classical physics.
A quantum system, on the other hand, can actually generate truly random numbers. This is because of the superposition state of the quantum systems, that we cannot predict its outcome with certainty and once we measure it, the result is completely random. Einstein did not like this.
Search Problems
We have already seen one example of search problems in the performance section when we investigated unsorted database searches. The concept can be applied to a range of related problems to increase the search speed by harnessing the power of quantum parallelization.
NP-Complete Problems
NP-completeness is a far too complex subject to explain the details in here, maybe I will devote another post to it later. Most of the problems we can effectively solve with our computers have polynomial time complexity, like O(n²). Not all problems have a polynomial time complexity. For example, if a problem can be solved in O(n!) — all permutations of something — it means that our deterministic computers cannot solve it for a large n value in a feasible time.
One example of these problems is called Traveling Salesman Problem. In this problem, some seller dude needs to through N cities in order to sell some stuff but he wants to minimize the travelling distance/cost. In order to find the minimum cost, you need to calculate all possible routes or permutations, in which you will end up with N! options. Even for a small value like N=10, you need to consider more than 3 million different routes!
For a problem like the travelling salesman, quantum parallelization can be exploited in order to calculate all possible routes at the same time. This does not mean all problems in NP class can be solved with quantum computers, but it might be possible to find feasible solutions to some of them.
Simulation
Quantum computers can simulate the behaviour of real quantum systems. This capability can be groundbreaking for different areas of science and in my opinion, this will be the main purpose to use quantum computers in the future.
Cryptography
This one is a little speculative but its repercussions can be devastating. Most of our internet communication is based on a public key algorithm called RSA. RSA algorithm relies on the difficulty of prime factorization, meaning that it is practically not possible to factor the product of large prime numbers in a reasonable time.
Currently, our entire internet security depends on a few algorithms like RSA and ECC, that are accepted as unbreakable due to the mathematical difficulty of solving the underlying problems. However, if quantum computers can be used to quickly calculate the primes, it means that the entire systems we have been using the securely communicate may break down. Are you scared yet?
In my opinion, the use of quantum computers will stay restricted to the solution of certain problems and we will never have one in our homes. They might be offered as a cloud service in the future, though. Still, it should be noted that quantum computing technology is still in its infancy phase and it is impossible to know what the future holds.
Before we finish I would like to recommend some extra study material. First of all, this is the first post I have used OpenAI’s ChatGPT in my research instead of Google, which allowed me to find more accurate results more quickly, so you may want to try that. I wrote a short article to explain how I conducted this research using ChatGPT.
You can some of the other resources I have used:
- Quantum Computing for Everyone, written by Chris Bernhardt
- Quantum Computing blogs by IBM, Microsoft, Intel and Amazon
- Professor Andrea Morello’s videos
I can’t believe they are not paying me to do this. I don’t want agitate you but they really should! Anyway, if you actually were able to read this far, kudos. If you have any feedback or interesting insights on the subject, feel free to share and see you later.
