For 3-SAT problems, direct PUBO encoding shows larger minimum energy gaps than a standard QUBO reduction, hinting at an exponential speedup for some problem families.
Efficient QUBO transformation for Higher Degree Pseudo Boolean Functions
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
Quadratic Unconstrained Binary Optimization (QUBO) is recognized as a unifying framework for modeling a wide range of problems. Problems can be solved with commercial solvers customized for solving QUBO and since QUBO have degree two, it is useful to have a method for transforming higher degree pseudo-Boolean problems to QUBO format. The standard transformation approach requires additional auxiliary variables supported by penalty terms for each higher degree term. This paper improves on the existing cubic-to-quadratic transformation approach by minimizing the number of additional variables as well as penalty coefficient. Extensive experimental testing on Max 3-SAT modeled as QUBO shows a near 100% reduction in the subproblem size used for minimization of the number of auxiliary variables.
citation-role summary
baseline 1
citation-polarity summary
fields
quant-ph 1years
2024 1verdicts
CONDITIONAL 1roles
baseline 1polarities
unclear 1representative citing papers
citing papers explorer
-
Boosting quantum annealing performance through direct polynomial unconstrained binary optimization
For 3-SAT problems, direct PUBO encoding shows larger minimum energy gaps than a standard QUBO reduction, hinting at an exponential speedup for some problem families.