Problems that only Quantum Computers can solve

In this article, we will explore how quantum algorithms can solve real-world problems, and how you can get involved in this quantum revolution!

Quantum computers can solve NP-hard problems that classical computers are unable to solve.

Currently, the two most important and notable complexity classes are “P” and “NP.” P represents problems that can be solved in polynomial time by a classical computer. For instance, asking if a number is prime belongs to P. NP problems are problems that cannot be solved in polynomial time by classical computers, but the answers to the problem can be verified quickly with a classical computer. Asking what are the prime factors of a number is an NP problem, as it can be easily verified if x is the prime factor of a number y, however it is very hard for the computer to find out its prime factors. The problem of whether P=NP, whether the two complexity classes are distinct or not is an important dilemma and the one who solves it gets a million dollars!

In 1993, Ethan Bernstein and Umesh Vazirani defined a new complexity class called “bounded-error quantum polynomial time" or BQP. They defined this class to contain decision problems — problems with a yes or no answer — that quantum computers can solve efficiently. They also proved that P is a subset of BQP- that a quantum computer can solve all problems that a classical computer can solve.

They also defined another class of problems called PH or "Polynomial Hierarchy". PH is a generalization of NP. Problems in PH are NP problems that are made more complex by asking questions like is it true "for all" or "does it exist for a particular x".

But can a quantum computer solve problems that classical computers are unable to solve- the NP hard problems? Can we use quantum computing to solve practical problems that industries or companies are facing in real life? Well, you might have heard about how Shor’s algorithm might crack the encryption codes such as RSA and break into your bank account. Shor’s algorithm is able to solve the NP-hard problem of factoring large numbers- check out our implementation of Shor’s algorithm.

Recently, researchers at Chalmers University of Technology have been able to solve a small part of a logistics problem faced by the aviation industry- the Tail Assignment Problem- assigning airplanes to flights with the goal of minimizing connection times between flights and keeping in mind maintenance constraints.

This is a scheduling problem- which scales up exponentially with the number of flights and routes. The team at Chalmers was able to execute their algorithm on a processor with two qubits using the Quantum Approximate Optimization Algorithm or QAOA. The research team also simulated the optimization problem for up to 278 aircraft, however it requires a 25 qubit processor. Read this article to find out more!

So what exactly is the Quantum Approximate Optimization algorithm?

Optimization is searching for an optimal solution in a finite or countably infinite set of potential solutions of a cost function, which is set to be maximized or minimized. In the tail assignment problem, the connection times between flights should be minimized. The problem can also be defined in a way such that the total distance travelled by all airplanes over all air routes should be minimized.

Let us take a simple version of an optimization problem that is easy to visualize. Consider the Travelling Salesman Problem: A salesman wants to travel through all historic sites of the United States to sell souvenirs. The aim is to find the shortest route the salesman should travel such that he visits all the sites and returns back to his starting point.

The image above represents the shortest path to travel through all the historic sites of America. It would take the salesman 50 years to travel this path!

For a small number of cities, we can apply the “brute-force” solution: calculate all the possible routes and pick the shortest. For a large number of cities n, the complexity of this approach is O(n!), which is not efficient

How we would find this path is to use graph theory: each historic site is a vertex, and the edges are drawn between the vertices and represent the journey that the salesman takes. There will be numbers between the edges that represent the distance between the sites. How we minimize the distance is to first convert the problem into a weighted bipartite graph, and minimize the sum of the edges of the graph.

A weighted bipartite graph looks like the one above. We describe it as a hamiltonian cycle: A cycle where the start and end point is the same and uses each vertex of the graph exactly once.

In qiskit, we can map this problem to a Ising Hamiltonian, and minimize the value of the Ising Hamiltonian using the minimum variational Quantum Eigensolver optimizer. We will use the QuadraticProgram() function in Qiskit to make a model of the optimization problem. Check here to find out more.

To find out the shortest path between the vertices, we will be using the tsp module from qiskit.optimization.applications.ising class to solve our problem! Then we will find out what the shortest distance is( which is the objective or the minimum value of our cost function)

from qiskit import Aer
from qiskit.tools.visualization import plot_histogram
from qiskit.circuit.library import TwoLocal
from qiskit.optimization.applications.ising import max_cut, tsp
from qiskit.aqua.algorithms import VQE, NumPyMinimumEigensolver
from qiskit.aqua.components.optimizers import SPSA
from qiskit.aqua import aqua_globals
from qiskit.aqua import QuantumInstance
from qiskit.optimization.applications.ising.common import sample_most_likely
from qiskit.optimization.algorithms import MinimumEigenOptimizer
from qiskit.optimization.problems import QuadraticProgram

qubitOp, offset = tsp.get_operator(ins)
qp = QuadraticProgram()
qp.from_ising(qubitOp, offset, linear=True)
qp.to_docplex().prettyprint()

exact = MinimumEigenOptimizer(NumPyMinimumEigensolver())
result = exact.solve(qp)
print(result)
eigensolver = NumPyMinimumEigensolver(qubitOp)
result = eigensolver.run()

print('energy:', result.eigenvalue.real)
z = tsp.get_tsp_solution(x)
print('solution:', z)
print('solution objective:', tsp.tsp_value(z, ins.w))

Our output will look something like this:

energy: -1600560.0
solution: [1, 2, 3, 0]
solution objective: 236.0

This means that the solution is the path from 1 to 2 to 3 to 0 to 1. The minimum distance when traversing the graph is 236.0.

If we want to make sure this is the correct solution, we can compare with the brute force method(to find the minimum sum of the edges).

We are still in the Noisy Intermediate Quantum Scale Era, and have a long way to go before running  optimization algorithms will be feasible. In the paper, the authors estimate that 420 qubits will be necessary to run the QAOA in a short amount of time and scalable to complex optimization problems. Currently, IBM's supercomputers work on around 50 qubits. However, quantum optimization can be used to solve other problems such as finding the ground state energy of a molecule or optimizing portfolios in finance.

Qiskit can solve a wide range of combinatorial optimization problems. To find out more, check [this](https://qiskit.org/textbook/ch-applications/qaoa.html.).

In this paper, computer scientists have found out a problem that is in BQP but not in PH. This means even if classical computers were able to solve NP problems, quantum computers still have an advantage over them as a problem is found to exist in BQP and not PH- problems that only a quantum computer can solve. This further proves the fact that quantum computers have a processing capacity beyond what a classical computer can achieve.