Are there quantum algorithms that solve the boolean satisfiability problem in subexponential time? Do they just give a determination as to whether an expression can ever evaluate to true, or can they also tell which input will cause the expression to evaluate to true?

  • 1
    $\begingroup$ Quantumness is thought to give at most quadratic speedup. I don't think any quantum SAT algorithm with superpolynomial speedup is known. However, proving that there does not exist one is even harder than proving ETH. $\endgroup$ – rus9384 Oct 10 '17 at 7:07
  • $\begingroup$ @rus9384 This is not true. Quantumness is though to give exponential speedup, e.g. in the case of factoring/discrete log. $\endgroup$ – Ariel Oct 10 '17 at 8:12
  • $\begingroup$ @Ariel, I meant in worst case. $\endgroup$ – rus9384 Oct 10 '17 at 8:29
  • $\begingroup$ so did I (need more characters) $\endgroup$ – Ariel Oct 10 '17 at 8:57
  • $\begingroup$ The answer to the second part of your question is implied by the first. For each variable, set that variable's value to whether the system is solvable when that variable is true and already-considered variables are set to their respective values. $\endgroup$ – Craig Gidney Oct 11 '17 at 1:52

Your Answer

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

Browse other questions tagged or ask your own question.