  Boolean satisfiability (SAT) solving is a fundamental problem in computer
science. Finding efficient algorithms for SAT solving has broad implications in
many areas of computer science and beyond. Quantum SAT solvers have been
proposed in the literature based on Grover's algorithm. Although existing
quantum SAT solvers can consider all possible inputs at once, they evaluate
each clause in the formula one by one sequentially, making the time complexity
O(m) -- linear to the number of clauses m -- per Grover iteration. In this
work, we develop a parallel quantum SAT solver, which reduces the time
complexity in each iteration from linear time O(m) to constant time O(1) by
utilising extra entangled qubits. To further improve the scalability of our
solution in case of extremely large problems, we develop a distributed version
of the proposed parallel SAT solver based on quantum teleportation such that
the total qubits required are shared and distributed among a set of quantum
computers (nodes), and the quantum SAT solving is accomplished collaboratively
by all the nodes. We have proved the correctness of our approaches and
demonstrated them in simulations.
