Team: 29
School: Los Alamos High
Area of Science: Computer Science and Mathematics
Proposal: Quantum computing has the potential to drastically increase the speed at which critical problems can be solved in many fields. Most of these problems are NP-Complete or NP-Hard, which means that most classical algorithms that solve these problems run in exponential time. However, these problems are very large and solving them efficiently using quantum algorithms implemented on quantum computers requires fault tolerant qubits, with high qubit connectivity and a large number of qubits. 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 hybrid quantum-classical optimization algorithm QAOA will be used because it can be implemented on current NISQ computers. Several NP-Hard and NP-Complete problems that have relevance for optimization in industry will be tested. Each of these problems can be represented as Ising 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. Problem reduction and decomposition will also be tested in order to increase the size of problem which can be solved using current 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 and classical simulators of quantum systems.
Team Members:
Sponsoring Teacher: NA