Algorithmic QUBO Formulations for k-SAT and Hamiltonian Cycles

Quadratic unconstrained binary optimization (QUBO) can be seen as a generic language for optimization problems. QUBOs attract particular attention since they can be solved with quantum hardware, like quantum annealers or quantum gate computers running QAOA. In this paper, we present two novel QUBO f...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2022-04
Main Authors: Nüßlein, Jonas, Gabor, Thomas, Linnhoff-Popien, Claudia, Feld, Sebastian
Format: Article
Language:English
Subjects:
Algorithms
Mathematical analysis
Nodes
Optimization
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Quadratic unconstrained binary optimization (QUBO) can be seen as a generic language for optimization problems. QUBOs attract particular attention since they can be solved with quantum hardware, like quantum annealers or quantum gate computers running QAOA. In this paper, we present two novel QUBO formulations for \(k\)-SAT and Hamiltonian Cycles that scale significantly better than existing approaches. For \(k\)-SAT we reduce the growth of the QUBO matrix from \(O(k)\) to \(O(log(k))\). For Hamiltonian Cycles the matrix no longer grows quadratically in the number of nodes, as currently, but linearly in the number of edges and logarithmically in the number of nodes. We present these two formulations not as mathematical expressions, as most QUBO formulations are, but as meta-algorithms that facilitate the design of more complex QUBO formulations and allow easy reuse in larger and more complex QUBO formulations.
ISSN:2331-8422
DOI:10.48550/arxiv.2204.13539