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.
Download full-text PDF |
Source |
|---|---|
| http://dx.doi.org/10.1109/TNB.2008.2002286 | DOI Listing |
Publication Analysis
Top Keywords
Similar Publications
An Exact and Fast SAT Formulation for the DCJ Distance.
bioRxiv
November 2024
Department of Computer Science and Engineering, The Pennsylvania State University, University Park, PA 16802, USA.
Reducing into a satisfiability (SAT) formulation has been proven effective in solving certain NP-hard problems. In this work, we extend this research by presenting a novel SAT formulation for computing the double-cut-and-join (DCJ) distance between two genomes with duplicate genes. The DCJ distance serves as a crucial metric in studying genome rearrangement.
View Article and Find Full Text PDFSolving the B-SAT Problem Using Quantum Computing: Smaller Is Sometimes Better.
Entropy (Basel)
October 2024
Department of Electrical and Computer Engineering, North Carolina State University, Raleigh, NC 27695, USA.
This paper aims to outline the effectiveness of modern universal gate quantum computers when utilizing different configurations to solve the B-SAT (Boolean satisfiability) problem. The quantum computing experiments were performed using Grover's search algorithm to find a valid solution. The experiments were performed under different variations to demonstrate their effects on the results.
View Article and Find Full Text PDFCounting the number of solutions in satisfiability problems with tensor-network message passing.
Phys Rev E
September 2024
School of Fundamental Physics and Mathematical Sciences, Hangzhou Institute for Advanced Study, UCAS, Hangzhou 310024, China.
Article Synopsis
- - This research focuses on counting the solutions to the Boolean satisfiability (SAT) problem, a crucial topic in theoretical computer science with various real-world applications.
- - The authors transform this counting problem into a spin-glass problem from statistical physics and develop a new method to compute entropy, which represents the number of solutions, using tensor networks and message-passing algorithms.
- - Their method effectively handles both long and short loops in the SAT problem's factor graph, showing improved accuracy over traditional algorithms, and they validate their approach on random and structured 3-SAT problems with potential applications in combinatorial optimization.
All-to-all reconfigurability with sparse and higher-order Ising machines.
Nat Commun
October 2024
Department of Electrical and Computer Engineering, University of California, Santa Barbara, Santa Barbara, CA, 93106, USA.
Domain-specific hardware to solve computationally hard optimization problems has generated tremendous excitement. Here, we evaluate probabilistic bit (p-bit) based Ising Machines (IM) on the 3-Regular 3-Exclusive OR Satisfiability (3R3X), as a representative hard optimization problem. We first introduce a multiplexed architecture that emulates all-to-all network functionality while maintaining highly parallelized chromatic Gibbs sampling.
View Article and Find Full Text PDFComputing high-degree polynomial gradients in memory.
Nat Commun
September 2024
Department of Electrical and Computer Engineering, University of California at Santa Barbara, Santa Barbara, CA, USA.
Specialized function gradient computing hardware could greatly improve the performance of state-of-the-art optimization algorithms. Prior work on such hardware, performed in the context of Ising Machines and related concepts, is limited to quadratic polynomials and not scalable to commonly used higher-order functions. Here, we propose an approach for massively parallel gradient calculations of high-degree polynomials, which is conducive to efficient mixed-signal in-memory computing circuit implementations and whose area scales proportionally with the product of the number of variables and terms in the function and, most importantly, independent of its degree.
View Article and Find Full Text PDFWant AI Summaries of new PubMed Abstracts delivered to your In-box?
Enter search terms and have AI summaries delivered each week - change queries or unsubscribe any time!