Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Optical Memory and Neural Networks

Attraction area of minima in quadratic binary optimization

Iakov Karandashev, Boris Kryzhanovsky

Published Apr 1, 2014• 8 citations
Publisher

Abstract

The paper deals with the problem of quadratic functional minimization in the space of binary variables. We analyze the efficiency of the random search procedure used in binary minimization and show that the radius of the attraction area of a minimum directly depends on its depth: the deeper the minimum, the greater its radius of attraction. Thus, the probability of finding a minimum during random search grows exponentially with depth of the minimum.

DOI
10.3103/s1060992x1402009x

Related papers

On some features of quadratic unconstrained binary optimization with random coefficients

Marco Isopi, Benedetto Scoppola, Alessio Troiani

Abstract Quadratic Unconstrained Binary Optimization (QUBO or UBQP) is concerned with maximizing/minimizing the quadratic form $$H(J, \eta ) = W \sum _{i,j} J_{i,j} \eta _{i} \eta _{j}$$ H ( J , η ) = W ∑ i , j J i , j η i η j with J a matrix of coefficients, $$\eta \in \{0, 1\}^N$$ η ∈ { 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}$$ J i , j ’s have zero mean and finite variance then, after proper normalization, the minimum and maximum 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}$$ J i , j ’s is allowed to be zero with probability going to 1 as $$N \rightarrow \infty $$ N → ∞ in a suitable way.

arXiv:2402.17059•Bollettino Della Unione Matematica Italiana•Aug 22, 2024•7 citations

The binarization of the decision rule in the binary optimization problem

Boris Kryzhanovsky, Vladimir Kryzhanovsky

The study deals with minimization of a multiple-extremum quadratic functional defined in the state space of binary variables. In order to speed the computation of the local field (which is similar to the gradient in the continuous space), we offer binarization of the matrix on which the functional is built by substituting its elements with 0, +1, or −1 according to their signs. We show that the binarization can be performed so that the computed and real directions of the local field will very likely be the same. The algorithm is particularly useful for treating high-dimensionality configuration spaces because the binarization of the matrix considerably simplifies computations and decreases the amount of memory needed.

Optical Memory and Neural Networks•Mar 1, 2010•0 citations

Discretization of a matrix in quadratic functional binary optimization

Boris Kryzhanovsky, M. V. Kryzhanovsky, M. Yu. Malsagov

The capability of discretization of matrix elements in the problem of quadratic functional minimization with linear member built on matrix in N-dimensional configuration space with discrete coordinates is researched. It is shown, that optimal procedure of replacement matrix elements by the integer quantities with the limited number of gradations exist, and the efficient of minimization does not reduce. Parameter depends on matrix properties, which allows estimate the capability of using described procedure for given type of matrix, is found. Computational complexities of algorithm and RAM requirements are reduced by 16 times, correct using of integer elements allows increase minimization algorithm speed by the orders.

arXiv:1205.0732•Doklady Mathematics•Jun 1, 2011•5 citations

Bounds for Random Binary Quadratic Programs

Karthik Natarajan, Dongjian Shi, Kim-Chuan Toh

In this paper, we consider a binary quadratic program (BQP) with random objective coefficients. Given only information on the marginal distributions of the objective coefficients, we propose a tight bound on the expected optimal value of the random BQP. We show that the complexity of computing this bound does not increase substantially with respect to the complexity of solving the corresponding deterministic BQP. For the quadratic unconstrained binary optimization (QUBO) problem with nonnegative off-diagonal random entries, the bound is shown to be computable in polynomial time. We generalize the asymptotic bound for the random quadratic assignment problem from independent random variables to dependent random variables and propose a new closed-form bound on the expected optimal value of the quadratic k-cluster problem. We also provide polynomial time computable upper bounds on the expected optimal value for the NP-hard instances using the linear and semidefinite programming relaxation of the deterministic BQP. The semidefinite programming bound of the expected optimal value of the random MAX-CUT problem inherits the approximation ratio of 0.878 from the semidefinite relaxation of the deterministic MAX-CUT problem. Computational experiments on random QUBO problems and random quadratic knapsack problems provide evidence of the quality of the bounds. Overall, our results indicate that the new bound on the expected optimal value of the random BQP is attractive since it exploits many of the nice results and formulations of the deterministic BQP and is valid under limited distributional information.

