Solving k-SAT Problems with Generalized Quantum Measurements, Part II: Algorithm Scaling and Performance

We introduce a novel quantum algorithm solving Boolean satisfiability (k-SAT) problems using only k-local generalized measurement with adjustable strength. The algorithm operates by measuring each clause term of the k-SAT problem while gradually changing the measurement basis. We develop a filtering technique in order to detect clause failures when employing weak measurement. While the algorithm can be implemented autonomously (with Lindbladian dissipation), benchmarking reveals that heralding and filtering significantly improve the algorithm's performance. Furthermore, we clarify the role of measurement strength. While the weak continuous limit is seen to be advantageous in terms of the optimal time-to-solution (TTS) value, the scaling of the optimal TTS with qubit number is similar in both continuous (weak) and discrete (stronger) measurement settings. We show that the quantum system converges to the solution state deterministically in the long time limit, and we analyze the tradeoffs in the overall TTS as we approach that limit.