Marco Aldi

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 being a classical complexity class, however, TFNP has made a surprise appearance in the study of Quantum Satisfiability (QSAT): If a QSAT instance has a System of Distinct Representatives (SDR), then it has a product-state solution [Laumann, Läuchli, Moessner, Scardicchio, and Sondhi 2010]. Efficiently finding this product-state solution, however, has remained elusive. In this work, we introduce a new framework based on Weighted SDRs (WSDR), which among other results, allows us to: (1) significantly simplify and extend the results of [LLMSS 2010] to qudit systems, (2) establish a connection to the Bézout number for multihomogeneous polynomial systems, and (3) apply the parameterized algorithm of [Aldi, de Beaudrap, Gharibian, Saeedi 2021] to solve new instances of QSAT efficiently on qudits. The second of these, in particular, allows us to define the first ""quantum-inspired"" subclass of TFNP, for which we show QSAT with SDR is complete. Thus, we obtain the first evidence that QSAT with SDR is, in fact, intractable.