Why do we need quantum computing?
The word “quantum” is so intriguing that when combined with the potential of computational power, it sounds downright fascinating. So, why exactly do we need quantum computing?
Half a century ago, Gordon Moore observed that the density of transistors on a given area of silicon inside would double about every two years. Moore’s law implied that computing would increase in power, and decrease in cost, at an exponential pace and it has done so over the past few decades. To increase the power of Microprocessors, they have had to be made as small as possible, and there are two primary reasons for this. First, microprocessors process information faster when the density of transistors that are inside them is higher. This is because electricity takes time to travel and large microprocessors will be slower because electricity has a longer distance to travel (even it that is only a few nanometers). Second, microprocessors use lesser power when the transistors are placed closer. When transistors are further apart the resistance in the circuits that connect them waste electricity and generate heat, making them less efficient.
Microprocessor technology has evolved at a phenomenal rate since the onset of the computer revolution, and today’s microprocessors can incorporate circuits that are just 14 nanometers (one billionth of a metre) in size. However, looming over this relentless miniaturization of the metal-oxide-semiconductor field-effect transistor (MOSFET) are the laws of physics, one, in particular, is a phenomenon known as quantum tunnelling.
As more and more transistors are squeezed onto microprocessors, the distances between transistor regions decrease. That distance is around 14 nanometers currently, however, scientists believe it can be reduced further to somewhere between 1 and 4 nanometres. If chip makers attempt to reduce the distance even further, electrons will start to ‘tunnel’ through electronic barriers. When electrons tunnel through barriers, quantum tunnelling is said to occur making microprocessors chronically unreliable. The unreliability occurs because transistor that should technically be in the “off,” state appears to flip to the ‘on’ state when electrons that enable the flow of current tunnel through electronic barriers.
Faster computer requires smaller microprocessors and therefore if we are going to be able to meet the ever-increasing demand for more powerful and faster computers, we are going to have to find a replacement for the MOSFET.
We can’t stop electrons from tunnelling through thin barriers. However, we might be able to design more powerful computers by using quantum mechanics to our advantage. It is also envisaged that Quantum computers will be able to solve certain types of problems that traditional computers cannot solve in reasonable polynomial time – Intractable problems. Algorithms exist for such intractable problems; good examples are Grover’s algorithm for searching an unstructured database or the Shor’s algorithm for factoring large numbers. However, even the fastest traditional computers cannot execute these algorithms, at least not in a timeframe that’s practical.
Quantum computing is a field of research that aims to build computers that do not depend on traditional microprocessors for their computation power and are able to solve intractable problems by exploit quantum characteristics such as superposition and entanglement.
What are quantum computers?
Quantum computing is unlike traditional computing, to understand how it works requires thinking about things in a non-intuitive way. Quantum computers are based on quantum mechanics, which is a weird world where things behave in unexpected ways. In this world, particles can exist in more than one state at a time. It is this ability that quantum computers leverage. In quantum computing, operations use what’s called the quantum state, encoded via what’s known as a qubit (or a quantum bit). Unlike a classical bit, a quantum bit can exist in the state of 0 and 1 at the same time, which is called a Superposition State.
In the world of quantum mechanics, particles can be inextricably linked in perfect harmony even when placed at opposite ends of the universe. A phenomenon that Einstein described as “spooky action at a distance.” The strong correlation that exists between quantum particles is what is called Entanglement.
A quantum computer leverages and exploits superposition and entanglement to perform computation. Quantum computing is possible in principle, and there are no know laws of Nature that prevent it. However, reliable quantum computers are incredibly challenging to build.
How do quantum computers work?
Quantum mechanics, that mysterious, confusing discipline, which none of us really understands, but which we know how to use
The best way to understand the power of quantum computers is to compare their approach to solving problems with traditional computers.
Suppose three classmates Andy, Becky and Charlie are heading to town and there are two cars at their disposal. However, all is not well between the three people. Andy and Becky are friends. but they do not like Charlie’s company. Your task is to maximize the number of friendly pairs in a car. For a human, this is easy to work out. The solution will be to send Charlie in a separate car. Easy right? Now think about how we would solve this using a traditional computer.
Lets being by labelling the cars C0 and C1 and use three bits to manage the assignment of people to cars. As an example, 001 would represent that Andy and Becky are in C0 (i.e. Car 0) and Charlie is in C1 (i.e. Car 1). Similarly, 101 would imply Andy and Charlie are in C1 and Becky is in C0. There are two choices for each person, therefore, there are 2 x 2 x 2 = 8 ways to allocate the three people to two cars.
A list of all possible configurations is on the right. Using 3 bits, we are able to represent any one of the eight possible combinations of allocating three people to two cars.
Remember our task is to maximize the number of friendly pairs in a car. To programme that, we will use the following simple formula to compute a score for each allocation of people to cars.
Score of a given allocation = (# friend pairs sharing the same car) – (# enemy pairs sharing the same car)
As an example, let’s suppose that Andy, Becky, and Charlie all get into C1. With three bits, this scenario can be expressed as 111. In this scenario, there is only one friend pair sharing the same car, i.e. Andy and Becky. However, two enemy pairs are sharing the same car, i.e. Andy and Charlie, and Becky and Charlie. Applying the above formula to this scenario gives us a score of -1 (1-2=-1).
With a traditional computer, to find the best allocation of people to cars the computer programme will have to go through all eight configurations to identify ones with the highest score. The image to the right highlights in red the two configurations amongst the eight that achieving a high score of 1 (i.e. 001 and 110)
The difficulty in solving this problem increases exponentially as the number of people increases. For four people there will be 16 possible allocations. For 30 people there will be 1073741824 possible allocations. For 100 people there will be one million million million million million – A problem that is impossible for today’s computer to solve.
In the example above a traditional computer used 3 bits to represent one of the potential eight solutions at any given time. In comparison, a quantum computer will use three quantum bits (qubits). However, unlike a traditional computer, a qubit can represent all eight allocations of people to cars at the same time. That is possible because quantum computing is based on quantum mechanics where a particle can exist in more than one state at a time. A quantum computer leverages and exploits superposition and entanglement to perform computation and is, therefore, able to tackle problems that traditional computer are unable to . The speed at which Quantum computers solves the above problem is not dependent on the number of people or their allocation to cars. A quantum computer does not need to trawl through each possible allocation of people to cars one at a time. Whether there are three, four, hundred, or a million people, the time taken to solve the problem will remain the same. Quantum computing is not just about solving problems faster; they let us do things that are currently impossible with traditional computers (the so-called Intractable Problems).
How good are today’s quantum computers?
Quantum computers are exceedingly difficult to design, build and program. Unlike traditional computers, quantum computers are error-prone. Qubits are inherently unstable and fragile. Today’s qubits are made from sensitive substances such as individual atoms, electrons trapped in silicon (quantum dots). An area of research called quantum error correction is underway to address the error-prone nature of quantum computers. One potential approach is to combine several qubits to form one more reliable qubit. Another challenge that scientist have is to counter the natural tendency of quantum things to lose their quantumness (decoherence).
Quantum computer if they work as intended could transform weather prediction, artificial intelligence, traffic management, cybersecurity, molecular modelling and many more. Quantum computing could change the world – but we are not there yet.
2 comments
This was a great intro to Quantum computing.
Thank you for putting together this well structured overview.