REVIEW 4 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
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 4 Pith papers
-
Quantum SAT Problems with Finite Sets of Projectors are Complete for a Plethora of Classes
New QSAT variants on qubits and qudits are complete for BQP_1, coRP, QCMA and six PI/SoPU classes, implying any classification of strong quantum CSPs must contain at least 13 classes unless some collapse.
-
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.
-
State Engineering of Unsteerable Hamiltonians
Frustrated local Hamiltonians can sometimes be steered into their ground-state manifold via discrete local measurement steps, and when they cannot, local steering is bounded by a 'glass floor' set by the smallest eige...
-
Heisenberg limited quantum algorithm for estimating the fidelity susceptibility
A quantum algorithm estimates fidelity susceptibility in O~(1/epsilon) queries using a resolvent reformulation, achieving Heisenberg-limited precision.
Discussion (0). Continue with ORCID to comment.