Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Chinese Physics B

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

Ren Ting-Ting, Feng Mang, Weng-Long Chang, Luo Jun

Published Dec 1, 2009• 0 citations
Publisher

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.

DOI
10.1088/1674-1056/18/12/013

Related papers

Quantum mechanical NMR implementation of DNA algorithm for satisfiability problem

Ren, T. T., Mang Feng, Weng-Long Chang +2 more

DNA computation could in principle solve the satisfiability (SAT) problem due to the operations in parallel on extremely large numbers of strands. We demonstrate some quantum gates corresponding to the DNA ones, based on which an implementation of DNA algorithm for SAT problem is available by quantum mechanical way. Since quantum computation owns the favorable feature of operations in parallel on 2$^{n}$ states by using only n qubits, instead of 2$^{n}$ strands in DNA computation, computational complexity is much reduced in treating the SAT problem quantum mechanically. We take a three-clause SAT problem with two variables as an example, and carry out a NMR experiment for solving a one-variable SAT problem.

arXiv:0802.0232•Feb 2, 2008•0 citations

Quantum algorithms for bio-molecular solutions to the satisfiability problem on a quantum computer

Weng-Long Chang, Ting-Ting Ren, Jun Luo +2 more

We demonstrate that the logic computation performed by the DNA-based algorithm for solving general cases of the satisfiability problem can be implemented by our proposed quantum algorithm on the quantum machine proposed by Deutsch. Moreover, we also prove that the logic computation by the bio-molecular operations proposed by Adleman can be implemented by quantum gates (for example, the Hadamard gate, NOT, CNOT, and CCNOT) on the quantum machine. Furthermore, those NP-complete problems solved on a bio-molecular computer are also solvable on a quantum computer. To test our theory, we carry out a three-qubit NMR experiment for solving the simplest satisfiability problem.

IEEE Congress on Evolutionary Computation (CEC)•Jun 1, 2008•0 citations

Quantum Algorithms for Biomolecular Solutions of the Satisfiability Problem on a Quantum Machine

Weng-Long Chang, Ting-Ting Ren, J. L. Luo +3 more

In this paper, we demonstrate that the logic computation performed by the DNA-based algorithm for solving general cases of the satisfiability problem can be implemented more efficiently by our proposed quantum algorithm on the quantum machine proposed by Deutsch. To test our theory, we carry out a three-quantum bit nuclear magnetic resonance experiment for solving the simplest satisfiability problem.

IEEE Transactions on NanoBioscience•Sep 1, 2008•21 citations

Quantum Algorithms and Mathematical Representation of Bio-molecular Solutions for the Hitting-set Problem on a Quantum Computer

Weng-Long Chang, Ting-Ting Ren, Mang Feng +6 more

In this paper, it is demonstrated that quantum implementation of bio-molecular solutions to compute the number of elements in each hitting-set in an instance of the hitting-set problem could be considered as the oracle work in Grover's algorithm, i.e., the target state labeling, preceding Grover's searching steps. Finally, for testing our theory, a three-qubit nuclear magnetic resonance (NMR) experiment of solving the simplest hitting-set problem is performed.

International Conference on Computational Aspects of Social Networks (CASoN)•Sep 1, 2010•0 citations

Deterministic Storage of Quantum Information in the Genetic Code

Roberto Rivelino

DNA has been proposed as a chemical platform for computing and data storage, paving the way for building DNA-based computers. Recently, DNA has been hypothesized as an ideal quantum computer with the base pairs working as Josephson junctions. There are still major challenges to be overcome in these directions, but they do not prevent deviceful perspectives of the main problem. The present paper explores DNA base pairs as elementary units for a scalable nuclear magnetic resonance quantum computer (NMRQC). First, it presents an overview of the proton transfer (PT) mechanism during the prototropic tautomerism in the base pairs, scoring the current stage. Second, as a proof-of-principle, the paper examines these molecular structures as quantum processing units (QPUs) of a biochemical quantum device. For the model proposed here, it is theoretically demonstrated that the nuclear spins involved in the PT of base pairs can be deterministically prepared in a superposition of triplet states. Under appropriate conditions, the proton dynamics provides the minimal two-qubit entanglement required for quantum computing. The dynamics between the canonical and tautomeric quantum states (CQS and TQS, respectively) is determined from a thermally dependent Watson-Crick quantum superposition (WCQS); i.e., |WCQS> = a(T)|CQS> + b(T)|TQS> with |a(T)|^2 + |b(T)|^2 = 1. If the DNA structure is sufficiently protected to avoid environment-induced decoherence of the confined-proton quantum states, quantum information can be successfully encoded in several base pairs along the coiled double strand. As a potential applicability, a crystalline DNA device could be employed for quantum computing and cryptography controlled by a sequence of Ramsey pulses. Finally, this study critically evaluates these possibilities toward a proof-of-concept of a DNA-based quantum computer.

