Quantum Computing 101: Algorithms, Models, Challenges and Applications

From the first idea of a quantum computer in 1980 to today, the quantum computing industry has grown a lot, especially in the last 10 years. Many companies are working on quantum computers.

Understanding quantum computing can be tough for most of us, and a lot of information about it doesn’t explain the important details.

This article intends to clarify everything, and if you read the entire piece, you’ll gain a comprehensive understanding of what quantum computing is, various types of quantum computing, their functioning, algorithms, models, approaches, challenges, and applications.

What are Quantum Computers?

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, While classical computers can only occupy 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 basics of a regular computer are bits, and for a quantum computer, it’s quantum bits or qubits for short. They operate in fundamentally distinct 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.

Superposition

For a useful visualization, you can think of them as an arrow pointing in 3D space. If they point up they are in the 1 state and if they point down, they are in the 0 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 result will still be either 1 or 0, but which one you get depends on a probability that is set by the direction of the arrow.

If the arrow is pointing more upwards, you are more likely to get back a 1 than a 0, and if it is pointing downwards, you are more likely to get a 0 than a 1, 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. 

Entanglement

In classical computers, the bits are entirely independent of 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 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 that 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.

With two qubits, you have a probability distribution spread across four 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. 

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 look like this; this is just a 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. 

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 be revealed 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.

Quantum Algorithms

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 article, so we’ll just focus on the most famous and historically important: Shor’s algorithm.

#1. 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.

This is why in 1994, when Peter Shor published a fast quantum algorithm that could efficiently find the factors of large integers, it caused quite a stir.

This was 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

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 classification is determined by the increasing level of difficulty in solving the problem as it becomes larger. Here, any problem inside the P box is easy for classical computers to solve,  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 circle, 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 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 transforms an unsolvable problem into a solvable one

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.

They would need about many qubits to do so, but so far, the most advanced universal quantum computers have around 433.

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.

#2. Grover’s Algorithm

Another notable example is Grover’s algorithm, which can search unstructured lists of data faster than the best classical algorithm. 

But we should be careful here to make sure we 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.

Simulating a quantum computer on a classical computer becomes exponentially more challenging as the number of qubits being simulated increases.

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 favorite application of quantum computers: quantum simulation.

#3. 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 struggle to simulate quantum systems.

But simulating quantum systems with as few 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 behavior of exotic materials at low temperatures like understanding what makes some materials superconduct or studying 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.

You can learn about quantum chemistry simulation in depth.

Other potential applications of quantum simulation include improving solar panels, improving batteries, and 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 has the potential to significantly expedite processes and result in substantial time and cost savings. 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.

Also Read: How to Learn Quantum Machine Learning

Models of Quantum Computers

Inside the world of quantum computers, there is 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.

The Circuit Model

In the circuit model, they have qubits that work together and special gates that tinker with a few qubits at a time, changing their states without checking. They put these gates in a specific order to create a quantum algorithm. In the end, measure the qubits to get the answer needed.

Adiabatic Quantum Computing

In adiabatic quantum computing, you take advantage of one of the fundamental behaviors in physics, the fact that every system in physics always moves towards the minimum energy state. Adiabatic quantum computing works by framing problems so that the quantum system’s lowest energy state represents the solution.

Quantum Annealing

Quantum annealing 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.

Topological Quantum Computing

In this approach, qubits are built from an entity in physics called a Majorana zero-mode quasi-particle, which is a type of non-abelian anyon. These quasi-particles are predicted to be more stable due to their physical separation from each other.

Challenges in Building

No matter what the approach is, they all face a similar set of obstacles, which we need to take a look at first.

• Decoherence: It’s really hard to control quantum systems because if you have any slight interaction with the outside world, the information starts leaking away. This is called decoherence. Your qubits will be made of physical stuff, and you will need other physical stuff nearby to control and measure them; your qubits are dumb; they’ll entangle with anything they can. You need to design your qubits very carefully to protect them from entangling with the environment.

