Distributed quantum-classical hybrid algorithm for solving K-SAT problem

Recently, Dunjko et al.(PRL, 2018) proposed an algorithm for accelerating the solution of 3-satisfiability problems using a small-scale quantum computer. In this paper, we design a distributed quantum-classical hybrid algorithm for solving K-satisfiability problems. Under resource-constrained conditions, our algorithm achieves a significant acceleration in the core term of the exponential time complexity. The proposed algorithm is a generalization of the algorithm by Dunjko et al. Compared with their algorithm, our algorithm requires a smaller number of qubits. More importantly, the proposed algorithm does not rely on any quantum communication.

Source: arXiv:2604.14057v1 - http://arxiv.org/abs/2604.14057v1 PDF: https://arxiv.org/pdf/2604.14057v1 Original Link: http://arxiv.org/abs/2604.14057v1