Using an Evolutionary Algorithm to Create (MAX)-3SAT QUBOs
Open Access
- 14 July 2024
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1984-1992
Abstract
A common way of solving satisfiability instances with quantum methods is to transform these instances into instances of QUBO. State-of-the-art transformations from MAX-3SAT to QUBO 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 is, therefore, algorithmically inefficient, we see potential for including search-based optimization. In this paper, we propose two methods of using evolutionary algorithms to create QUBO representations of MAX-3SAT problems automatically. 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.Keywords
All Related Versions
Funding Information
- German Federal Ministry of Education and Research (13N16196)
- German Federal Ministry for Economic Affairs and Climate Action (01MQ22008A)
This publication has 30 references indexed in Scilit:
- A Comparison of Evolutionary Algorithms for Training Variational Quantum Classifiers2023
- Genetic algorithms as classical optimizer for the Quantum Approximate Optimization AlgorithmApplied Soft Computing, 2023
- Variational quantum reinforcement learning via evolutionary optimizationMachine Learning: Science and Technology, 2022
- Productive fitness in diversity-aware evolutionary algorithmsNatural Computing, 2021
- Reverse quantum annealing approach to portfolio optimization problemsQuantum Machine Intelligence, 2019
- Quantum Annealing of Vehicle Routing Problem with Time, State and Capacity2019
- Quadratic reformulations of nonlinear binary optimization problemsMathematical Programming, 2016
- Memetic algorithms and memetic computing optimization: A literature reviewSwarm and Evolutionary Computation, 2012
- The dynamics of a Genetic Algorithm for simple random Ising systemsPhysica D: Nonlinear Phenomena, 1997
- Genetic algorithm approach for Ising modelJournal of Magnetism and Magnetic Materials, 1994