Algorithmic QUBO formulations for <i>k</i> -SAT and hamiltonian cycles
Jonas Nüßlein, Thomas Gabor, Claudia Linnhoff–Popien, Sebastian Feld
2022Proceedings of the Genetic and Evolutionary Computation Conference Companion18 citationsDOIOpen Access PDF
Abstract
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.
Topics & Concepts
Quadratic unconstrained binary optimizationQuadratic growthHamiltonian (control theory)Quadratic equationQuantum annealingQuantumComputer scienceQuantum computerBinary numberMathematicsMathematical optimizationAlgorithmArithmeticPhysicsQuantum mechanicsGeometryQuantum Computing Algorithms and ArchitectureQuantum Information and CryptographyQuantum-Dot Cellular Automata