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.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:2001.03715Journal of the Physical Society of JapanFeb 27, 20202 citations

Quadratic unconstrained binary optimization formulation for rectified-linear-unit-type functions

Go Sato, Makiko Konoshima, Takuya Ohwa +2 more

We propose a quadratic unconstrained binary optimization (QUBO) formulation of rectified-linear-unit (ReLU) type functions. Different from the q-loss function proposed by Denchev et al. [in Proceedings of the 29th International Conference on Machine Learning, Edinburgh, edited by J. Langford and J. Pineau (Omnipress, Madison, USA, 2012)], a simple discussion based on the Legendre duality is not sufficient to obtain the QUBO formulation of ReLU-type functions. In addition to the Legendre duality, we employ the Wolfe duality, and the QUBO formulation of ReLU type is derived. The QUBO formulation is available in Ising-type annealing methods, including quantum annealing machines.We propose a quadratic unconstrained binary optimization (QUBO) formulation of rectified-linear-unit (ReLU) type functions. Different from the q-loss function proposed by Denchev et al. [in Proceedings of the 29th International Conference on Machine Learning, Edinburgh, edited by J. Langford and J. Pineau (Omnipress, Madison, USA, 2012)], a simple discussion based on the Legendre duality is not sufficient to obtain the QUBO formulation of ReLU-type functions. In addition to the Legendre duality, we employ the Wolfe duality, and the QUBO formulation of ReLU type is derived. The QUBO formulation is available in Ising-type annealing methods, including quantum annealing machines.

arXiv:1811.03829Physical review. EApr 4, 20197 citations

Quantum Advantage in Decision Trees: A Weighted Graph and $L_1$ Norm ApproachQuantum Advantage in Decision Trees: A Weighted Graph and $L_1$ Norm Approach

Sebastian Alberto Grillo, Bernardo Daniel Dávalos, Rodney Fabian Franco Torres +2 more

The analysis of the computational power of single-query quantum algorithms is important because they must extract maximal information from one oracle call, revealing fundamental limits of quantum advantage and enabling optimal, resource-efficient quantum computation. This paper proposes a formulation of single-query quantum decision trees as weighted graphs. This formulation has the advantage that it facilitates the analysis of the $L_1$ spectral norm of the algorithm output. This advantage is based on the fact that a high $L_1$ spectral norm of the output of a quantum decision tree is a necessary condition to outperform its classical counterpart. We propose heuristics for maximizing the $L_{1}$ spectral norm, show how to combine weighted graphs to generate sequences with strictly increasing norm, and present functions exhibiting exponential quantum advantage. Finally, we establish a necessary condition linking single-query quantum advantage to the asymptotic growth of measurement projector dimensions.The analysis of the computational power of single-query quantum algorithms is important because they must extract maximal information from one oracle call, revealing fundamental limits of quantum advantage and enabling optimal, resource-efficient quantum computation. This paper proposes a formulation of single-query quantum decision trees as weighted graphs. This formulation has the advantage that it facilitates the analysis of the $L_1$ spectral norm of the algorithm output. This advantage is based on the fact that a high $L_1$ spectral norm of the output of a quantum decision tree is a necessary condition to outperform its classical counterpart. We propose heuristics for maximizing the $L_{1}$ spectral norm, show how to combine weighted graphs to generate sequences with strictly increasing norm, and present functions exhibiting exponential quantum advantage. Finally, we establish a necessary condition linking single-query quantum advantage to the asymptotic growth of measurement projector dimensions.

quant-pharXiv:2602.04700Feb 5, 20260 citations

A formulation of mask optimization into QUBO model for Ising machines

行秀小平, Yukihide Kohira, 知己松井 +5 more

Nov 1, 20230 citations

Quantum Advantage in Decision Trees: A Weighted Graph and

L_1

Norm Approach

L_1

spectral norm of the algorithm output. This advantage is based on the fact that a high

L_1

spectral norm of the output of a quantum decision tree is a necessary condition to outperform its classical counterpart. We propose heuristics for maximizing the

L_{1}

spectral norm, show how to combine weighted graphs to generate sequences with strictly increasing norm, and present functions exhibiting exponential quantum advantage. Finally, we establish a necessary condition linking single-query quantum advantage to the asymptotic growth of measurement projector dimensions.