Algorithmic QUBO formulations for k-SAT and hamiltonian cycles

Jonas Nüßlein, Thomas Gabor, Claudia Linnhoff-Popien, Sebastian Feld

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

7 Citations (Scopus)
50 Downloads (Pure)

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. 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.

Original languageEnglish
Title of host publicationGECCO 2022 Companion - Proceedings of the 2022 Genetic and Evolutionary Computation Conference
PublisherACM
Pages2240-2246
Number of pages7
ISBN (Electronic)978-1-4503-9268-6
DOIs
Publication statusPublished - 2022
Event2022 Genetic and Evolutionary Computation Conference, GECCO 2022 - Virtual, Online, United States
Duration: 9 Jul 202213 Jul 2022

Publication series

NameGECCO 2022 Companion - Proceedings of the 2022 Genetic and Evolutionary Computation Conference

Conference

Conference2022 Genetic and Evolutionary Computation Conference, GECCO 2022
Country/TerritoryUnited States
CityVirtual, Online
Period9/07/2213/07/22

Bibliographical note

Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care
Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Keywords

  • hamiltonian cycle
  • ising
  • k-SAT
  • QUBO
  • satisfiability

Fingerprint

Dive into the research topics of 'Algorithmic QUBO formulations for k-SAT and hamiltonian cycles'. Together they form a unique fingerprint.

Cite this