SIAM Journal on Optimization•Jan 1, 2018•4 citations

Extension of Quantum Annealing

Hiroshi Isshiki, Koki Asari

Quantum annealing enables a global minimum search for quadratic functions in binary integer variables. It should be applied to more general problems. Therefore, in this research, we investigate the extension of the method to solve global minimum search by the quantum annealing method. There are three issues that need to be addressed: (1) conversion of decimal integer variables to binary integer variables; (2) binary discrete variable approximation of decimal continuous variables; (3) extension to general non-quadratic functions. This paper aims to develop the basic mathematics necessary for expanding the scope of application of the quantum annealing method, which was created as a solution to the minimum problem of quadratic functions of binary integer variables.

The Proceedings of Mechanical Engineering Congress Japan•Jan 1, 2023•0 citations

Enhancing convexification techniques for solving nonconvex quadratic programming problems

Xiaofei Qi

At the intersection of combinatorial and nonlinear optimization, quadratic programming (QP) plays an important role in practice and optimization theory.With wide-spread real-world applications including, but not limited to, engineering design, game theory, and economics, quadratic programming has many valuable contributions and has attracted considerable interest over the past few decades.As a more general formulation, quadratically constrained quadratic programming (QCQP) problems arise naturally from a lot of applications such as facility location, production planning, economic equilibria and Euclidean distance geometry, etc.Most global optimization approaches for nonconvex QCQPs are based on constructing a convex or linear relaxation of the problem, and embedding it within an exhaustive search mechanism, where a lower bound is calculated as the value of the objective function of this relaxation (for a minimization problem) at each iteration of the search tree.The two principle elements affecting the overall effectiveness of such exhaustive search methods are the tightness of the underlying relaxation and the efficiency of calculating the lower bound.Besides, the performance of a branch-and-bound algorithm also relies on the procedure used to select a branching node and branching variable, which leads to good quality feasible solutions or equivalently an upper bound.vii LIST OF TABLES 5.5 Computational results of 0-1 QPs with n = 40 . . . . . . . . . . . .110 5.6 Computational results of 0-1 QPs with n = 50 . . . . . . . . . . . .

