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 Congress on Evolutionary Computation (CEC)

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

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

Published Jun 1, 2008• 0 citations
Publisher

Abstract

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.

DOI
10.1109/cec.2008.4630931

Related papers

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 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 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 of Bio-molecular Solutions for the Clique Problem on a Quantum Computer

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

In this paper, it is demonstrated that the DNA-based algorithm [Ho et al. 2005] for solving an instance of the clique problem to any a graph G = (V, E) with n vertices and p edges and its complementary graph G1 = (V, E1) with n vertices and m = (((n*(n-1))/2)-p) edges can be implemented by Hadamard gates, NOT gates, CNOT gates, CCNOT gates, Grover's operators, and quantum measurements on a quantum computer. It is also demonstrated that if Grovers algorithm is employed to accomplish the readout step in the DNA-based algorithm, the quantum implementation of the DNA-based algorithm is equivalent to the oracle work (in the language of Grover's algorithm), that is, the target state labeling preceding Grover,s searching steps. It is shown that one oracle work can be completed with O((2 * n) * (n + 1) * (n + 2) / 3) NOT gates, one CNOT gate and O((4 * m) + (((2 * n) * (n + 1) * (n + 14)) / 6)) CCNOT gates. This is to say that for the quantum implementation of the DNA-based algorithm [Ho et al. 2005] a faster labeling of the target state is attained, which also implies a speedy solution to an instance of the clique problem.

arXiv:0905.2028•May 13, 2009•0 citations

Quantum Algorithms and Mathematical Representation of Bio-molecular Solutions for the Clique Problem in a Finite-dimensional Hilbert Space

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

In this paper, it is demonstrated that the DNA-based algorithm [Ho et al. 2005] for solving an instance of the clique problem to any a graph G = (V, E) with n vertices and q edges and its complementary graph = (V, ) with n vertices and m = (((n * (n - 1)) / 2) - q) edges can be implemented by Hadamard gates, NOT gates, CNOT gates, CCNOT gates, Grover's operators, and quantum measurements on a quantum computer.

International Conference on Computational Aspects of Social Networks (CASoN)•Sep 1, 2010•0 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
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 (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.
In this paper, it is demonstrated that the DNA-based algorithm [Ho et al. 2005] for solving an instance of the clique problem to any a graph G = (V, E) with n vertices and p edges and its complementary graph G1 = (V, E1) with n vertices and m = (((n*(n-1))/2)-p) edges can be implemented by Hadamard gates, NOT gates, CNOT gates, CCNOT gates, Grover's operators, and quantum measurements on a quantum computer. It is also demonstrated that if Grovers algorithm is employed to accomplish the readout step in the DNA-based algorithm, the quantum implementation of the DNA-based algorithm is equivalent to the oracle work (in the language of Grover's algorithm), that is, the target state labeling preceding Grover,s searching steps. It is shown that one oracle work can be completed with O((2 * n) * (n + 1) * (n + 2) / 3) NOT gates, one CNOT gate and O((4 * m) + (((2 * n) * (n + 1) * (n + 14)) / 6)) CCNOT gates. This is to say that for the quantum implementation of the DNA-based algorithm [Ho et al. 2005] a faster labeling of the target state is attained, which also implies a speedy solution to an instance of the clique problem.