Analyzing quadratic unconstrained binary optimization problems via multicommodity flows [PDF]
Discrete Applied Mathematics, 2009 Quadratic Unconstrained Binary Optimization (QUBO) problems concern the minimization of quadratic polynomials in n {0, 1}-valued variables. These problems are NP-complete, but prior work has identified a sequence of polynomial-time computable lower bounds on the minimum value, denoted by C(2), C(3), C(4),….
Robert Kleinberg
exaly +6 more sources
On the hardness of quadratic unconstrained binary optimization problems [PDF]
Frontiers in Physics, 2022 We use exact enumeration to characterize the solutions of quadratic unconstrained binary optimization problems of less than 21 variables in terms of their distributions of Hamming distances to close-by solutions.
V. Mehta +7 more
doaj +9 more sources
Goal seeking Quadratic Unconstrained Binary Optimization
Results in Control and Optimization, 2022 The Quadratic Unconstrained Binary Optimization (QUBO) modeling and solution framework is a requirement for quantum and digital annealers. However optimality for QUBO problems of any practical size is extremely difficult to achieve.
Amit Verma, Mark Lewis
doaj +5 more sources
Benchmark of quantum-inspired heuristic solvers for quadratic unconstrained binary optimization [PDF]
Scientific Reports, 2022 Recently, inspired by quantum annealing, many solvers specialized for unconstrained binary quadratic programming problems have been developed. For further improvement and application of these solvers, it is important to clarify the differences in their ...
Hiroki Oshiyama, Masayuki Ohzeki
doaj +6 more sources
Quadratic Unconstrained Binary Optimization for the Automotive Paint Shop Problem [PDF]
IEEE Access, 2023 The Binary Paint Shop Problem (BPSP) is a combinatorial optimization problem which draws inspiration from the automotive paint shop. Its binary nature, making it a good fit for Quadratic Unconstrained Binary Optimization (QUBO) solvers, has been well ...
Pieter Debevere +2 more
doaj +3 more sources
Extremal Optimization for Quadratic Unconstrained Binary Problems [PDF]
Physics Procedia, 2015 AbstractWe present an implementation of τ-EO for quadratic unconstrained binary optimization (QUBO) problems. To this end, we transform modify QUBO from its conventional Boolean presentation into a spin glass with a random external field on each site.
Stefan Boettcher
exaly +3 more sources
Sampling electronic structure quadratic unconstrained binary optimization problems (QUBOs) with Ocean and Mukai solvers. [PDF]
PLoS ONE, 2022 The most advanced D-Wave Advantage quantum annealer has 5000+ qubits, however, every qubit is connected to a small number of neighbors. As such, implementation of a fully-connected graph results in an order of magnitude reduction in qubit count.
Alexander Teplukhin +4 more
doaj +2 more sources
Quadratic unconstrained binary optimization problem preprocessing: Theory and empirical analysis [PDF]
Networks, 2017 The Quadratic Unconstrained Binary Optimization problem (QUBO) has become a unifying model for representing a wide range of combinatorial optimization problems, and for linking a variety of disciplines that face these problems. A new class of quantum annealing computer that maps QUBO onto a physical qubit network structure with specific size and edge ...
Fred Glover, Mark Lewis
exaly +3 more sources
Digital Annealer for quadratic unconstrained binary optimization: A comparative performance analysis
Applied Soft Computing Journal, 2022 Digital Annealer (DA) is a computer architecture designed for tackling combinatorial optimization problems formulated as quadratic unconstrained binary optimization (QUBO) models. In this paper, we present the results of an extensive computational study to evaluate the performance of DA in a systematic way in comparison to multiple state-of-the-art ...
Merve Bodur, Oylum Şeker
exaly +3 more sources
Quadratic unconstrained binary optimization and constraint programming approaches for lattice-based cyclic peptide docking [PDF]
Scientific ReportsThe peptide-protein docking problem is an important problem in structural biology that facilitates rational and efficient drug design. In this work, we explore modeling and solving this problem with the quantum-amenable quadratic unconstrained binary ...
J. Kyle Brubaker +6 more
doaj +2 more sources