Quantum Approximate Optimization for Hard Problems in Linear Algebra

Understand

The Quantum Approximate Optimization Algorithm (QAOA) by Farhi et al.

• is a quantum computational framework for solving quantum or classical optimization tasks.
• Here, we explore using QAOA for Binary Linear Least Squares (BLLS); a problem that can serve as a building block of several other hard problems in linear algebra, such as the Non-negative Binary Matrix Factorization (NBMF) and other variants of the Non-negative Matrix Factorization (NMF) problem.
• Most of the previous efforts in quantum computing for solving these problems were done using the quantum annealing paradigm.