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?
