On some features of Quadratic Unconstrained Binary Optimization with random coefficients
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917708570820608 |
|---|---|
| author | Isopi, Marco Scoppola, Benedetto Troiani, Alessio |
| author_facet | Isopi, Marco Scoppola, Benedetto Troiani, Alessio |
| contents | Quadratic Unconstrained Binary Optimization (QUBO or UBQP) is concerned with
maximizing/minimizing the quadratic form
$H(J, η) = W \sum_{i,j} J_{i,j} η_{i} η_{j}$ with $J$ a matrix of coefficients,
$η\in \{0, 1\}^N$ and $W$ a normalizing constant.
In the statistical mechanics literature, QUBO is a lattice gas counterpart to the (generalized) Sherrington--Kirkpatrick spin glass model.
Finding the optima of $H$ is an NP-hard problem.
Several problems in combinatorial optimization and data analysis can be mapped to QUBO in a straightforward manner.
In the combinatorial optimization literature, random instances of QUBO are often used to test the effectiveness of heuristic algorithms.
Here we consider QUBO with random independent coefficients and show that if
the $J_{i,j}$'s have zero mean and finite variance then, after proper normalization,
the minimum and
maximum \emph{per particle} of $H$ do not depend on the details of the distribution
of the couplings and are concentrated around their expected values.
Further, with the help of numerical simulations, we study the
minimum and maximum of the objective function and provide some insight
into the structure of the minimizer and the maximizer of $H$.
We argue that also this structure is rather robust.
Our findings hold also in the diluted case where each of the $J_{i,j}$'s is allowed
to be zero with probability going to $1$ as $N \to \infty$ in a suitable way. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_17059 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On some features of Quadratic Unconstrained Binary Optimization with random coefficients Isopi, Marco Scoppola, Benedetto Troiani, Alessio Probability Statistical Mechanics 60F05, 82B44, 90C20 Quadratic Unconstrained Binary Optimization (QUBO or UBQP) is concerned with maximizing/minimizing the quadratic form $H(J, η) = W \sum_{i,j} J_{i,j} η_{i} η_{j}$ with $J$ a matrix of coefficients, $η\in \{0, 1\}^N$ and $W$ a normalizing constant. In the statistical mechanics literature, QUBO is a lattice gas counterpart to the (generalized) Sherrington--Kirkpatrick spin glass model. Finding the optima of $H$ is an NP-hard problem. Several problems in combinatorial optimization and data analysis can be mapped to QUBO in a straightforward manner. In the combinatorial optimization literature, random instances of QUBO are often used to test the effectiveness of heuristic algorithms. Here we consider QUBO with random independent coefficients and show that if the $J_{i,j}$'s have zero mean and finite variance then, after proper normalization, the minimum and maximum \emph{per particle} of $H$ do not depend on the details of the distribution of the couplings and are concentrated around their expected values. Further, with the help of numerical simulations, we study the minimum and maximum of the objective function and provide some insight into the structure of the minimizer and the maximizer of $H$. We argue that also this structure is rather robust. Our findings hold also in the diluted case where each of the $J_{i,j}$'s is allowed to be zero with probability going to $1$ as $N \to \infty$ in a suitable way. |
| title | On some features of Quadratic Unconstrained Binary Optimization with random coefficients |
| topic | Probability Statistical Mechanics 60F05, 82B44, 90C20 |
| url | https://arxiv.org/abs/2402.17059 |