•Jan 1, 2017•0 citations
The paper deals with the problem of quadratic functional minimization in the space of binary variables. We analyze the efficiency of the random search procedure used in binary minimization and show that the radius of the attraction area of a minimum directly depends on its depth: the deeper the minimum, the greater its radius of attraction. Thus, the probability of finding a minimum during random search grows exponentially with depth of the minimum.
Abstract Quadratic Unconstrained Binary Optimization (QUBO or UBQP) is concerned with maximizing/minimizing the quadratic form H(J,η)=W∑i,jJi,jηiηjH(J, \eta ) = W \sum _{i,j} J_{i,j} \eta _{i} \eta _{j}H(J,η)=W∑i,j​Ji,j​ηi​ηj​ H ( J , η ) = W ∑ i , j J i , j η i η j with J a matrix of coefficients, η∈{0,1}N\eta \in \{0, 1\}^Nη∈{0,1}N η ∈ { 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 Ji,jJ_{i,j}Ji,j​ J i , j ’s have zero mean and finite variance then, after proper normalization, the minimum and maximum 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 Ji,jJ_{i,j}Ji,j​ J i , j ’s is allowed to be zero with probability going to 1 as N→∞N \rightarrow \infty N→∞ N → ∞ in a suitable way.
The study deals with minimization of a multiple-extremum quadratic functional defined in the state space of binary variables. In order to speed the computation of the local field (which is similar to the gradient in the continuous space), we offer binarization of the matrix on which the functional is built by substituting its elements with 0, +1, or −1 according to their signs. We show that the binarization can be performed so that the computed and real directions of the local field will very likely be the same. The algorithm is particularly useful for treating high-dimensionality configuration spaces because the binarization of the matrix considerably simplifies computations and decreases the amount of memory needed.
The capability of discretization of matrix elements in the problem of quadratic functional minimization with linear member built on matrix in N-dimensional configuration space with discrete coordinates is researched. It is shown, that optimal procedure of replacement matrix elements by the integer quantities with the limited number of gradations exist, and the efficient of minimization does not reduce. Parameter depends on matrix properties, which allows estimate the capability of using described procedure for given type of matrix, is found. Computational complexities of algorithm and RAM requirements are reduced by 16 times, correct using of integer elements allows increase minimization algorithm speed by the orders.
In this paper, we consider a binary quadratic program (BQP) with random objective coefficients. Given only information on the marginal distributions of the objective coefficients, we propose a tight bound on the expected optimal value of the random BQP. We show that the complexity of computing this bound does not increase substantially with respect to the complexity of solving the corresponding deterministic BQP. For the quadratic unconstrained binary optimization (QUBO) problem with nonnegative off-diagonal random entries, the bound is shown to be computable in polynomial time. We generalize the asymptotic bound for the random quadratic assignment problem from independent random variables to dependent random variables and propose a new closed-form bound on the expected optimal value of the quadratic k-cluster problem. We also provide polynomial time computable upper bounds on the expected optimal value for the NP-hard instances using the linear and semidefinite programming relaxation of the deterministic BQP. The semidefinite programming bound of the expected optimal value of the random MAX-CUT problem inherits the approximation ratio of 0.878 from the semidefinite relaxation of the deterministic MAX-CUT problem. Computational experiments on random QUBO problems and random quadratic knapsack problems provide evidence of the quality of the bounds. Overall, our results indicate that the new bound on the expected optimal value of the random BQP is attractive since it exploits many of the nice results and formulations of the deterministic BQP and is valid under limited distributional information.
Quantum annealing enables a global minimum search for quadratic functions in binary integer variables. It should be applied to more general problems. Therefore, in this research, we investigate the extension of the method to solve global minimum search by the quantum annealing method. There are three issues that need to be addressed: (1) conversion of decimal integer variables to binary integer variables; (2) binary discrete variable approximation of decimal continuous variables; (3) extension to general non-quadratic functions. This paper aims to develop the basic mathematics necessary for expanding the scope of application of the quantum annealing method, which was created as a solution to the minimum problem of quadratic functions of binary integer variables.
At the intersection of combinatorial and nonlinear optimization, quadratic programming (QP) plays an important role in practice and optimization theory.With wide-spread real-world applications including, but not limited to, engineering design, game theory, and economics, quadratic programming has many valuable contributions and has attracted considerable interest over the past few decades.As a more general formulation, quadratically constrained quadratic programming (QCQP) problems arise naturally from a lot of applications such as facility location, production planning, economic equilibria and Euclidean distance geometry, etc.Most global optimization approaches for nonconvex QCQPs are based on constructing a convex or linear relaxation of the problem, and embedding it within an exhaustive search mechanism, where a lower bound is calculated as the value of the objective function of this relaxation (for a minimization problem) at each iteration of the search tree.The two principle elements affecting the overall effectiveness of such exhaustive search methods are the tightness of the underlying relaxation and the efficiency of calculating the lower bound.Besides, the performance of a branch-and-bound algorithm also relies on the procedure used to select a branching node and branching variable, which leads to good quality feasible solutions or equivalently an upper bound.vii LIST OF TABLES 5.5 Computational results of 0-1 QPs with n = 40 . . . . . . . . . . . .110 5.6 Computational results of 0-1 QPs with n = 50 . . . . . . . . . . . .