M. J. Kramer (2023)
On Quantum Algorithms for Satisfiability Problems

I submitted this work as my Master's thesis. Prof. Dr. Jens Eisert, Alexander Nietner, Paul K. Fährmann, and Johannes Jakob Meyer supervised this project. The full text is available on request.

Abstract:

In this work, we look at quantum algorithms from the perspective of classical optimization. We acknowledge that optimization problems that are classically hard in worst-case complexity can surely be solved in polynomial time for large classes of instances. In this work, we focus on satisfiability problems.

For example, in a Boolean satisfiability problem (SAT), if the clauses have a limited dependency on each other, one can find solutions in polynomial time using the Moser-Tardos algorithm. This can be rigorously explained using the Lovász Local Lemma. We study the classical background and also contribute here: We present a project where we use the Lovász Local Lemma and deep learning to construct stochastic local search solvers for SAT with performance guarantees. This is done by training an oracle factory, which can be used in the Moser-Tardos algorithm. We see that the machine-learning-boosted version of the Moser-Tardos algorithm can solve significantly more random 3-SAT instances than its uniform version. In addition, it is much faster regarding the steps it needs. Furthermore, we pitch an idea to study the relation of the Moser-Tardos algorithm to simulated annealing algorithms.

The main focus of this manuscript is to apply ideas from the classical side on the quantum side. Here, we try to find quantum algorithms that take inspiration from the Moser-Tardos algorithm. Luckily, the Lovász Local Lemma extends to the quantum setting. Therefore, it can be used to get a guarantee that certain instances of the quantum satisfiability problem (QSAT) are satisfiable. Those instances that fulfill the quantum generalization of the Lovász Local Lemma are studied, and we look at quantum algorithms that are guaranteed to find a satisfying state on those instances efficiently. We review the literature and propose a novel quantum algorithm that numerically outperforms existing quantum algorithms by orders of magnitude. We report various numerical results. Furthermore, we try to prove and understand the fast convergence of our algorithm analytically. Various ideas and attempts are presented. In particular, we show a proof of convergence to the ground state for our algorithm. In addition, we numerically study the behavior of our algorithm on random 3-QSAT instances. The performance beyond the regime where the Quantum Lovász Local Lemma guarantees satisfiability is reported.

M. J. Kramer & P. Boes (2023)
Using deep learning to construct stochastic local search SAT solvers with performance bounds

Preprint arXiv:2309.11452

GitHub Repository

Abstract: 

The Boolean Satisfiability problem (SAT) is the most prototypical NP-complete problem and of great practical relevance. One important class of solvers for this problem are stochastic local search (SLS) algorithms that iteratively and randomly update a candidate assignment. Recent breakthrough results in theoretical computer science have established sufficient conditions under which SLS solvers are guaranteed to efficiently solve a SAT instance, provided they have access to suitable "oracles" that provide samples from an instance-specific distribution, exploiting an instance's local structure. Motivated by these results and the well established ability of neural networks to learn common structure in large datasets, in this work, we train oracles using Graph Neural Networks and evaluate them on two SLS solvers on random SAT instances of varying difficulty. We find that access to GNN-based oracles significantly boosts the performance of both solvers, allowing them, on average, to solve 17% more difficult instances (as measured by the ratio between clauses and variables), and to do so in 35% fewer steps, with improvements in the median number of steps of up to a factor of 8. As such, this work bridges formal results from theoretical computer science and practically motivated research on deep learning for constraint satisfaction problems and establishes the promise of purpose-trained SAT solvers with performance guarantees.

M. J. Kramer (2021)
A Variational Approach for Quantum Annealing within the LHZ Architecture

I submitted this work as my Bachelor's thesis. Prof. Dr. Wolfgang Lechner, Dr. Andreas Hartmann, and Prof. Dr. Tilman Enss supervised this project. The full text is available on request.

Abstract:

In this thesis, I present an overview of adiabatic quantum computing and quantum annealing. I focus on the Lechner-Hauke-Zoller (LHZ) architecture proposed for an Ising model. This architecture is scalable, fully connected, and can be implemented using local interactions only. The main focus of this thesis is a variational approach within the LHZ architecture recently proposed by Susa and Nishimori. The schedule function for the constraint term that occurs in the LHZ architecture via construction is variationally improved during several diabatic sweeps. It is observed for a ferromagnetic Ising model and for spin-glass samples that the variationally obtained non-monotonic schedule function increases the final ground-state fidelity significantly.
Furthermore the obtained energy expectation value decreases towards the true ground state energy. In this thesis, I implemented an LHZ architecture in Python and reproduced the numerical results presented by Susa and Nishimori. Furthermore, my numerical studies go into a bit more into detail. Namely, I varied some more free parameters.