2 papers
cs.CC2025
Quantum k-SAT Related Hypergraph Problems
Simon-Luca Kremer, Dorian Rudolph, Sevag Gharibian
The Quantum k-SAT problem is the quantum generalization of the k-SAT problem. It is the problem whether a given local Hamiltonian is frustration-free. Frustration-free means that t…
quant-ph2024
An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem
Marco Aldi, Sevag Gharibian, Dorian Rudolph
The theory of Total Function NP (TFNP) and its subclasses says that, even if one is promised an efficiently verifiable proof exists for a problem, finding this proof can be intract…