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

IEEE Transactions on NanoBioscience

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

Weng-Long Chang, Ting-Ting Ren, J. L. Luo, Mang Feng, Minyi Guo, Kawuu W. Lin

Published Sep 1, 2008• 21 citations
Publisher

Abstract

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.

DOI
10.1109/tnb.2008.2002286

Related papers

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 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 demonstration of a bio-molecular solution of the satisfiability problem on spin-based ensemble

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

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.

Chinese Physics B•Dec 1, 2009•0 citations

Quantum Algorithms and Mathematical Formulations of Biomolecular Solutions of the Vertex Cover Problem in the Finite-Dimensional Hilbert Space

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

In this paper, it is shown that the proposed quantum algorithm for implementing Boolean circuits generated from the DNA-based algorithm solving the vertex-cover problem of any graph G with m edges and n vertices is the optimal quantum algorithm. Next, it is also demonstrated that mathematical solutions of the same biomolecular solutions are represented in terms of a unit vector in the finite-dimensional Hilbert space. Furthermore, for testing our theory, a nuclear magnetic resonance (NMR) experiment of three quantum bits to solve the simplest vertex-cover problem is completed.

IEEE Transactions on NanoBioscience•Dec 6, 2014•25 citations

Implementation of a quantum algorithm on a nuclear magnetic resonance quantum computer

J. A. Jones, M. Mosca

Quantum computing shows great promise for the solution of many difficult problems, such as the simulation of quantum systems and the factorization of large numbers. While the theory of quantum computing is fairly well understood, it has proved difficult to implement quantum computers in real physical systems. It has recently been shown that nuclear magnetic resonance (NMR) can be used to implement small quantum computers using the spin states of nuclei in carefully chosen small molecules. Here we demonstrate the use of a NMR quantum computer based on the pyrimidine base cytosine, and the implementation of a quantum algorithm to solve Deutsch’s problem (distinguishing between constant and balanced functions). This is the first successful implementation of a quantum algorithm on any physical system.

arXiv:quant-ph/9801027•The Journal of Chemical Physics•Aug 1, 1998•399 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
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.
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 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.
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.
In this paper, it is shown that the proposed quantum algorithm for implementing Boolean circuits generated from the DNA-based algorithm solving the vertex-cover problem of any graph G with m edges and n vertices is the optimal quantum algorithm. Next, it is also demonstrated that mathematical solutions of the same biomolecular solutions are represented in terms of a unit vector in the finite-dimensional Hilbert space. Furthermore, for testing our theory, a nuclear magnetic resonance (NMR) experiment of three quantum bits to solve the simplest vertex-cover problem is completed.
Quantum computing shows great promise for the solution of many difficult problems, such as the simulation of quantum systems and the factorization of large numbers. While the theory of quantum computing is fairly well understood, it has proved difficult to implement quantum computers in real physical systems. It has recently been shown that nuclear magnetic resonance (NMR) can be used to implement small quantum computers using the spin states of nuclei in carefully chosen small molecules. Here we demonstrate the use of a NMR quantum computer based on the pyrimidine base cytosine, and the implementation of a quantum algorithm to solve Deutsch’s problem (distinguishing between constant and balanced functions). This is the first successful implementation of a quantum algorithm on any physical system.