Quantum Complexity Meets TFNP: Exploring Product Quantum Satisfiability on Qudits at TQC 2024 🔍

Quantum complexity theory meets TFNP: Product Quantum Satisfiability on qudits | Marco Aldi, Sevag Gharibian and 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 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. TQC 2024 | 9-13 September 2024 at OIST, Japan http://tqc-conference.org 19th Conference on the Theory of Quantum Computation, Communication and Cryptography. TQC is a leading annual international conference for students and researchers working in the theoretical aspects of quantum information science. The scientific objective is to bring together the theoretical quantum information science community to present and discuss the latest advances in the field. Organisation: OIST: Okinawa Institute for Science and Technology Squids: Schools for Quantum Information Development Sponsors: JPMorganChase Google Quantum AI Horizon Quantum Computing Quantinuum Japan National Tourism Organization