2 citations · 3 across the 8 of their papers we have counts for
Showing 2024 · quant-phShow all
2 papers · 2 filters
quant-ph2024
An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem
Marco Aldi, 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 intract…
quant-ph2024
Quantum 2-SAT on low dimensional systems is -complete: Direct embeddings and black-box simulation
Dorian Rudolph, Sevag Gharibian, Daniel Nagaj
Despite the fundamental role the Quantum Satisfiability (QSAT) problem has played in quantum complexity theory, a central question remains open: At which local dimension does the c…