Performance of a measurement-driven 'adiabatic-like' quantum 3-SAT solver

I describe one quantum approach to solving 3-satisfiability (3-SAT), the well known problem in computer science. The approach is based on repeatedly measuring the truth value of the clauses forming the 3-SAT proposition using a non-orthogonal basis. If the basis slowly evolves then there is a strong analogy to adiabatic quantum computing, although the approach is entirely circuit-based. To solve a 3-SAT problem of n variables requires a quantum register of $n$ qubits, or more precisely rebits i.e. qubits whose phase need only be real. For cases of up to n=26 qubits numerical simulations indicate that the algorithm runs fast, outperforming Grover's algorithm and having a scaling with n that is superior to the best reported classical algorithms. There are indications that the approach has an inherent robustness versus imperfections in the elementary operations.

No reviews yet.

No comments yet.