中国物理B ›› 2009, Vol. 18 ›› Issue (12): 5173-5178.doi: 10.1088/1674-1056/18/12/013

• • 上一篇    下一篇

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

张云龙1, 冯芒2, 罗军3, 任婷婷4   

  1. (1)Department of Computer Science and Information Engineering, National Kaohsiung University of Applied Sciences, Kaohsiung 80778, China; (2)State Key Laboratory of Magnetic Resonance and Atomic and Molecular Physics, Wuhan Institute of Physics and Mathematics, the Chinese Academy of Sciences, Wuhan 430071, China; (3)State Key Laboratory of Magnetic Resonance and Atomic and Molecular Physics, Wuhan Institute of Physics and Mathematics, the Chinese Academy of Sciences, Wuhan 430071, China \addressb)Center for Cold Atom Physics, the Chinese Academy of Sciences, Wuhan ; (4)State Key Laboratory of Magnetic Resonance and Atomic and Molecular Physics, Wuhan Institute of Physics and Mathematics, the Chinese Academy of Sciences, Wuhan 430071, China;Center for Cold Atom Physics, the Chinese Academy of Sciences, Wuhan 430071, Ch
  • 收稿日期:2008-10-07 修回日期:2009-06-29 出版日期:2009-12-20 发布日期:2009-12-20
  • 基金资助:
    Project supported by the National Natural Science Foundation of China (Grant Nos 10774163 and 10574143), and the National Basic Research Program of China (Grant No 2006CB921203).

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

Ren Ting-Ting(任婷婷)a)b)c),Feng Mang(冯芒) a)†, Chang Weng-Long(张云龙)d), and Luo Jun(罗军)a)b)   

  1. a State Key Laboratory of Magnetic Resonance and Atomic and Molecular Physics, Wuhan Institute of Physics and Mathematics, the Chinese Academy of Sciences, Wuhan 430071, China; b Center for Cold Atom Physics, the Chinese Academy of Sciences, Wuhan 430071, China; c Graduate School of the Chinese Academy of Sciences, Beijing 100049, China; d Department of Computer Science and Information Engineering, National Kaohsiung University of Applied Sciences, Kaohsiung 80778, China
  • Received:2008-10-07 Revised:2009-06-29 Online:2009-12-20 Published:2009-12-20
  • Supported by:
    Project supported by the National Natural Science Foundation of China (Grant Nos 10774163 and 10574143), and the National Basic Research Program of China (Grant No 2006CB921203).

PDF (PC)

523

赞

摘要： 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.

Abstract: 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.

Key words: DNA computation, liquid-state nuclear magnetic resonance, SAT problem, quantum computation

中图分类号:  (Nucleic acids)

  • 87.14.G-
03.67.Lx (Quantum computation architectures and implementations) 87.15.A- (Theory, modeling, and computer simulation)