In this paper, a quantum algorithm to solve the 3-SAT problem in linear time is presented. Is it true? Did the author make a mistake? What state-of-the-art algorithms exist for this problem?

  • $\begingroup$ Welcome to SE.Cryptography! You might want to check out SE.QuantumComputing. $\endgroup$
    – Nat
    Jun 16, 2019 at 8:58

1 Answer 1


I do not know if the result is true, since I did not check it, but note that this algorithm is not in the standard model of quantum computation. As the author himself put it:

The Deutsch model of quantum computation is extended to allow for thermodynamically irreversible operations by allowing the system of interest to interact with an outside reservoir. A set of irreversible logical error correction superoperators are constructed which allow the rapid concentration of probability from an exponentially large search space into a small number of logically defined states. These capabilities are used to construct a linear time solution algorithm for the NP complete problem 3SAT.

Therefore, this result, if true, simply says that in an appropriate extended model of quantum computation, there exists an algorithm that solves 3SAT in linear time. This does not prove BQP = NP (which would be a major breakthrough), nor is it clear whether this model has any concrete value - put otherwise, it is not an algorithm that a quantum computer, if it is ever build and runs as quantum computation experts expect it should run, could ever run.

A few additional notes: algorithms that solve NP-complete problems in extended models of computation are well-known, people have long investigated closed timelike curves, post-selection in quantum computation, and other appropriate modifications of the standard model of quantum computation. More often than not, these modifications make the model much more powerful, able to evaluate much more complex functions (indeed, studying how specific variations of the model deeply change its computational power is one of the ways some researchers use, e.g. Scott Aaronson to name only one, to understand the exact boundaries of BQP). Note also that the paper you link was added to ArXiv in 2015 and, as far as I can see, was never published anywhere - so it does not seem unlikely that it either contains a mistake, or the alternative model investigated there was not judged realistic, useful or interesting by the reviewers.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.