Derivation of QUBO formulations for sparse estimation
This work provides a method for sparse estimation in quantum annealing, but it is incremental as it extends existing derivation techniques to the l1-norm.
The authors tackled the problem of sparse estimation by deriving a quadratic unconstrained binary optimization (QUBO) formulation for the l1-norm, enabling its use with Ising-type annealing methods like quantum annealing, and they simplified it by removing a redundant variable.
We propose a quadratic unconstrained binary optimization (QUBO) formulation of the l1-norm, which enables us to perform sparse estimation of Ising-type annealing methods such as quantum annealing. The QUBO formulation is derived using the Legendre transformation and the Wolfe theorem, which have recently been employed to derive the QUBO formulations of ReLU-type functions. It is shown that a simple application of the derivation method to the l1-norm case results in a redundant variable. Finally a simplified QUBO formulation is obtained by removing the redundant variable.