Compressed sensing enhanced by a quantum approximate optimization algorithm

We present a framework to deal with a range of large-scale compressive-sensing problems using a quantum subroutine. We apply a quantum approximate optimization algorithm (QAOA) to support detection in a sparse-signal reconstruction algorithm: matching pursuit. The constrained optimization required in this algorithm is difficult to handle when the size of the problem is large, and the constraints usually given by unstructured patterns also become an issue. Our framework utilizes specially designed structured constraints that are easy to manipulate and reduce the optimization problem to the solution of an Ising model which can be found using Ising solvers. In this study, we simulate QAOA for this purpose and evaluate the performances. We observe that our method can outperform reference classical methods in the same context. Our results explore a promising path for applying quantum computers in the compressive-sensing field.