Showing cs.CCShow all
2 papers · 1 filter
cs.CC2026
Separating ClonableQMA and QCMA Relative to a Classical Oracle
Alper Cakan, Kai-Min Chung, Wei-Hsiang Hung +1
Since the introduction of the complexity class QMA as a quantum-verifier analogue of NP (Kitaev, 1997), many have wondered whether quantum proofs are necessary or classical proofs…
cs.CC2025
Tight Quantum Time-Space Tradeoffs for Permutation Inversion
Akshima, Tyler Besselman, Kai-Min Chung +2
In permutation inversion, we are given a permutation , and want to prepare some advice of size , such that we can efficiently invert any image in time $T…