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

On A Quantum Proof Of The Equivalence of P And NP

Adewale Oluwasanmi

Published Nov 3, 2019• 0 citations
Publisher

Abstract

We present an algorithm, along with a correctness proof, for solving the 3 Satisfiability problem that is inspired by quantum mechanical principles and that runs in polynomial time with respect to the size of the input problem. Even though we term both our algorithm and its associated proof as quantum (for reasons which we will demonstrate), it is intended to be run on standard classical architecture. In the article, we posit that the 3 Satisfiability problem has an intrinsic complex quantum form that can be programmed in order to build a model of the solution space for satisfiable instances or show that such a model cannot be constructed. This yields surprising results on the ability for classical systems to abstractly simulate general quantum systems.

DOI
10.31224/osf.io/8ht2m

Related papers

Linear time algorithm for quantum 2SAT

Itai Arad, Miklós Sántha, Aarthi Sundaram +1 more

A canonical result about satisfiability theory is that the 2-SAT problem can be solved in linear time, despite the NP-hardness of the 3-SAT problem. In the quantum 2-SAT problem, we are given a family of 2-qubit projectors $Π_{ij}$ on a system of $n$ qubits, and the task is to decide whether the Hamiltonian $H=\sum Π_{ij}$ has a 0-eigenvalue, or it is larger than $1/n^α$ for some $α=O(1)$. The problem is not only a natural extension of the classical 2-SAT problem to the quantum case, but is also equivalent to the problem of finding the ground state of 2-local frustration-free Hamiltonians of spin $\frac{1}{2}$, a well-studied model believed to capture certain key properties in modern condensed matter physics. While Bravyi has shown that the quantum 2-SAT problem has a classical polynomial-time algorithm, the running time of his algorithm is $O(n^4)$. In this paper we give a classical algorithm with linear running time in the number of local projectors, therefore achieving the best possible complexity.

arXiv:1508.06340•Aug 26, 2015•11 citations

Linear-Time Algorithm for Quantum 2SAT

Itai Arad, Miklós Sántha, Aarthi Sundaram +1 more

A well-known result about satisfiability theory is that the 2-SAT problem can be solved in linear time, despite the NP-hardness of the 3-SAT problem. In the quantum 2-SAT problem, we are given a family of 2-qubit projectors $\Pi_{ij}$ on a system of $n$ qubits, and the task is to decide whether the Hamiltonian $H=\sum \Pi_{ij}$ has a 0-eigenvalue, or all eigenvalues are greater than $1/n^\alpha$ for some $\alpha=O(1)$. The problem is not only a natural extension of the classical 2-SAT problem to the quantum case, but is also equivalent to the problem of finding a ground state of 2-local frustration-free Hamiltonians of spin $\frac{1}{2}$, a well-studied model believed to capture certain key properties in modern condensed matter physics. Bravyi has shown that the quantum 2-SAT problem has a deterministic algorithm of complexity $O(n^4)$ in the algebraic model of computation where every arithmetic operation on complex numbers can be performed in unit time, and $n$ is the number of variables. In this paper we give a deterministic algorithm in the algebraic model with running time $O(n+m)$, where $m$ is the number of local projectors, therefore achieving the best possible complexity in that model. We also show that if in the input every number has a constant size representation then the bit complexity of our algorithm is $O((n+m) M(n))$, where $M(n)$ denotes the complexity of multiplying two $n$-bit integers. A conference version of this paper appeared in the Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP'16), 2016.

Theory of Computing•Jan 1, 2018•5 citations

A Numerical Study of the Performance of a Quantum Adiabatic Evolution Algorithm for Satisfiability

Edward Farhi, Jeffrey Goldstone, Sam Gutmann

Quantum computation by adiabatic evolution, as described in quant-ph/0001106, will solve satisfiability problems if the running time is long enough. In certain special cases (that are classically easy) we know that the quantum algorithm requires a running time that grows as a polynomial in the number of bits. In this paper we present numerical results on randomly generated instances of an NP-complete problem and of a problem that can be solved classically in polynomial time. We simulate a quantum computer (of up to 16 qubits) by integrating the Schrodinger equation on a conventional computer. For both problems considered, for the set of instances studied, the required running time appears to grow slowly as a function of the number of bits.

arXiv:quant-ph/0007071•Jul 19, 2000•74 citations

Linear Time Algorithm for Quantum 2SAT

Itai Arad, Miklós Sántha, Aarthi Sundaram +1 more

A canonical result about satisfiability theory is that the 2-SAT problem can be solved in linear time, despite the NP-hardness of the 3-SAT problem. In the quantum 2-SAT problem, we are given a family of 2-qubit projectors Q_{ij} on a system of n qubits, and the task is to decide whether the Hamiltonian H = sum Q_{ij} has a 0-eigenvalue, or it is larger than 1/n^c for some c = O(1). The problem is not only a natural extension of the classical 2-SAT problem to the quantum case, but is also equivalent to the problem of finding the ground state of 2-local frustration-free Hamiltonians of spin 1/2, a well-studied model believed to capture certain key properties in modern condensed matter physics. While Bravyi has shown that the quantum 2-SAT problem has a classical polynomial-time algorithm, the running time of his algorithm is O(n^4). In this paper we give a classical algorithm with linear running time in the number of local projectors, therefore achieving the best possible complexity.

