@inproceedings{57866,
  abstract     = {{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 intractable. Despite the success of the theory at showing
intractability of problems such as computing Brouwer fixed points and Nash
equilibria, subclasses of TFNP remain arguably few and far between. In this
work, we define two new subclasses of TFNP borne of the study of complex
polynomial systems: Multi-homogeneous Systems (MHS) and Sparse Fundamental
Theorem of Algebra (SFTA). The first of these is based on B\'ezout's theorem
from algebraic geometry, marking the first TFNP subclass based on an algebraic
geometric principle. At the heart of our study is the computational problem
known as Quantum SAT (QSAT) with a System of Distinct Representatives (SDR),
first studied by [Laumann, L\"auchli, Moessner, Scardicchio, and Sondhi 2010].
Among other results, we show that QSAT with SDR is MHS-complete, thus giving
not only the first link between quantum complexity theory and TFNP, but also
the first TFNP problem whose classical variant (SAT with SDR) is easy but whose
quantum variant is hard. We also show how to embed the roots of a sparse,
high-degree, univariate polynomial into QSAT with SDR, obtaining that SFTA is
contained in a zero-error version of MHS. We conjecture this construction also
works in the low-error setting, which would imply SFTA is contained in MHS.}},
  author       = {{Aldi, Marco and Gharibian, Sevag and Rudolph, Dorian}},
  booktitle    = {{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)}},
  pages        = {{7:1--7:24}},
  title        = {{{An unholy trinity: TFNP, polynomial systems, and the quantum  satisfiability problem}}},
  volume       = {{362}},
  year         = {{2026}},
}

@unpublished{60432,
  abstract     = {{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 the ground state of the k-local Hamiltonian
minimizes the energy of every local interaction term simultaneously. This is a
central question in quantum physics and a canonical QMA_1-complete problem. The
Quantum k-SAT problem is not as well studied as the classical k-SAT problem in
terms of special tractable cases, approximation algorithms and parameterized
complexity. In this paper, we will give a graph-theoretic study of the Quantum
k-SAT problem with the structures core and radius. These hypergraph structures
are important to solve the Quantum k-SAT problem. We can solve a Quantum k-SAT
instance in polynomial time if the derived hypergraph has a core of size n-m+a,
where a is a constant, and the radius is at most logarithmic. If it exists, we
can find a core of size n-m+a with the best possible radius in polynomial time,
whereas finding a general minimum core with minimal radius is NP-hard.}},
  author       = {{Kremer, Simon-Luca and Rudolph, Dorian and Gharibian, Sevag}},
  booktitle    = {{arXiv:2506.17066}},
  title        = {{{Quantum k-SAT Related Hypergraph Problems}}},
  year         = {{2025}},
}