In this paper we consider the closest vector problem (CVP) for lattices $Λ\subseteq \mathbb{Z}^n$ given by a generator matrix $A\in \mathcal{M}_{n\times n}(\mathbb{Z})$. Let $b>0$ be the maximum of the absolute values of the entries of the matrix $A$. We prove that the CVP can be reduced in polynomial time to a quadratic unconstrained binary optimization (QUBO) problem in $O(n^2(\log(n)+\log(b)))$ binary variables, where the length of the coefficients in the corresponding quadratic form is $O(n(\log(n)+\log(b)))$.
In this paper we consider the closest vector problem (CVP) for lattices Λ⊆Zn given by a generator matrix A∈Mn×n(Z). Let b>0 be the maximum of the absolute values of the entries of the matrix A. We prove that the CVP can be reduced in polynomial time to a quadratic unconstrained binary optimization (QUBO) problem in O(n2(log(n)+log(b))) binary variables, where the length of the coefficients in the corresponding quadratic form is O(n(log(n)+log(b))).
Abstract Quadratic Unconstrained Binary Optimization (QUBO or UBQP) is concerned with maximizing/minimizing the quadratic form H(J,η)=W∑i,jJi,jηiηj H ( J , η ) = W ∑ i , j J i , j η i η j with J a matrix of coefficients, η∈{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,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,j J i , j ’s is allowed to be zero with probability going to 1 as N→∞ N → ∞ in a suitable way.
A quadratic unconstrained binary optimization (QUBO) model is defined by an objective function that consists of a quadratic formula involving multiple binary variables. The goal of the QUBO problem is to find an optimal assignment of values to the variables that minimizes the objective function. One of the most well-known problems that can be reduced to a QUBO problem is the N-Queens problem. The N-Queens problem seeks to find a configuration of n queens on an n×n chessboard such that no two queens can attack each other. It is widely recognized that a conventional technique can be used to design a QUBO model with an n×n matrix of binary variables representing the chessboard, where a queen is placed in a particular position if and only if the corresponding binary variable is set to 1. This technique involves incorporating terms in the objective function to ensure that the sum of each row and column is 1, and the sum of each diagonal and anti-diagonal is either 0 or 1. The resulting reduced QUBO model contains 35n3−2n2+31n quadratic terms. Due to the simplicity and straightforwardness of designing such a QUBO model, there are numerous resources available that explain this model as an easy example of QUBO models. However, to the best of our knowledge, no fundamentally different approach to designing a QUBO model for the N-Queens problem has been discovered. The prevailing view within the community is that this approach is the only method for designing a QUBO model for the N-Queens problem, and no superior alternative has been found. In this paper, we will present a counterintuitive result that demonstrates a more efficient QUBO model for the N-Queens problem, requiring fewer quadratic terms. Surprisingly, this alternative model involves only 12n2−24n+12 quadratic terms, which is smaller than the conventional QUBO model whenever n is greater than or equal to 7. This discovery marks a significant breakthrough in the theoretical challenge of minimizing a QUBO model for solving the N-Queens problem.
This dissertation investigates the Quadratic Unconstrained Binary Optimization (QUBO) problem, i.e. the problem of minimizing a quadratic function in binary variables. QUBO is studied at two complementary levels. First, there is an algorithmic aspect that tells how to preprocess the problem, how to find heuristics, how to get improved bounds and how to solve the problem with all the above ingredients.Second, there is a practical aspect that uses QUBO to solve various applications from the engineering and social sciences fields including: via minimization, 2D/3D Ising models, 1D Ising chain models, image binarization, hierarchical clustering, greedy graph coloring/partitioning, MAX-2-SAT, MIN-VC, MAX-CLIQUE, MAX-CUT, graph stability and minimum k-partition.Several families of fast heuristics for QUBO are analyzed, which include a novel probabilistic based class of methods.It is shown that there is a unique maximal set of persistencies for the linearization model for QUBO.This set is determined in polynomial time by a maximum flow followed by the computation of the strong components of a network that has 2n+2 nodes, where n is the number of variables. The identification of the above persistencies leads to a unique decomposition of the function, such that each component can be optimized separately. To find further persistencies, two additional techniques are proposed: one is based on the second order derivatives of Hammer et al. [HH81]; the other technique is a probing procedure on the two possible values of the variables.These preprocessing tools work remarkably well for certain classes of problems.We improved the Iterated Roof-Dual bound (IRD) of [BH89] by proposing two combinatorial methods: one was named the squeezed IRD; and the second was called the project-and-lift IRD method.The cubic-dual bound can be found by means of linear programming by adding a set of triangle inequalities to the standard linearization, whose number is cubic in the number of variables. We show that this set can be reduced depending on the coefficients of the terms of the function. This leads to the possibility of computing the cubic-duals of larger QUBOs.
The closest vector problem (CVP) is a fundamental optimization problem in lattice-based cryptography and its conjectured hardness underpins the security of lattice-based cryptosystems. Furthermore, Schnorr's lattice-based factoring algorithm reduces integer factoring (the foundation of current cryptosystems, including RSA) to the CVP. Recent work has investigated the inclusion of a heuristic CVP approximation `refinement' step in the lattice-based factoring algorithm, using quantum variational algorithms to perform the heuristic optimization. This coincides with the emergence of probabilistic computing as a hardware accelerator for randomized algorithms including tasks in combinatorial optimization. In this work we investigate the application of probabilistic computing to the heuristic optimization task of CVP approximation refinement in lattice-based factoring. We present the design of a probabilistic computing algorithm for this task, a discussion of `prime lattice' parameters, and experimental results showing the efficacy of probabilistic computing for solving the CVP as well as its efficacy as a subroutine for lattice-based factoring. The main results found that (a) this approach is capable of finding the maximal available CVP approximation refinement in time linear in problem size and (b) probabilistic computing used in conjunction with the lattice parameters presented can find the composite prime factors of a semiprime number using up to 100x fewer lattice instances than similar quantum and classical methods.
Quadratic Unconstrained Binary Optimization (QUBO) models are defined by quadratic expressions composed of binary variables, each taking a value of either 0 or 1. The objective of the QUBO problem is to find an optimal assignment of these binary variables that minimizes the value of the QUBO model. The QUBO problem has attracted significant research interest due to its versatility in reformulating various NP-complete problems and its potential for efficiently finding heuristic solutions through quantum annealing. This paper focuses on converting Cubic Unconstrained Binary Optimization (CUBO) problems, defined by cubic expressions, into equivalent QUBO models. Through this conversion, CUBO problems can be solved using quantum annealing. Since the important NP-hard problem 3-SAT can be straightforwardly represented as a CUBO problem, investigating the conversion from CUBO to QUBO models is a meaningful endeavor.
Ising machines, including quantum annealing machines, can efficiently solve combinatorial optimization problems by formulating them as Quadratic Unconstrained Binary Optimization (QUBO). However, it is known that the solving performance of Ising machines deteriorates as the energy landscape represented by the QUBObecomes more complex. Simplifying the coefficients of QUBOmatrix can improve the performance of solving combinatorial optimization problems using an Ising machine. In this paper, we propose QUBO simplification methods for Ising machines using singular value decomposition (SVD) and coefficient elimination based on their absolute value (ABS). The proposed SVD method simplifies QUBO by capturing the global structure of the QUBO matrix. QUBO is further simplified by combining it with the simple ABS method. The simplified QUBO is expected to have a less complex energy landscape, while maintaining the global structure of the original, enabling the Ising machine to efficiently find the (semi-)ground state.We demonstrate the numerical experiments using an Ising machine to evaluate the effectiveness of the SVD method alone, the ABS method alone, and the two methods combined.