Leibniz international proceedings in informatics•Jan 1, 2016•5 citations

Quantum programming of the satisfiability problem with Rydberg atom graphs

Seokho Jeong, Minhyuk Kim, Minki Hhan +2 more

Finding a quantum computing method to solve nondeterministic polynomial time (NP)-complete problems is currently of paramount importance in quantum information science. Here we propose and experimentally demonstrate a Rydberg atom approach to program the 3-SAT problem, the prototypical NP-complete problem which allows general programming of all NP problems. We use Rydberg atom graphs, each of which consists of Rydberg atom dimers and trimers coupled with quantum wires in the Rydberg blockade interaction regime, to formulate general Boolean expressions, and obtain their many-body ground states to determine the satisfiabilities of the given 3-SAT problem instances quantum mechanically.

arXiv:2302.14369•Physical Review Research•Oct 12, 2023•23 citations

Complexity of Quantum Logic Satisfiability in Fixed Dimension: Realification and Rank-One Encodings

Higuchi, Joaquim Reizi

Quantum propositional logic, introduced by Birkhoff and von Neumann, formalizes reasoning about experimental propositions in quantum mechanics through closed subspaces of Hilbert spaces. We provide a comprehensive complexity analysis of the satisfiability problem for quantum logic formulas over the connectives conjunction, disjunction, and negation. Distinguishing between weak satisfiability (evaluation to a nonzero subspace) and strong satisfiability (evaluation to the full space), we establish that both notions coincide with Boolean satisfiability for dimension one, are classically NP complete for dimension two, and become complete for the Blum Shub Smale class NP_R when dimension d >= 3 is fixed. Our principal contribution is twofold. First, we present two alternative constructive reductions from quantum logic satisfiability to the Existential Theory of the Reals (ETR): a realification based encoding that explicitly handles the complex to real translation through commutant characterizations, and a rank one column encoding with orthogonal splitting gadgets. Both reductions yield polynomial size systems of quadratic equations for fixed dimension, proving membership in the complexity class existsR and hence in PSPACE via Cannys algorithm. Second, we provide detailed size bounds distinguishing weak and strong satisfiability: weak satisfiability encodes with O(n D^2 + N_v D) scalar variables where n is the number of atoms, D the real dimension, and N_v the number of disjunctions, while strong satisfiability requires O(n D^2 + N_v D^2) variables due to basis vector witnesses. When dimension is part of the input, strong satisfiability becomes polynomial time equivalent to feasibility of noncommutative integer polynomial equations. These results position quantum logic satisfiability precisely between classical NP and existsR, highlighting dimension as a fundamental complexity parameter.

