Schoening's algorithm for 3SAT can be converted to a quantum algorithm.  The classical circuit representing a 3SAT expression in CNF form can be converted to a quantum version involving reversible unitary gates and a lot of ancillary qubits. Flipping a variable (if the clause is not satisfied) can be done using CNOT, CCNOT, CCCNOT gates properly placed (also involving ancillary qubits ). The random choices that the algorithm makes can be implemented by "flipping a coin " and choosing what branches of the large quantum circuit to be activated at a given stage of the computation.  In principle I see no problem in the implementation. 

A related approach can be found  here

Two simplistic computations involving simple expressions with 1-clauses and 2-clauses are described here (in order to see what I'm looking for ):

first simplistic sample computation

second simplistic sample computation

Note that at each step a lot of states are affected. In terms of classical truth assignments it's like running a lot of classical Schoening algorithms in parallel. I am not talking about applying Grover's algorithm for 3SAT, I am thinking about translating Schoning's algorithm into a quantum algorithm.

Question.  Have these types of algorithms been studied extensively, in order to assess their efficiency? What are the known results in this direction,  and the open problems? More importantly (this is the main question), could anyone provide a proof that these algorithms are not polynomial?

  • $\begingroup$ This cstheory.stackexchange question might be interesting to you. $\endgroup$
    – smapers
    Commented Aug 25, 2020 at 8:02


Your Answer

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