We present a quantum-inspired tensor network algorithm for solving tridiagonal Quadratic Unconstrained Binary Optimization (QUBO) problems and quadratic unconstrained discrete optimization (QUDO) problems. We also solve the more general Tensor quadratic unconstrained discrete optimization (T-QUDO) problems with one-neighbor interactions in a lineal chain. This method provides an exact and explicit equation for these problems. Our algorithms are based on the simulation of a state that undergoes imaginary time evolution and a Half partial trace. In addition, we address the degenerate case and evaluate the polynomial complexity of the algorithm, also providing a parallelized version. We implemented and tested them with other well-known classical algorithms and observed an improvement in the quality of the results. The performance of the proposed algorithms is compared with the Google OR-TOOLS and dimod solvers, improving their results.
We present a quantum-inspired tensor network algorithm for solving tridiagonal Quadratic Unconstrained Binary Optimization (QUBO) problems and quadratic unconstrained discrete optimization (QUDO) problems. We also solve the more general Tensor quadratic unconstrained discrete optimization (T-QUDO) problems with one-neighbor interactions in a lineal chain. This method provides an exact and explicit equation for these problems. Our algorithms are based on the simulation of a state that undergoes imaginary time evolution and a Half partial trace. In addition, we address the degenerate case and evaluate the polynomial complexity of the algorithm, also providing a parallelized version. We implemented and tested them with other well-known classical algorithms and observed an improvement in the quality of the results. The performance of the proposed algorithms is compared with the Google OR-TOOLS and dimod solvers, improving their results.
This work presents a novel tensor network algorithm for solving Quadratic Unconstrained Binary Optimization (QUBO) problems, Quadratic Unconstrained Discrete Optimization (QUDO) problems, and Tensor Quadratic Unconstrained Discrete Optimization (T-QUDO) problems. The proposed algorithm is based on the MeLoCoToN methodology, which solves combinatorial optimization problems by employing superposition, imaginary time evolution, and projective measurements. Additionally, two different approaches are presented to solve QUBO and QUDO problems with k-neighbors interactions in a lineal chain, one based on 4-order tensor contraction and the other based on matrix-vector multiplication, including sparse computation and a new technique called "Waterfall". Furthermore, the performance of both implementations is compared with a quadratic optimization solver to demonstrate the performance of the method, showing advantages in several problem instances.
In this paper, we present two tensor network quantum-inspired algorithms to solve the knapsack and the shortest path problems, and enables to solve some of its variations. These methods provide an exact equation which returns the optimal solution of the problems. As in other tensor network algorithms for combinatorial optimization problems, the method is based on imaginary time evolution and the implementation of restrictions in the tensor network. In addition, we introduce the use of symmetries and the reutilization of intermediate calculations, reducing the computational complexity for both problems. To show the efficiency of our implementations, we carry out some performance experiments and compare the results with those obtained by other classical algorithms.
Quadratic Unconstrained Binary Optimization (QUBO) is a broad class of optimization problems with many practical applications. To solve its hard instances in an exact way, known classical algorithms require exponential time and several approximate methods have been devised to reduce such cost. With the growing maturity of quantum computing, quantum algorithms have been proposed to speed up the solution by using either quantum annealers or universal quantum computers. Here we apply the divide-and-conquer approach to reduce the original problem to a collection of smaller problems whose solutions can be assembled to form a single Polynomial Binary Unconstrained Optimization instance with fewer variables. This technique can be applied to any QUBO instance and leads to either an all-classical or a hybrid quantum-classical approach. When quantum heuristics like the Quantum Approximate Optimization Algorithm (QAOA) are used, our proposal leads to a double advantage: a substantial reduction of quantum resources, specifically an average of ~42% fewer qubits to solve MaxCut on random 3-regular graphs, together with an improvement in the quality of the approximate solutions reached.
Quadratic Unconstrained Binary Optimization (QUBO) provides a versatile framework for representing NP-hard combinatorial problems, yet existing solvers often face trade-offs among speed, accuracy, and scalability. In this work, we introduce a quantum-inspired solver (QIS) that unites branch-and-bound pruning, continuous gradient-descent refinement, and quantum-inspired heuristics within a fully adaptive control architecture. We benchmark QIS3 against eight state-of-the-art solvers, including genetic algorithms, coherent Ising machines, simulated bifurcation, parallel tempering, simulated annealing, our prior QIS2 version, D-Wave's simulated-annealing (Neal), and Gurobi on three canonical QUBO problem classes: Max-Cut, NAE-3SAT, and Sherrington-Kirkpatrick spin glass problems. Under a uniform runtime budget, QIS3 attains the best solution on nearly all instances, achieving optimality in 94% of max-cut instances. These results establish QIS3 as a robust, high-performance solver that bridges classical exact strategies and quantum-inspired heuristics for scalable QUBO optimization.
In this study, we introduce a novel family of tensor networks, termed constrained matrix product states (MPS), designed to incorporate exactly arbitrary discrete linear constraints, including inequalities, into sparse block structures. These tensor networks are particularly tailored for modeling distributions with support strictly over the feasible space, offering benefits such as reducing the search space in optimization problems, alleviating overfitting, improving training efficiency, and decreasing model size. Central to our approach is the concept of a quantum region, an extension of quantum numbers traditionally used in U(1) U ( 1 ) symmetric tensor networks, adapted to capture any linear constraint, including the unconstrained scenario. We further develop a novel canonical form for these new MPS, which allow for the merging and factorization of tensor blocks according to quantum region fusion rules and permit optimal truncation schemes. Utilizing this canonical form, we apply an unsupervised training strategy to optimize arbitrary objective functions subject to discrete linear constraints. Our method’s efficacy is demonstrated by solving the quadratic knapsack problem, achieving superior performance compared to a leading nonlinear integer programming solver. Additionally, we analyze the complexity and scalability of our approach, demonstrating its potential in addressing complex constrained combinatorial optimization problems.
Practical discrete optimization problems often contain multidimensional arrays of variables with linear constraints, which complicates their conversion to QUBO (quadratic unconstrained binary optimization) form. The article proposes a systematic approach to transforming such problems, which includes three key steps: the transition from a multidimensional representation of variables to a one-dimensional one using the Kronecker product of matrices, the reduction of mixed variables to binary ones, and the introduction of linear constraints into the objective function through quadratic penalties. Explicit computational formulas are obtained for each stage, simplifying their software implementation. The developed method is illustrated with examples from graph theory and combinatorial optimization, including classical formulations, confirming its universality. The results of the article allow standardizing the process of adapting problems for solving on quantum annealing algorithms (e.g., D-Wave) and classical QUBO solvers.