• Noise: You need to shield your qubits from any kind of noise, such as cosmic rays, radiation, heat energy, or rogue particles. Some amount of decoherence and noise is inevitable in any physical system and is impossible to eliminate completely.

• Scalability: For each qubit, you need to have a bunch of wires to manipulate and measure it. As you add more qubits, the necessary infrastructure grows linearly, posing a significant engineering challenge. Any quantum computer design must find a way to efficiently entangle, control, and measure all these qubits as it scales up.

• Quantum Error Correction: Quantum error correction is an error correction scheme to make fault-tolerant quantum computers by using many entangled qubits together to represent one noise-free qubit. This requires a large number of physical qubits to make one fault-tolerant qubit.

Physical Implementations

There is 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. Here are some of the most widely used and successful approaches:

• Superconducting Quantum Computers: Superconducting qubits are currently the most popular approach. These qubits are 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.

• Quantum Dot Quantum Computers: Qubits are made from electrons or groups of electrons and the two-level system is encoded into the spin or charge of the electrons. These qubits are built from semiconductors like silicon.

• Linear Optical Quantum Computing: Optical quantum computers use photons of light as the qubits and operate on these qubits using optical elements like mirrors, waveplates, and interferometers.

• Trapped Ion Quantum Computers: Charged atoms are used as qubits, and these atoms are ionized, having a missing electron. The two-level state that encodes the qubit is the specific energy levels of the atom, which can be manipulated or measured with microwaves or laser beams.

• Color Center or Nitrogen Vacancy Quantum Computers: These qubits are made from atoms embedded in materials like nitrogen in diamond or silicon carbide. They are created using the nuclear spins of the embedded atoms and are entangled together with electrons.

• Neutral Atoms in Optical Lattices: This approach captures neutral atoms into an optical lattice, which is a crisscrossed arrangement of laser beams. The two-level system for the qubits can be the hyperfine energy level of the atom or excited states.

These are some of the key approaches to building quantum computers, each with its own unique characteristics and challenges. Quantum computing is changing quickly, and picking the right approach is vital for future success.

Applications of Quantum Computers

• Quantum Simulation: Quantum computers have the potential to simulate complex quantum systems, making it possible to study chemical reactions, the behavior of electrons in materials, and various physical parameters. This has applications in improving solar panels, batteries, drug development, aerospace materials, and more.

• Quantum Algorithms: Algorithms like Shor’s Algorithm and Grover’s Algorithm can solve problems that are thought to be intractable for classical computers. These have applications in cryptography, optimizing complex systems, machine learning, and AI.

• Cybersecurity: Quantum computers pose a threat to classical encryption systems. However, they can also contribute to cybersecurity through the development of quantum-resistant encryption schemes. Quantum cryptography, a field related to quantum computing, can enhance security.

• Optimization Problems: Quantum computers can tackle complex optimization problems more efficiently than classical computers. This has applications in various industries, from supply chain management to financial modeling.

• Weather Forecasting and Climate Change: While not fully detailed in the article, quantum computers could potentially improve weather forecasting models and help address climate change-related challenges. This is an area that may benefit from quantum computing in the future.

• Quantum Cryptography: Quantum cryptography boosts data security using quantum principles for safe communication. In a time of growing cyber threats, this is crucial.

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. 

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. This is likely to be the same for quantum computers.

Final Thoughts

Quantum computers are getting better every day, and while we can’t use them in our daily lives yet, they hold potential for practical applications in the future.

In this article, I have discussed various aspects of quantum computers, including their fundamental concepts, such as superposition, entanglement, and interference.

Following that, we explored quantum algorithms, including Shor’s algorithm and Grover’s algorithm. We also delved into quantum complexity theory and the different models of quantum computers.

Subsequently, I addressed the challenges and practical implementation issues associated with quantum computing. Finally, we examined the wide range of potential applications for quantum computers.

Next, You may also read about Quantum Computing FAQs.