177 citations · 983 across the 32 of their papers we have counts for
3 papers · 1 filter
The Local Hamiltonian problem on a line with eight states is QMA-complete
Sean Hallgren, Daniel Nagaj, Sandeep Narayanaswami
The Local Hamiltonian problem is the problem of estimating the least eigenvalue of a local Hamiltonian, and is complete for the class QMA. The 1D problem on a chain of qubits has h…
The SAT-UNSAT transition in the adversarial SAT problem
Marco Bardoscia, Daniel Nagaj, Antonello Scardicchio
Adversarial SAT (AdSAT) is a generalization of the satisfiability (SAT) problem in which two players try to make a boolean formula true (resp. false) by controlling their respectiv…
Quantum 3-SAT is QMA1-complete
David Gosset, Daniel Nagaj
Quantum satisfiability is a constraint satisfaction problem that generalizes classical boolean satisfiability. In the quantum k-SAT problem, each constraint is specified by a k-loc…