---
_id: '57866'
abstract:
- lang: eng
  text: "The theory of Total Function NP (TFNP) and its subclasses says that, even
    if\r\none is promised an efficiently verifiable proof exists for a problem, finding\r\nthis
    proof can be intractable. Despite the success of the theory at showing\r\nintractability
    of problems such as computing Brouwer fixed points and Nash\r\nequilibria, subclasses
    of TFNP remain arguably few and far between. In this\r\nwork, we define two new
    subclasses of TFNP borne of the study of complex\r\npolynomial systems: Multi-homogeneous
    Systems (MHS) and Sparse Fundamental\r\nTheorem of Algebra (SFTA). The first of
    these is based on B\\'ezout's theorem\r\nfrom algebraic geometry, marking the
    first TFNP subclass based on an algebraic\r\ngeometric principle. At the heart
    of our study is the computational problem\r\nknown as Quantum SAT (QSAT) with
    a System of Distinct Representatives (SDR),\r\nfirst studied by [Laumann, L\\\"auchli,
    Moessner, Scardicchio, and Sondhi 2010].\r\nAmong other results, we show that
    QSAT with SDR is MHS-complete, thus giving\r\nnot only the first link between
    quantum complexity theory and TFNP, but also\r\nthe first TFNP problem whose classical
    variant (SAT with SDR) is easy but whose\r\nquantum variant is hard. We also show
    how to embed the roots of a sparse,\r\nhigh-degree, univariate polynomial into
    QSAT with SDR, obtaining that SFTA is\r\ncontained in a zero-error version of
    MHS. We conjecture this construction also\r\nworks in the low-error setting, which
    would imply SFTA is contained in MHS."
author:
- first_name: Marco
  full_name: Aldi, Marco
  last_name: Aldi
- first_name: Sevag
  full_name: Gharibian, Sevag
  id: '71541'
  last_name: Gharibian
  orcid: 0000-0002-9992-3379
- first_name: Dorian
  full_name: Rudolph, Dorian
  id: '57863'
  last_name: Rudolph
citation:
  ama: 'Aldi M, Gharibian S, Rudolph D. An unholy trinity: TFNP, polynomial systems,
    and the quantum  satisfiability problem. In: <i>17th Innovations in Theoretical
    Computer Science Conference (ITCS 2026)</i>. Vol 362. ; 2026:7:1-7:24.'
  apa: 'Aldi, M., Gharibian, S., &#38; Rudolph, D. (2026). An unholy trinity: TFNP,
    polynomial systems, and the quantum  satisfiability problem. <i>17th Innovations
    in Theoretical Computer Science Conference (ITCS 2026)</i>, <i>362</i>, 7:1-7:24.'
  bibtex: '@inproceedings{Aldi_Gharibian_Rudolph_2026, title={An unholy trinity: TFNP,
    polynomial systems, and the quantum  satisfiability problem}, volume={362}, booktitle={17th
    Innovations in Theoretical Computer Science Conference (ITCS 2026)}, author={Aldi,
    Marco and Gharibian, Sevag and Rudolph, Dorian}, year={2026}, pages={7:1-7:24}
    }'
  chicago: 'Aldi, Marco, Sevag Gharibian, and Dorian Rudolph. “An Unholy Trinity:
    TFNP, Polynomial Systems, and the Quantum  Satisfiability Problem.” In <i>17th
    Innovations in Theoretical Computer Science Conference (ITCS 2026)</i>, 362:7:1-7:24,
    2026.'
  ieee: 'M. Aldi, S. Gharibian, and D. Rudolph, “An unholy trinity: TFNP, polynomial
    systems, and the quantum  satisfiability problem,” in <i>17th Innovations in Theoretical
    Computer Science Conference (ITCS 2026)</i>, 2026, vol. 362, p. 7:1-7:24.'
  mla: 'Aldi, Marco, et al. “An Unholy Trinity: TFNP, Polynomial Systems, and the
    Quantum  Satisfiability Problem.” <i>17th Innovations in Theoretical Computer
    Science Conference (ITCS 2026)</i>, vol. 362, 2026, p. 7:1-7:24.'
  short: 'M. Aldi, S. Gharibian, D. Rudolph, in: 17th Innovations in Theoretical Computer
    Science Conference (ITCS 2026), 2026, p. 7:1-7:24.'
