Quantum Complexity Theory Meets TFNP - Product Quantum Satisfiability on Qudits

Explore a 24-minute conference talk from the 19th Theory of Quantum Computation, Communication and Cryptography Conference (TQC 2024) that delves into the intersection of quantum complexity theory and Total Function NP (TFNP). Learn how researchers introduce a new framework based on Weighted Systems of Distinct Representatives (WSDR) to advance the study of Quantum Satisfiability (QSAT) on qudit systems. Discover how this framework simplifies and extends previous results, establishes connections to Bézout numbers in multihomogeneous polynomial systems, and enables efficient solutions for new QSAT instances. Understand the significance of defining the first "quantum-inspired" subclass of TFNP, where QSAT with SDR is proven complete, suggesting its intractability. Presented by Marco Aldi, Sevag Gharibian, and Dorian Rudolph at OIST, Japan, this talk represents cutting-edge research in theoretical quantum information science, supported by major industry leaders including JPMorganChase, Google Quantum AI, and Quantinuum.