Using QAOA to Solve NP-Hard Problems on NISQ Computers

Team: 29

School: Los Alamos High

Area of Science: Computer Science / Mathematics

Quantum computing has the potential to drastically increase the speed at which critical problems can be solved in many fields of research. Some of these problems use quantum algorithms which require fault tolerant qubits, and high qubit number and connectivity. At the moment, the best quantum computers are referred to as Noisy Intermediate-Scale Quantum (NISQ) computers, and have low qubit number and connectivity. Therefore, in order to apply quantum computers to useful applications, quantum algorithms which can be used on cloud accessible NISQ devices must be implemented. In this case, the approximation hybrid quantum-classical optimization algorithm QAOA will be used because it can be implemented on current NISQ computers. QAOA can solve or approximate optimization problems, such as NP-Hard problems, in polynomial time, whereas classical algorithms that solve these problems run in exponential time. Several NP-Hard problems that have relevance for optimization in industry will be tested. Each of these problems can be represented as Hamiltonian formulations, which can then be solved by both classical and quantum algorithms. The problems generated will either be solvable by only classical algorithms, or by both the classical algorithms and QAOA run on NISQ computers. The viability of using NISQ computers to solve industry relevant NP-Hard problems will be investigated using the QAOA algorithm in comparison to classical solvers, as well as a DWave 2000Q device.

Progress to date:
Using the open source software released by Rigetti, IBM, and DWave, code for comparing and running classical solvers and QAOA run on both simulators and quantum devices has been created. All current code can be found at
Running this code involves the installation the beta qvm from Rigetti, and the local QASM simulator from Qiskit (IBM Quantum Experience). Additionally, the full directories from Grove and Pyquil (Rigetti) and Aqua and Qiskit-Terra (IBM) are needed.

Included in this code are QUBO and Ising formulation generators for arbitrary graphs for Max Cut, Max Clique, Max Independent Set, and Min Vertex Cover.

Expected Results:
The Ising and Qubo formulation of Maximum Clique takes the complement of the problem graph. This means sparse NISQ devices can actually solve the Maximum Clique of large graphs, if the noise is not too dampening. Maximum Clique has direct relationships to Maximum Independent Set and Vertex Cover. It remains to be seen how effective QAOA is on NISQ devices.


Team Members:

  Elijah Pelofske

Sponsoring Teacher: NA

Mail the entire Team