3 ms·
Can somebody comment, if this actually means that one can essentially solve SAT with a quantum computer? In particular: The algorithm prepares a superposit
by yk 11y ago
Can somebody comment, if this actually means that one can essentially solve SAT with a quantum computer? In particular:
The algorithm prepares a superposition of all possible
variable assignments, then the algorithm evaluates the
set of clauses using all the pos-sible variable
assignments simultaneously and then amplifies the
amplitudes of the state(s) that achieve(s) the maximum
satisfaction to the set of clauses using a novel
amplitude amplification technique that applies an
iterative partial nega-tion and partial measurement.
This sounds a bit like hiding some runtime in 'partial measurement.' ( But I did only read the introduction yet, and I don't understand quantum computers.)
- sanxiyn 11y agoI am not sure whether this works, but the paper's statement does actually mean that one can solve SAT in polynomial time with high probability with a quantum computer.
- andrelaszlo 11y agoAn "arbitrary [sic] high probability" even. If I got it right.
- sanxiyn 11y agoYup, arbitrarily high probability.
- zitterbewegung 11y agoTo understand this paper you should read about this problem which they cite in the paper. https://en.wikipedia.org/wiki/MAXEkSAT https://en.wikipedia.org/wiki/MAXEkSAT They are attempting to solve the problem for k=3 and then probably figure out how to run the approximation algorithm for this problem on a quantum computer.