arXiv:2412.07504•Dec 10, 2024•0 citations

Implementation for Solving Random Satisfiability Problems through CNOT-based circuits in a NMR Quantum Processor

Xinhua Peng, Xiwen Zhu, Kelin Gao

We give a general method of construting quantum circuit for random \QTR{it}{satisfiability} (SAT) problems with the basic logic gates such as multi-qubit controlled-NOT and NOT gates. The sizes of these circuits are almost the same as the sizes of the SAT formulas. Further, a parallelization scheme is described to solve random SAT problems efficiently through these quantum circuits in \QTR{it}{nuclear magnetic resonance} (NMR) ensemble quantum computing. This scheme exploits truly mixed states as input states rather than pseudo-pure states, and combines with the topological nanture of the NMR spectrum to identify the solutions to SAT problems in a parallel way. Several typical SAT problems have been experimentally demonstrated by this scheme with good performances.

arXiv:quant-ph/0308130•Aug 25, 2003•0 citations
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.
DNA computation could in principle solve the satisfiability (SAT) problem due to the operations in parallel on extremely large numbers of strands. We demonstrate some quantum gates corresponding to the DNA ones, based on which an implementation of DNA algorithm for SAT problem is available by quantum mechanical way. Since quantum computation owns the favorable feature of operations in parallel on 2n^{n}n states by using only n qubits, instead of 2n^{n}n strands in DNA computation, computational complexity is much reduced in treating the SAT problem quantum mechanically. We take a three-clause SAT problem with two variables as an example, and carry out a NMR experiment for solving a one-variable SAT problem.
We demonstrate that the logic computation performed by the DNA-based algorithm for solving general cases of the satisfiability problem can be implemented by our proposed quantum algorithm on the quantum machine proposed by Deutsch. Moreover, we also prove that the logic computation by the bio-molecular operations proposed by Adleman can be implemented by quantum gates (for example, the Hadamard gate, NOT, CNOT, and CCNOT) on the quantum machine. Furthermore, those NP-complete problems solved on a bio-molecular computer are also solvable on a quantum computer. To test our theory, we carry out a three-qubit NMR experiment for solving the simplest satisfiability problem.
DNA has been proposed as a chemical platform for computing and data storage, paving the way for building DNA-based computers. Recently, DNA has been hypothesized as an ideal quantum computer with the base pairs working as Josephson junctions. There are still major challenges to be overcome in these directions, but they do not prevent deviceful perspectives of the main problem. The present paper explores DNA base pairs as elementary units for a scalable nuclear magnetic resonance quantum computer (NMRQC). First, it presents an overview of the proton transfer (PT) mechanism during the prototropic tautomerism in the base pairs, scoring the current stage. Second, as a proof-of-principle, the paper examines these molecular structures as quantum processing units (QPUs) of a biochemical quantum device. For the model proposed here, it is theoretically demonstrated that the nuclear spins involved in the PT of base pairs can be deterministically prepared in a superposition of triplet states. Under appropriate conditions, the proton dynamics provides the minimal two-qubit entanglement required for quantum computing. The dynamics between the canonical and tautomeric quantum states (CQS and TQS, respectively) is determined from a thermally dependent Watson-Crick quantum superposition (WCQS); i.e., |WCQS> = a(T)|CQS> + b(T)|TQS> with |a(T)|^2 + |b(T)|^2 = 1. If the DNA structure is sufficiently protected to avoid environment-induced decoherence of the confined-proton quantum states, quantum information can be successfully encoded in several base pairs along the coiled double strand. As a potential applicability, a crystalline DNA device could be employed for quantum computing and cryptography controlled by a sequence of Ramsey pulses. Finally, this study critically evaluates these possibilities toward a proof-of-concept of a DNA-based quantum computer.
We give a general method of construting quantum circuit for random \QTR{it}{satisfiability} (SAT) problems with the basic logic gates such as multi-qubit controlled-NOT and NOT gates. The sizes of these circuits are almost the same as the sizes of the SAT formulas. Further, a parallelization scheme is described to solve random SAT problems efficiently through these quantum circuits in \QTR{it}{nuclear magnetic resonance} (NMR) ensemble quantum computing. This scheme exploits truly mixed states as input states rather than pseudo-pure states, and combines with the topological nanture of the NMR spectrum to identify the solutions to SAT problems in a parallel way. Several typical SAT problems have been experimentally demonstrated by this scheme with good performances.