Please wait a minute...
Chin. Phys. B, 2009, Vol. 18(12): 5173-5178    DOI: 10.1088/1674-1056/18/12/013
GENERAL Prev   Next  

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)
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
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.
Keywords:  DNA computation      liquid-state nuclear magnetic resonance      SAT problem      quantum computation  
Received:  07 October 2008      Revised:  29 June 2009      Accepted manuscript online: 
PACS:  87.14.G- (Nucleic acids)  
  03.67.Lx (Quantum computation architectures and implementations)  
  87.15.A- (Theory, modeling, and computer simulation)  
Fund: 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).

Cite this article: 

Ren Ting-Ting(任婷婷),Feng Mang(冯芒), Chang Weng-Long(张云龙), and Luo Jun(罗军) Quantum demonstration of a bio-molecular solution of the satisfiability problem on spin-based ensemble 2009 Chin. Phys. B 18 5173

[1] High-fidelity universal quantum gates for hybrid systems via the practical photon scattering
Jun-Wen Luo(罗竣文) and Guan-Yu Wang(王冠玉). Chin. Phys. B, 2023, 32(3): 030303.
[2] Analysis and improvement of verifiable blind quantum computation
Min Xiao(肖敏) and Yannan Zhang(张艳南). Chin. Phys. B, 2022, 31(5): 050305.
[3] Optimized quantum singular value thresholding algorithm based on a hybrid quantum computer
Yangyang Ge(葛阳阳), Zhimin Wang(王治旻), Wen Zheng(郑文), Yu Zhang(张钰), Xiangmin Yu(喻祥敏), Renjie Kang(康人杰), Wei Xin(辛蔚), Dong Lan(兰栋), Jie Zhao(赵杰), Xinsheng Tan(谭新生), Shaoxiong Li(李邵雄), and Yang Yu(于扬). Chin. Phys. B, 2022, 31(4): 048704.
[4] Molecular beam epitaxy growth of quantum devices
Ke He(何珂). Chin. Phys. B, 2022, 31(12): 126804.
[5] Quantum simulation and quantum computation of noisy-intermediate scale
Kai Xu(许凯), and Heng Fan(范桁). Chin. Phys. B, 2022, 31(10): 100304.
[6] Quantum computation and simulation with superconducting qubits
Kaiyong He(何楷泳), Xiao Geng(耿霄), Rutian Huang(黄汝田), Jianshe Liu(刘建设), and Wei Chen(陈炜). Chin. Phys. B, 2021, 30(8): 080304.
[7] Quantum computation and simulation with vibrational modes of trapped ions
Wentao Chen(陈文涛), Jaren Gan, Jing-Ning Zhang(张静宁), Dzmitry Matuskevich, and Kihwan Kim(金奇奂). Chin. Phys. B, 2021, 30(6): 060311.
[8] Quantum computation and error correction based on continuous variable cluster states
Shuhong Hao(郝树宏), Xiaowei Deng(邓晓玮), Yang Liu(刘阳), Xiaolong Su(苏晓龙), Changde Xie(谢常德), and Kunchi Peng(彭堃墀). Chin. Phys. B, 2021, 30(6): 060312.
[9] Realization of arbitrary two-qubit quantum gates based on chiral Majorana fermions
Qing Yan(闫青) and Qing-Feng Sun(孙庆丰). Chin. Phys. B, 2021, 30(4): 040303.
[10] Efficient self-testing system for quantum computations based on permutations
Shuquan Ma(马树泉), Changhua Zhu(朱畅华), Min Nie(聂敏), and Dongxiao Quan(权东晓). Chin. Phys. B, 2021, 30(4): 040305.
[11] Quantum algorithm for a set of quantum 2SAT problems
Yanglin Hu(胡杨林), Zhelun Zhang(张哲伦), and Biao Wu(吴飙). Chin. Phys. B, 2021, 30(2): 020308.
[12] Low-temperature environments for quantum computation and quantum simulation
Hailong Fu(付海龙), Pengjie Wang(王鹏捷), Zhenhai Hu(胡禛海), Yifan Li(李亦璠), and Xi Lin(林熙). Chin. Phys. B, 2021, 30(2): 020702.
[13] A concise review of Rydberg atom based quantum computation and quantum simulation
Xiaoling Wu(吴晓凌), Xinhui Liang(梁昕晖), Yaoqi Tian(田曜齐), Fan Yang(杨帆), Cheng Chen(陈丞), Yong-Chun Liu(刘永椿), Meng Khoon Tey(郑盟锟), and Li You(尤力). Chin. Phys. B, 2021, 30(2): 020305.
[14] Quantum adiabatic algorithms using unitary interpolation
Shuo Zhang(张硕), Qian-Heng Duan(段乾恒), Tan Li(李坦), Xiang-Qun Fu(付向群), He-Liang Huang(黄合良), Xiang Wang(汪翔), Wan-Su Bao(鲍皖苏). Chin. Phys. B, 2020, 29(1): 010308.
[15] Novel quantum secret image sharing scheme
Gao-Feng Luo(罗高峰), Ri-Gui Zhou(周日贵), Wen-Wen Hu(胡文文). Chin. Phys. B, 2019, 28(4): 040302.
No Suggested Reading articles found!