Using an Evolutionary Algorithm to Create (MAX)-3SAT QUBOs
<|reference_start|>Using an Evolutionary Algorithm to Create (MAX)-3SAT QUBOs: A common way of solving satisfiability instances with quantum methods is to transform these instances into instances of QUBO, which in itself is a potentially difficult and expensive task. State-of-the-art transformations from MAX-3SAT to QUBO currently work by mapping clauses of a 3SAT formula associated with the MAX-3SAT instance to an instance of QUBO and combining the resulting QUBOs into a single QUBO instance representing the whole MAX-3SAT instance. As creating these transformations is currently done manually or via exhaustive search methods and, therefore, algorithmically inefficient, we see potential for including search-based optimization. In this paper, we propose two methods of using evolutionary algorithms to automatically create QUBO representations of MAX-3SAT problems. We evaluate our created QUBOs on 500 and 1000-clause 3SAT formulae and find competitive performance to state-of-the-art baselines when using both classical and quantum annealing solvers.<|reference_end|>
@article{zielinski2024using,
    title={Using an Evolutionary Algorithm to Create (MAX)-3SAT QUBOs},
    author={Sebastian Zielinski, Maximilian Zorn, Thomas Gabor, Sebastian Feld,
  Claudia Linnhoff-Popien},
    journal={arXiv preprint arXiv:2405.09272},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.09272},
    primaryClass={quant-ph cs.ET}
}