Quantum + NP-Complete = No problem
We haven’t been able to solve NP-Complete problems since the 1950s. And if solved, some of these problems can change the world.
What is an NP-Complete problem?
NP-Complete problems are a class of complexity problems that currently have no time-efficient algorithm.
Here are some real-world examples:
Let’s save lives.
In gene analysis, genes are clustered by their similar reactions to certain conditions. When a cluster of connected genes are found, we can then use this to gain major insights about specific diseases and conduct drug targeting.
Efficient Routes for Transportation Will Benefit the Environment
The Travelling Salesman problem asks to find the most efficient route to travel from one destination to another within a city while visiting various destinations on the route. If we solve this problem, we can exponentially decrease the amount of time and resources spent in transportation for companies like FedX and UPS. The environment would love this too; transportation currently produces 26% of GHG in our atmosphere. This percent would drop exponentially.
These are both NP-Complete problems. Clearly, if we can find a solution to these problems, they will solve many of humanities’ problems. Not to mention that these are only two; there are countless more problems that make major impact when solved.
Now here is the interesting part:
If we can find an efficient algorithm for an NP-Complete problem, an efficient algorithm can be found for all such problems.
In other words:
- We find an efficient algorithm to solve one NP-Complete problem
- We use that algorithm to solve the above NP-Complete problems among others
- *boom* we solve many of the world’s problems
Of course, doing so is easier said than done. ‘
While thinking about potential solutions, I decided to look at a different approaches to computing that may be able to solve NP-Complete problems.
The Quantum Realm: There’s a quantum computing algorithm that can solve specific NP-Complete problems.
Grover’s Algorithm
Grover’s algorithm is a quantum algorithm that is used to search through unstructured data sets.
Why is this algorithm special?
It provides a quadratic speedup.
Let’s say we are looking for “4” in a data set of n=10²⁰ numbers. A classical algorithm would use O(10²⁰) [O(n)] operations. But Grover’s algorithm would use O( √10²⁰) [O(√10^n)] operations.
If you’re interested, here is a deeper dive into how Grover’s algorithm works
Some search problems can be shown as a function, f, and x as an input.
f(x) = 1 (if x is the solution) and f(x) = 0 (if x is not the solution to the search problem).
When applying the oracle (a black box operation), qubits are first put in a uniform superposition using the Hadamard gate.
The oracle is applied to find the solution to the search problem. If we have a search problem with N problems and M solutions, the oracle is applied O( √N/M) times to find the solution to such problem.
Grover’s algorithm can be implemented on a specific class of NP-Complete problems called 3SAT problems:
Before we look at 3SAT, let’s understand what SAT is:
A SAT or satisfiability problem looks for a set of variables that make a boolean formula true. Let’s have a closer look:
A 3SAT problem is slightly different. 3SAT problems require 3 variables in each clause. For example, the problem may look like this: (x1∨x2∨x3)∧(x4∨x5∨x6)
If Grover’s algorithm can solve 3SAT problems, we may be able to solve other NP-Complete problems. And many of these NP-Complete problems can solve some of the world’s biggest problems.
I recently implemented Grover’s algorithm on a 3SAT problem using IBM’s QISKit and encountered a common problem.
I used the above 3SAT problem.
And I received the above output.
Clearly, the algorithm didn’t work in this instance. The reason? The quantum simulator could not use a sufficient amount of qubits to solve the problem. This is one of the biggest challenges quantum computers face today. They don’t have enough error-corrected qubits to be applied to substantial problems.
Nevertheless, IBM is currently working on optimizing Grover’s algorithm so that less qubits are required to run the algorithm on problems.
Although we can’t solve NP-Complete problems right now, with the advancement of quantum computers and quantum algorithms, it can become a reality in the near future. Solving NP-Complete problems means that we’ll be able to discover more about our genes to combat diseases, optimize transport, energy and more. The possibilities are endless.
