REVIEW 1 cited by
Efficient algorithm for a quantum analogue of 2-SAT
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Efficient algorithm for a quantum analogue of 2-SAT
read the original abstract
Complexity of a quantum analogue of the satisfiability problem is studied. Quantum k-SAT is a problem of verifying whether there exists n-qubit pure state such that its k-qubit reduced density matrices have support on prescribed subspaces. We present a classical algorithm solving quantum 2-SAT in a polynomial time. It generalizes the well-known algorithm for the classical 2-SAT. Besides, we show that for any k>=4 quantum k-SAT is complete in the complexity class QMA with one-sided error.
Forward citations
Cited by 1 Pith paper
-
A Slice-Rank Drift Bound for Random Quantum \(k\)-SAT
Random quantum k-SAT is unsatisfiable above density α⋆(k)∼2^k/k, improving the prior O(2^k) upper bound by a factor of order k, with α⋆(3)≈1.947.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.