Something exciting is happening in the world of computing. And the excitement couldn’t come soon enough for those grieving the demise of Moore’s Law. Gordon Moore, one of the founders of Intel, observed that the number of transistors in dense integrated circuit doubles every two years.
For the last fifty years, advancements in computing have been about making transistors smaller. Let me take a step back. Most of us know that the computers speak a different language. The language of bits (i.e. 0 and 1). But if you open up a computer and sort through its innards, you don’t find any 1’s and 0’s lying around. You see chips, and these chips contain transistors. Transistors either allow electrons to pass or not depending upon the voltage that is applied. A bit can be built from an arrangement of a couple or more transistors. Eight bits make a byte. And many, many bytes make up the internet, apps, software, these words you are reading, etc.
Back to Moore’s Law. Its dying because it’s getting harder to make transistors any smaller. They are getting so small now that engineers have to worry about quantum tunneling effects1Click for description. In this effect electrons are essentially and probabilistically walking through walls, making a mockery of our efforts to control their flow that is critical to the operation of a transistor!
Intuitively, the laws of reality should be the same whether something is big or small. Whether we are holding a grain of sand or an apple, gravity pulls both down when we release them. However, our intuition about reality is based on our experiences with matter containing trillions and trillions of atoms. A single grain of sand has 1020 molecules. If each molecule was a human, a grain of sand would represent enough humans to populate 14 billion Earths! But reality does not care about our intuition, and the world of the extremely tiny, the quantum world, is bizarre!
In an Aikido-like move, we have figured out how to take the very thing that is killing rapid advancement in transistor-based computing and turn it into a significant advantage. We can utilize the bizarre concepts of Quantum superposition and entanglement to solve certain problems that are intractable for our current computers. Such problems include optimization (e.g. traveling salesman problem), simulating molecular interactions in chemistry, the N-body problem in physics, etc.
Computational tasks can be classified as “P” and “NP”. “P” (or Polynomial-time) tasks are those that current computers can solve quickly 2The distinction between P and NP represents one the most important and unsolved problems in computer science. Read more here. “NP” (or Non-Polynomial time) tasks cannot be solved by current machines but they can quickly verify a solution to the problem. A quantum computer holds the promise to quickly solve “NP” problems. One example is being able to break encryption protocols quickly. Given how many passwords each of us has for everything from our bank accounts to Netflix, needless to say that it would be a very bad thing (but could also lead to good things, like impenetrably secure data transmission)!3More on the possible effects of quantum computing on encryption here
A quantum computer excels at the exponential scaling of a computational problem. As long as a computational task can be encoded onto a quantum environment, we can observe the probabilistic results of that environment in order to get solutions to that problem.
This is a very different approach to solving a computational task. Our current method maps a task into a sequential operation of transistors comparing 0’s and 1’s in order to get to a final discrete state (i.e. one correct answer). For some problems, our best bet today is to search through the entire solution-space bit by bit4pun intended! in order to find the right answer.
In a quantum computer you can encode the solution-space of the problem onto the massive number of states (or phase-space) accessible to a quantum system. A particle can act like a wave. When waves are in phase their amplitude increases and vice versa. We can utilize the principles of interference in order to amplify the correct answer and suppress all the incorrect ones. Nature itself reveals the solution to us.
Two quantum mechanical characteristics are particularly important to quantum computers:
The basic unit of a quantum computer is a quantum-bit, q-bit or qubit. Whereas a bit can be 0 or 1, a qubit can be in a superposed state of 0 or 1. In fact, it is 0 and 1. A way to think about it is to imagine a sphere. Whereas a traditional bit is either the north pole (=1) or the south pole (=0), a qubit is anywhere on a longitude connecting the north and the south pole. When we encode information on the qubit, we give it a phase which is like a latitude rotating it from the longitude connecting the north and south pole.
Adding more transistors to our current machines leads to a linear increase in compute as it can only deal with one bit at a time. In a quantum computer the computational ability scales exponentially. Since qbits can be in a superposition of 1 and 0, n qbits can represent 2n states. Ten qbits can represent 1024 states. One hundred qbits represent 1.26 x 1030 states!
The other important concept in quantum computing is entanglement. If we actually live in a simulation5See this video of Elon Musk laying out the argument for why we might be living in a simulation: video, one evidence of it might be the weird glitch embedded in our reality called entanglement! Einstein called it a “spooky action at a distance”. The reason it is so terrifying is that we know that there is a cosmic speed limit, just like we know there is this thing called gravity. Nothing can travel faster than the speed of light. And yet, if two particles are entangled, they seemingly are able to communicate regardless of the distance between them. We can have one particle in the Milky Way and the other in the Andromeda galaxy (2.5 million light years away!). If we measure the Milky Way particle to have one state, the Andromeda one instantly acquires the opposite state. It is as if they instantly exchange information between them ignoring the cosmic speed limit. Do we actually know what we thought we knew?
A quantum computer is able to use the principle of entanglement by creating superpositions such that if we measure one “particle” to have state 1, the other is instantly in state 0.
Entanglement is one of those amazing mysteries in physics, and the following is a really good (new) documentary on it:
But we can do more than just see a documentary. We can demonstrate entanglement on an actual real-life quantum computer! See the video below that I recorded demonstrating entanglement on an IBM quantum computer6See this video for additional info.
Quantum computing is in its infancy right now. The technology is very hard to do and the usefulness is rather academic right now. However, things could change very quickly. I suspect that this technology will have major consequences for things like secure communications and artificial intelligence. Perhaps the reason we have not yet build a sentient machine is that our brains are made of physical stuff, and may be accessing the world of the quantum. We might have strong Ai7Sentient and general intelligence machines rather than specific task-oriented Ai we have today if we built it using a quantum computer. At any rate – definitely one of the technologies to watch for the future!
A good explanation of quantum computing: link