•Nov 17, 2025•0 citations
We present an algorithm, along with a correctness proof, for solving the 3 Satisfiability problem that is inspired by quantum mechanical principles and that runs in polynomial time with respect to the size of the input problem. Even though we term both our algorithm and its associated proof as quantum (for reasons which we will demonstrate), it is intended to be run on standard classical architecture. In the article, we posit that the 3 Satisfiability problem has an intrinsic complex quantum form that can be programmed in order to build a model of the solution space for satisfiable instances or show that such a model cannot be constructed. This yields surprising results on the ability for classical systems to abstractly simulate general quantum systems.
A canonical result about satisfiability theory is that the 2-SAT problem can be solved in linear time, despite the NP-hardness of the 3-SAT problem. In the quantum 2-SAT problem, we are given a family of 2-qubit projectors ΠijΠ_{ij}Πij​ on a system of nnn qubits, and the task is to decide whether the Hamiltonian H=∑ΠijH=\sum Π_{ij}H=∑Πij​ has a 0-eigenvalue, or it is larger than 1/nα1/n^α1/nα for some α=O(1)α=O(1)α=O(1). The problem is not only a natural extension of the classical 2-SAT problem to the quantum case, but is also equivalent to the problem of finding the ground state of 2-local frustration-free Hamiltonians of spin 12\frac{1}{2}21​, a well-studied model believed to capture certain key properties in modern condensed matter physics. While Bravyi has shown that the quantum 2-SAT problem has a classical polynomial-time algorithm, the running time of his algorithm is O(n4)O(n^4)O(n4). In this paper we give a classical algorithm with linear running time in the number of local projectors, therefore achieving the best possible complexity.
A well-known result about satisfiability theory is that the 2-SAT problem can be solved in linear time, despite the NP-hardness of the 3-SAT problem. In the quantum 2-SAT problem, we are given a family of 2-qubit projectors Πij\Pi_{ij}Πij​ on a system of nnn qubits, and the task is to decide whether the Hamiltonian H=∑ΠijH=\sum \Pi_{ij}H=∑Πij​ has a 0-eigenvalue, or all eigenvalues are greater than 1/nα1/n^\alpha1/nα for some α=O(1)\alpha=O(1)α=O(1). The problem is not only a natural extension of the classical 2-SAT problem to the quantum case, but is also equivalent to the problem of finding a ground state of 2-local frustration-free Hamiltonians of spin 12\frac{1}{2}21​, a well-studied model believed to capture certain key properties in modern condensed matter physics. Bravyi has shown that the quantum 2-SAT problem has a deterministic algorithm of complexity O(n4)O(n^4)O(n4) in the algebraic model of computation where every arithmetic operation on complex numbers can be performed in unit time, and nnn is the number of variables. In this paper we give a deterministic algorithm in the algebraic model with running time O(n+m)O(n+m)O(n+m), where mmm is the number of local projectors, therefore achieving the best possible complexity in that model. We also show that if in the input every number has a constant size representation then the bit complexity of our algorithm is O((n+m)M(n))O((n+m) M(n))O((n+m)M(n)), where M(n)M(n)M(n) denotes the complexity of multiplying two nnn-bit integers. A conference version of this paper appeared in the Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP'16), 2016.
Quantum computation by adiabatic evolution, as described in quant-ph/0001106, will solve satisfiability problems if the running time is long enough. In certain special cases (that are classically easy) we know that the quantum algorithm requires a running time that grows as a polynomial in the number of bits. In this paper we present numerical results on randomly generated instances of an NP-complete problem and of a problem that can be solved classically in polynomial time. We simulate a quantum computer (of up to 16 qubits) by integrating the Schrodinger equation on a conventional computer. For both problems considered, for the set of instances studied, the required running time appears to grow slowly as a function of the number of bits.
A canonical result about satisfiability theory is that the 2-SAT problem can be solved in linear time, despite the NP-hardness of the 3-SAT problem. In the quantum 2-SAT problem, we are given a family of 2-qubit projectors Q_{ij} on a system of n qubits, and the task is to decide whether the Hamiltonian H = sum Q_{ij} has a 0-eigenvalue, or it is larger than 1/n^c for some c = O(1). The problem is not only a natural extension of the classical 2-SAT problem to the quantum case, but is also equivalent to the problem of finding the ground state of 2-local frustration-free Hamiltonians of spin 1/2, a well-studied model believed to capture certain key properties in modern condensed matter physics. While Bravyi has shown that the quantum 2-SAT problem has a classical polynomial-time algorithm, the running time of his algorithm is O(n^4). In this paper we give a classical algorithm with linear running time in the number of local projectors, therefore achieving the best possible complexity.
Finding a quantum computing method to solve nondeterministic polynomial time (NP)-complete problems is currently of paramount importance in quantum information science. Here we propose and experimentally demonstrate a Rydberg atom approach to program the 3-SAT problem, the prototypical NP-complete problem which allows general programming of all NP problems. We use Rydberg atom graphs, each of which consists of Rydberg atom dimers and trimers coupled with quantum wires in the Rydberg blockade interaction regime, to formulate general Boolean expressions, and obtain their many-body ground states to determine the satisfiabilities of the given 3-SAT problem instances quantum mechanically.
Quantum propositional logic, introduced by Birkhoff and von Neumann, formalizes reasoning about experimental propositions in quantum mechanics through closed subspaces of Hilbert spaces. We provide a comprehensive complexity analysis of the satisfiability problem for quantum logic formulas over the connectives conjunction, disjunction, and negation. Distinguishing between weak satisfiability (evaluation to a nonzero subspace) and strong satisfiability (evaluation to the full space), we establish that both notions coincide with Boolean satisfiability for dimension one, are classically NP complete for dimension two, and become complete for the Blum Shub Smale class NP_R when dimension d >= 3 is fixed. Our principal contribution is twofold. First, we present two alternative constructive reductions from quantum logic satisfiability to the Existential Theory of the Reals (ETR): a realification based encoding that explicitly handles the complex to real translation through commutant characterizations, and a rank one column encoding with orthogonal splitting gadgets. Both reductions yield polynomial size systems of quadratic equations for fixed dimension, proving membership in the complexity class existsR and hence in PSPACE via Cannys algorithm. Second, we provide detailed size bounds distinguishing weak and strong satisfiability: weak satisfiability encodes with O(n D^2 + N_v D) scalar variables where n is the number of atoms, D the real dimension, and N_v the number of disjunctions, while strong satisfiability requires O(n D^2 + N_v D^2) variables due to basis vector witnesses. When dimension is part of the input, strong satisfiability becomes polynomial time equivalent to feasibility of noncommutative integer polynomial equations. These results position quantum logic satisfiability precisely between classical NP and existsR, highlighting dimension as a fundamental complexity parameter.