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:quant-ph/9809075

NP problem in quantum algorithm

Masanori Ohya, Natsuki Masuda

Published Sep 24, 1998• 9 citations
arXivHTMLPDF

Abstract

In complexity theory, there exists a famous unsolved problem whether NP can be P or not. In this paper, we discuss this aspect in SAT (satisfiability) problem, and it is shown that the SAT can be solved in plynomial time by means of quantum algorithm.
DOI
10.48550/arxiv.quant-ph/9809075

Related papers

NP Problem in Quantum Algorithm

Masanori Ohya, Natsuki Masuda

In complexity theory, a famous unsolved problem is whether NP is equal to P or not. In this paper, we discuss this aspect in SAT (satisfiability) problem, and it is shown that SAT can be solved in polynomial time by means of a quantum algorithm if the superposition of two orthogonal vectors |0〉 and |1〉 prepared is detected physically.

WORLD SCIENTIFIC eBooks•Feb 1, 2008•8 citations

Classical and Quantum Algorithms for the Boolean Satisfiability Problem

Carlos Barrón-Romero

This paper presents a complete algorithmic study of the decision Boolean Satisfiability Problem under the classical computation and quantum computation theories. The paper depicts deterministic and probabilistic algorithms, propositions of their properties and the main result is that the problem has not an efficient algorithm (NP is not P). Novel quantum algorithms and propositions depict that the complexity by quantum computation approach for solving the Boolean Satisfiability Problem or any NP problem is lineal time.

arXiv:1510.02682•Oct 6, 2015•4 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 $Π_{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 Stochastic Limit Approach to the SAT Problem

Luigi Accardi, Masanori Ohya

There exists an important problem whether there exists an algorithm to solve an NP-complete problem in polynomial time. In this paper, a new concept of quantum adaptive stochastic systems is proposed, and it is shown that it can be used to solve the problem above.

arXiv:quant-ph/0401110•Open Systems & Information Dynamics•Sep 1, 2004•28 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
This paper presents a complete algorithmic study of the decision Boolean Satisfiability Problem under the classical computation and quantum computation theories. The paper depicts deterministic and probabilistic algorithms, propositions of their properties and the main result is that the problem has not an efficient algorithm (NP is not P). Novel quantum algorithms and propositions depict that the complexity by quantum computation approach for solving the Boolean Satisfiability Problem or any NP problem is lineal time.
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.
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.