date_created: 2024-12-30T13:55:27Z
date_updated: 2026-01-23T07:53:03Z
external_id:
  arxiv:
  - '2412.19623'
intvolume: '       362'
language:
- iso: eng
page: 7:1-7:24
publication: 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)
publication_status: published
status: public
title: 'An unholy trinity: TFNP, polynomial systems, and the quantum  satisfiability
  problem'
type: conference
user_id: '71541'
volume: 362
year: '2026'
...
---
_id: '60432'
abstract:
- lang: eng
  text: "The Quantum k-SAT problem is the quantum generalization of the k-SAT problem.\r\nIt
    is the problem whether a given local Hamiltonian is frustration-free.\r\nFrustration-free
    means that the ground state of the k-local Hamiltonian\r\nminimizes the energy
    of every local interaction term simultaneously. This is a\r\ncentral question
    in quantum physics and a canonical QMA_1-complete problem. The\r\nQuantum k-SAT
    problem is not as well studied as the classical k-SAT problem in\r\nterms of special
    tractable cases, approximation algorithms and parameterized\r\ncomplexity. In
    this paper, we will give a graph-theoretic study of the Quantum\r\nk-SAT problem
    with the structures core and radius. These hypergraph structures\r\nare important
    to solve the Quantum k-SAT problem. We can solve a Quantum k-SAT\r\ninstance in
    polynomial time if the derived hypergraph has a core of size n-m+a,\r\nwhere a
    is a constant, and the radius is at most logarithmic. If it exists, we\r\ncan
    find a core of size n-m+a with the best possible radius in polynomial time,\r\nwhereas
    finding a general minimum core with minimal radius is NP-hard."
author:
- first_name: Simon-Luca
  full_name: Kremer, Simon-Luca
  last_name: Kremer
- first_name: Dorian
  full_name: Rudolph, Dorian
  id: '57863'
  last_name: Rudolph
- first_name: Sevag
  full_name: Gharibian, Sevag
  id: '71541'
  last_name: Gharibian
  orcid: 0000-0002-9992-3379
citation:
  ama: Kremer S-L, Rudolph D, Gharibian S. Quantum k-SAT Related Hypergraph Problems.
    <i>arXiv:250617066</i>. Published online 2025.
  apa: Kremer, S.-L., Rudolph, D., &#38; Gharibian, S. (2025). Quantum k-SAT Related
    Hypergraph Problems. In <i>arXiv:2506.17066</i>.
  bibtex: '@article{Kremer_Rudolph_Gharibian_2025, title={Quantum k-SAT Related Hypergraph
    Problems}, journal={arXiv:2506.17066}, author={Kremer, Simon-Luca and Rudolph,
    Dorian and Gharibian, Sevag}, year={2025} }'
  chicago: Kremer, Simon-Luca, Dorian Rudolph, and Sevag Gharibian. “Quantum K-SAT
    Related Hypergraph Problems.” <i>ArXiv:2506.17066</i>, 2025.
  ieee: S.-L. Kremer, D. Rudolph, and S. Gharibian, “Quantum k-SAT Related Hypergraph
    Problems,” <i>arXiv:2506.17066</i>. 2025.
  mla: Kremer, Simon-Luca, et al. “Quantum K-SAT Related Hypergraph Problems.” <i>ArXiv:2506.17066</i>,
    2025.
  short: S.-L. Kremer, D. Rudolph, S. Gharibian, ArXiv:2506.17066 (2025).
date_created: 2025-06-27T06:56:35Z
date_updated: 2025-06-27T06:57:03Z
external_id:
  arxiv:
  - '2506.17066'
language:
- iso: eng
publication: arXiv:2506.17066
status: public
title: Quantum k-SAT Related Hypergraph Problems
type: preprint
user_id: '71541'
year: '2025'
...