When to use a quantum computer

Quantum computing is weird.

No, I am not referring to the strange phenomena of quantum mechanics that govern the operation of quantum computers.

I am referring to the discrepancies in media coverage. In the popular media, quantum computing is touted as a magic device that will solve all our problems. In contrast, critical literature doubts that quantum computing will ever do anything useful.

If we believed everything the media wrote about quantum computing, it would be like having a personality disorder where you vacillate between jumping for joy and devastation.

I, too, am guilty. I’ve dished up both in my weekly posts, which I’ve been writing for almost two years now. I’ve highlighted all the incredible things that quantum computers could do. But I’ve also clarified the inflated expectations resulting from a severe misunderstanding of quantum computers.

While I try to make the entire subject as accessible as possible by not relying solely on mathematical formulas, I do my best to remain as grounded as possible.

Therefore, In my previous post, I pointed out what quantum computers do:

All quantum computing does is make it possible to implement non-deterministic algorithms.

Of course, this definition does not help without further clarification and interpretation.

So let’s look at what this means and its implications because it is the key to identifying problems we should with a quantum computer.

But before we get into that, let me briefly explain why I emphasized “should” and did not write “could.” The simple reason is that quantum computers can do everything digital computers can do. But quantum computers are costly devices whose few quantum bits (qubits) are susceptible to noise.

IBM’s current QPU (Quantum Processing Unit) Eagle has 127 qubits. So it can do everything a CPU with 127 bits could do. So if we had millions (one megaqubit) or billions (one gigaqubit) of qubits, a quantum computer could do everything a current CPU can.

But even a quantum computer with billions of qubits is slower, more error-prone, and much more expensive than a comparable classical chip. So I would definitely stick with a digital computer…. unless there is a reason to use a quantum computer.

The question is not whether we could use a quantum computer. Instead, the question is whether we should. So why should we even bother with tiny processors, noisy results, and costs?

We should use a quantum computer to solve non-deterministic polynomial (NP) problems. By definition, these are decision problems that a non-deterministic algorithm can solve in polynomial time, but a deterministic one cannot. This sounds like a tautology, but it has meaning.

To understand what this means, we need to talk about complexity theory. This is the theory about how the time or number of steps it takes to solve a problem grows as the size of the problem increases.

Let’s consider two problems. First, the multiplication of two numbers, e.g., “What is three times seven?” Second, the factorization of two numbers, e.g., “What are the prime factors of 21?” Both problems are easy to solve. The reason is that the problem size is tiny.

How about these problems:

• what is 101 times 223?

• What are the prime factors of the 22523?

While you can solve the first problem with pen and paper, you might have difficulty solving the second problem. By the way, these are still small problems, too.

The complexity of multiplying an n-digit number increases by about n2. WE call it a polynomial problem solution. In contrast, the complexity of finding the prime factors of an n-digit number is e^{n^{1/3}}. It means that the effort increases exponentially with the number of digits.

It’s important not to underestimate the difference between polynomial and exponential complexity. While your smartphone multiplies numbers with 800 digits in a few seconds, the factorization of such numbers on a supercomputer takes about 2,000 years.

We consider problems that we can solve in polynomial time tractable and those with exponential growth intractable. For large values of n, problems with exponentially growing complexity become so hard that even the best supercomputer would take far too long to solve them — in some cases, this means millions or even billions of years.

Have you bothered to solve the above tasks? What if I told you that the prime factors of 22523 are 101 and 223?

Whether this solution is correct can be checked in polynomial time since the check is a multiplication. This makes the factorization of numbers a non-deterministic polynomial decision problem.

A decision problem is one that we can answer yes or no. Moreover, this answer must be verifiable by concise proof. A proof is concise if its complexity exhibits polynomial growth.

Moreover, if we can guess its solution, a problem is said to be a non-deterministic polynomial (NP) one. This means that there is no particular rule that we can follow to infer the solution, but if we are lucky, we can still find the correct solution on the first try.

Thus, if a non-deterministic algorithm can solve an NP problem in polynomial time, it means that it makes such a problem tractable.

And the power of quantum computing origins in its ability to implement non-deterministic algorithms. Thus, we could create algorithms for such NP problems.

And that is precisely when we should use a quantum computer. We should use a quantum computer when faced with an NP decision problem that we cannot solve efficiently (i.e., with polynomial complexity) with a classical computer.

Take multiplication, for example. This is a decision problem we can already solve efficiently. Therefore, we should not use a quantum computer, even though we could.

On the other hand, factorization is a decision problem we can’t solve efficiently. Therefore, we should use a quantum computer for it.

What about optimization? Suppose you want to find the shortest possible route between a list of cities. This is a problem that we cannot yet solve efficiently. However, it is not a decision problem because you cannot verify that a solution is the best, even if someone tells you. You will never know if there is a better solution until you consider all possible routes.

But that doesn’t mean quantum computing couldn’t help with optimization. It could be used, for example, to find possible routes in the first place. Of course, sometimes finding a valid route is an NP problem in itself. But once we have a route, we can quickly check if it is right, even if we can’t tell if it is optimal.

We should use a quantum computer to find the routes in this case. A classical optimizer could then make the selection of the best route. This is something we know as variational quantum-classical algorithms.

Apparently, you need profound expertise in the problem domain to tell whether you should use a quantum computer to solve it.

Use this knowledge to identify problems in your domain that you should solve with a quantum computer. It’ll bring you into the pole position.

You're interested in quantum computing and machine learning...

...But you don't know how to get started?