2
$\begingroup$

Is there a quantum SAT algorithm, a quantum analogue of the DPLL or CDCL algorithms?

Note: I'm not looking for the quantum analogue of the Boolean satisfiability problem (though that would be interesting), but a quantum algorithm that solves Boolean SAT problems.

$\endgroup$
5
  • 1
    $\begingroup$ You can use Grover’s algorithm. $\endgroup$
    – Yuval Filmus
    Mar 15, 2022 at 23:02
  • $\begingroup$ @YuvalFilmus Yes, I figured something like that, but wouldn't the search space be too big? $\endgroup$
    – Geremia
    Mar 15, 2022 at 23:18
  • $\begingroup$ Define "too big". I suspect some requirements are missing from the question. It is trivial to come up with an exponential-time algorithm. What are your requirements on the running time of the algorithm? Also, anything you can implement on a conventional computer, you can also implement on a quantum computer, so DPLL and CDCL can already be used on a quantum computer (they can be viewed as quantum algorithms). Perhaps you want to know whether SAT can be solved more efficiently on a quantum computer than on a conventional computer? $\endgroup$
    – D.W. ♦
    Mar 16, 2022 at 4:57
  • 1
    $\begingroup$ Asked on Theoretical Computer Science: cstheory.stackexchange.com/questions/36428/… $\endgroup$
    – Yuval Filmus
    Mar 16, 2022 at 7:22
  • $\begingroup$ @D.W. "Perhaps you want to know whether SAT can be solved more efficiently on a quantum computer than on a conventional computer?" Yes. $\endgroup$
    – Geremia
    Mar 16, 2022 at 16:55

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy