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

Elsevier eBooks

A Formalism for Quantum Computing and a Satisfiability Problem

César Bautista-Ramos, M. Castro-Cardona, Alfred Zehe

Published Jan 1, 2005• 0 citations
Publisher
DOI
10.1016/b978-008044648-6.50046-x

Related papers

Programming Complex Systems

Philip Z. Maymin

Classical programming languages cannot model essential elements of complex systems such as true random number generation. This paper develops a formal programming language called the lambda-q calculus that addresses the fundamental properties of complex systems. This formal language allows the expression of quantumized algorithms, which are extensions of randomized algorithms in that probabilities can be negative, and events can cancel out. An illustration of the power of quantumized algorithms is the ability to efficiently solve the satisfiability problem, something that many believe is beyond the capability of classical computers. This paper proves that the lambda-q calculus is not only capable of solving satisfiability but can also simulate such complex systems as quantum computers. Since satisfiability is believed to be beyond the capabilities of quantum computers, the lambda-q calculus may be strictly stronger.

arXiv:quant-ph/9710035•Oct 15, 1997•3 citations

On the Study of Quantum Computing

Myo Myo Aung

•Oct 30, 2019•0 citations

Theory of Quantum Computing and its Analog of the Halting Problem

Andrii Hopanchuk

•Jan 1, 2025•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

A Formal Analysis of Quantum Algorithms

Benoît Valiron

•Jan 1, 2018•0 citations

Quantum 3-SAT Is QMA1-Complete

David Gosset, Daniel Nagaj

Quantum satisfiability is a constraint satisfaction problem that generalizes classical boolean satisfiability. In the quantum k-SAT problem, each constraint is specified by a k-local projector and is satisfied by any state in its nullspace. Bravyi showed that quantum 2-SAT can be solved efficiently on a classical computer and that quantum k-SAT with k ≥ 4 is QMA1-complete [4]. Quantum 3-SAT was known to be contained in QMA1[4], but its computational hardness was unknown until now. We prove that quantum 3-SAT is QMA1-hard, and therefore complete for this complexity class.

arXiv:1302.0290•Annual Symposium on Foundations of Computer Science•Oct 1, 2013•42 citations
Classical programming languages cannot model essential elements of complex systems such as true random number generation. This paper develops a formal programming language called the lambda-q calculus that addresses the fundamental properties of complex systems. This formal language allows the expression of quantumized algorithms, which are extensions of randomized algorithms in that probabilities can be negative, and events can cancel out. An illustration of the power of quantumized algorithms is the ability to efficiently solve the satisfiability problem, something that many believe is beyond the capability of classical computers. This paper proves that the lambda-q calculus is not only capable of solving satisfiability but can also simulate such complex systems as quantum computers. Since satisfiability is believed to be beyond the capabilities of quantum computers, the lambda-q calculus may be strictly stronger.
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.
Quantum satisfiability is a constraint satisfaction problem that generalizes classical boolean satisfiability. In the quantum k-SAT problem, each constraint is specified by a k-local projector and is satisfied by any state in its nullspace. Bravyi showed that quantum 2-SAT can be solved efficiently on a classical computer and that quantum k-SAT with k ≥ 4 is QMA1-complete [4]. Quantum 3-SAT was known to be contained in QMA1[4], but its computational hardness was unknown until now. We prove that quantum 3-SAT is QMA1-hard, and therefore complete for this complexity class.