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?
$\begingroup$
$\endgroup$
5
-
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$– rus9384Commented Oct 10, 2017 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$– ArielCommented Oct 10, 2017 at 8:12
-
$\begingroup$ @Ariel, I meant in worst case. $\endgroup$– rus9384Commented Oct 10, 2017 at 8:29
-
$\begingroup$ so did I (need more characters) $\endgroup$– ArielCommented Oct 10, 2017 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 GidneyCommented Oct 11, 2017 at 1:52
Add a comment
|