Quantum demonstration of a bio-molecular solution of the satisfiability problem on spin-based ensemble

摘要

DNA computation (DNAC) has been proposed to solve the satisfiability (SAT) problem due to operations in parallel on extremely large numbers of strands.This paper attempts to treat the DNA-based bio-molecular solution for the SAT problem from the quantum mechanical perspective with a purpose to explore the relationship between DNAC and quantum computation (QC).To achieve this goal,it first builds up the correspondence of operations between QC and DNAC.Then it gives an example for the case of two variables and three clauses for details of this theory.It also demonstrates a three-qubit experiment for solving the simplest SAT problem with a single variable on a liquid-state nuclear magnetic resonance ensemble to verify this theory.Some discussions are made for the potential application and for further exploration of the present work.