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 solu...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.展开更多
We present a quantum adiabatic algorithm for a set of quantum 2-satisfiability(Q2SAT)problem,which is a generalization of 2-satisfiability(2SAT)problem.For a Q2SAT problem,we construct the Hamiltonian which is similar...We present a quantum adiabatic algorithm for a set of quantum 2-satisfiability(Q2SAT)problem,which is a generalization of 2-satisfiability(2SAT)problem.For a Q2SAT problem,we construct the Hamiltonian which is similar to that of a Heisenberg chain.All the solutions of the given Q2SAT problem span the subspace of the degenerate ground states.The Hamiltonian is adiabatically evolved so that the system stays in the degenerate subspace.Our numerical results suggest that the time complexity of our algorithm is O(n^(3.9))for yielding non-trivial solutions for problems with the number of clauses m=dn(n-1)/2(d■0.1).We discuss the advantages of our algorithm over the known quantum and classical algorithms.展开更多
基金Project supported by the National Natural Science Foundation of China (Grant Nos 10774163 and 10574143)the National Basic Research Program of China (Grant No 2006CB921203)
文摘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.
基金Project supported by the National Key R&D Program of China(Grant Nos.2017YFA0303302 and 2018YFA0305602)the National Natural Science Foundation of China(Grant No.11921005)Shanghai Municipal Science and Technology Major Project,China(Grant No.2019SHZDZX01)。
文摘We present a quantum adiabatic algorithm for a set of quantum 2-satisfiability(Q2SAT)problem,which is a generalization of 2-satisfiability(2SAT)problem.For a Q2SAT problem,we construct the Hamiltonian which is similar to that of a Heisenberg chain.All the solutions of the given Q2SAT problem span the subspace of the degenerate ground states.The Hamiltonian is adiabatically evolved so that the system stays in the degenerate subspace.Our numerical results suggest that the time complexity of our algorithm is O(n^(3.9))for yielding non-trivial solutions for problems with the number of clauses m=dn(n-1)/2(d■0.1).We discuss the advantages of our algorithm over the known quantum and classical algorithms.
