Derivation of QUBO formulations for sparse estimation
arXiv:2001.03715 · doi:10.7566/JPSJ.89.034801
Abstract
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.
arXiv comment5 pages, 2 figures
References in corpus (8)
- Quantum Machine Learning
- Ising formulations of many NP problems
- Quantum Annealing in the Transverse Ising Model
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
- Architectural considerations in the design of a superconducting quantum annealing processor
- Ground State Spin Logic
- Quadratic unconstrained binary optimization formulation for rectified-linear-unit-type functions