Team: 29
School: Los Alamos High
Area of Science: Computer Science / Mathematics
Interim:
Abstract:
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 https://github.com/epelofske/quantum_optimization
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.
Sources:
https://arxiv.org/abs/1302.5843
https://arxiv.org/abs/1801.08649
https://www.sciencedirect.com/science/article/pii/S0166218X01003419
https://arxiv.org/abs/1707.03429
https://arxiv.org/abs/1608.03355
https://arxiv.org/abs/1411.4028
https://arxiv.org/abs/1706.02998
Team Members:
Sponsoring Teacher: NA