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

arXiv:0802.0232

Quantum mechanical NMR implementation of DNA algorithm for satisfiability problem

Ren, T. T., Mang Feng, Weng-Long Chang, Luo, J., Mingsheng Zhan

Published Feb 2, 2008• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.0802.0232

Related papers

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 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 logic synthesis for Satisfiability Problems.

Shuai Yang, Wei Zi, Bujiao Wu +3 more

To demonstrate the advantage of quantum computation, many attempts have been made to attack classically intractable problems, such as the satisfiability problem (SAT), with quantum computer. To use quantum algorithms to solve these NP-hard problems, a quantum oracle with quantum circuit implementation is usually required. In this manuscript, we first introduce a novel algorithm to synthesize quantum logic in the Conjunctive Normal Form (CNF) model. Compared with linear ancillary qubits in the implementation of Qiskit open-source framework, our algorithm can synthesize an m clauses n variables k-CNF with $O(k^2 m^2/n)$ quantum gates by only using three ancillary qubits. Both the size and depth of the circuit can be further compressed with the increase in the number of ancillary qubits. When the number of ancillary qubits is $\Omega(m^\epsilon)$ (for any $\epsilon > 0$), the size of the quantum circuit given by the algorithm is O(km), which is asymptotically optimal. Furthermore, we design another algorithm to optimize the depth of the quantum circuit with only a small increase in the size of the quantum circuit. Experiments show that our algorithms have great improvement in size and depth compared with the previous algorithms.

•Jan 14, 2021•1 citation

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

Multiple-Valued Quantum-DNA Computing

Hafiz Md. Hasan Babu

Quantum and DNA computing are both distributed and parallel types of computing. They're useful for tasks that require high-complexity computations and/or large data sets, such as searching, sorting, merging, pattern recognition, image processing, and encryption. Quantum and DNA algorithms cannot be efficiently simulated on classical computers because they are incapable of coping with parallelism. Quantum computers are more powerful than classical turing machines because of their coherent superposition of states. Biotechnology techniques can be used to evolve DNA computers. Both of these qualities could be captured by combining DNA and quantum computers. Self-assembling quantum logic circuits from gates attached to DNA strands could be achieved using DNA computers. In terms of how inputs are given and outputs are generated, multiple-valued Quantum and DNA computing can be combined in two ways. They can be named as: Multiple-Valued Quantum-DNA Computing, and Multiple-Valued DNA-Quantum Computing.

CRC Press eBooks•Aug 29, 2023•0 citations
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.
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.
To demonstrate the advantage of quantum computation, many attempts have been made to attack classically intractable problems, such as the satisfiability problem (SAT), with quantum computer. To use quantum algorithms to solve these NP-hard problems, a quantum oracle with quantum circuit implementation is usually required. In this manuscript, we first introduce a novel algorithm to synthesize quantum logic in the Conjunctive Normal Form (CNF) model. Compared with linear ancillary qubits in the implementation of Qiskit open-source framework, our algorithm can synthesize an m clauses n variables k-CNF with O(k2m2/n)O(k^2 m^2/n)O(k2m2/n) quantum gates by only using three ancillary qubits. Both the size and depth of the circuit can be further compressed with the increase in the number of ancillary qubits. When the number of ancillary qubits is Ω(mϵ)\Omega(m^\epsilon)Ω(mϵ) (for any ϵ>0\epsilon > 0ϵ>0), the size of the quantum circuit given by the algorithm is O(km), which is asymptotically optimal. Furthermore, we design another algorithm to optimize the depth of the quantum circuit with only a small increase in the size of the quantum circuit. Experiments show that our algorithms have great improvement in size and depth compared with the previous algorithms.
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.
Quantum and DNA computing are both distributed and parallel types of computing. They're useful for tasks that require high-complexity computations and/or large data sets, such as searching, sorting, merging, pattern recognition, image processing, and encryption. Quantum and DNA algorithms cannot be efficiently simulated on classical computers because they are incapable of coping with parallelism. Quantum computers are more powerful than classical turing machines because of their coherent superposition of states. Biotechnology techniques can be used to evolve DNA computers. Both of these qualities could be captured by combining DNA and quantum computers. Self-assembling quantum logic circuits from gates attached to DNA strands could be achieved using DNA computers. In terms of how inputs are given and outputs are generated, multiple-valued Quantum and DNA computing can be combined in two ways. They can be named as: Multiple-Valued Quantum-DNA Computing, and Multiple-Valued DNA-Quantum Computing.