5 papers
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…
Constant-Rate Certified Deletion
Kai-Min Chung, Tzu-Hsiang Huang, Wei-Hsiang Hung +1
We present a unified framework for upgrading a broad class of cryptographic primitives to support constant-rate certified deletion. Previous constructions require a linear number o…
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…
Complexity Theory for Quantum Promise Problems
Nai-Hui Chia, Kai-Min Chung, Tzu-Hsiang Huang +2
We begin by establishing structural results for several fundamental quantum complexity classes: p/mBQP, p/mQ(C)MA, , p/mQIP, p/mBQP/qpoly, p/mBQP/poly,…
The Black-Box Simulation Barrier Persists in a Fully Quantum World
Nai-Hui Chia, Kai-Min Chung, Xiao Liang +1
Zero-Knowledge (ZK) protocols have been intensely studied due to their fundamental importance and versatility. However, quantum information's inherent differences significantly alt…