Daniel Nagaj

collaborators

2 papers

quant-ph2025

Quantum SAT Problems with Finite Sets of Projectors are Complete for a Plethora of Classes

Ricardo Rivera Cardoso, Alex Meiburg, Daniel Nagaj

Previously, all known variants of the Quantum Satisfiability (QSAT) problem, i.e. deciding whether a $k$ -local ( $k$ -body) Hamiltonian is frustration-free, could be classified as be…

quant-ph2024

Quantum 2-SAT on low dimensional systems is $QMA_{1}$ -complete: Direct embeddings and black-box simulation

Dorian Rudolph, Sevag Gharibian, Daniel Nagaj

Despite the fundamental role the Quantum Satisfiability (QSAT) problem has played in quantum complexity theory, a central question remains open: At which local dimension does the c…

Quantum SAT Problems with Finite Sets of Projectors are Complete for a Plethora of Classes

Quantum 2-SAT on low dimensional systems is QMA1​-complete: Direct embeddings and black-box simulation

Quantum 2-SAT on low dimensional systems is $QMA_{1}$ -complete: Direct embeddings and black-box simulation