1
talks
0
committee roles
0
leadership roles
2024–2024
years active
Contributions
QIP QCrypt TQC presenter award · △program ◇steering ○organising □local · filled = chair
Talks
| Title | Conference | Type | Co-authors |
|---|---|---|---|
| Quantum complexity theory meets TFNP: Product Quantum Satisfiability on qudits | TQC 2024 | regular ▸ presenter | Sevag Gharibian, 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. |
|||
Collaborators
| Co-author | Joint talks |
|---|---|
| Dorian Rudolph | 1 |
| Sevag Gharibian | 1 |