Name
Abstract | ||
|---|---|---|
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. |
Year | Venue | Field |
|---|---|---|
2015 | ICALP | Quantum phase estimation algorithm,Hamiltonian (quantum mechanics),Quantum mechanics,Quantum computer,Quantum algorithm,Time complexity,Discrete mathematics,Combinatorics,Algorithm,Quantum algorithm for linear systems of equations,P versus NP problem,Qubit,Mathematics |
DocType | Volume | Citations |
Journal | abs/1508.06340 | 1 |
PageRank | References | Authors |
0.41 | 3 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Itai Arad | 1 | 78 | 8.54 |
| Miklos Santha | 2 | 728 | 92.42 |
| Aarthi Sundaram | 3 | 4 | 3.18 |
| Shengyu Zhang | 4 | 329 | 42.48 |