تقرير
Oracle separation of QMA and QCMA with bounded adaptivity
العنوان: | Oracle separation of QMA and QCMA with bounded adaptivity |
---|---|
المؤلفون: | Ben-David, Shalev, Kundu, Srijita |
سنة النشر: | 2024 |
المجموعة: | Computer Science Quantum Physics |
مصطلحات موضوعية: | Quantum Physics, Computer Science - Computational Complexity |
الوصف: | We give an oracle separation between QMA and QCMA for quantum algorithms that have bounded adaptivity in their oracle queries; that is, the number of rounds of oracle calls is small, though each round may involve polynomially many queries in parallel. Our oracle construction is a simplified version of the construction used recently by Li, Liu, Pelecanos, and Yamakawa (2023), who showed an oracle separation between QMA and QCMA when the quantum algorithms are only allowed to access the oracle classically. To prove our results, we introduce a property of relations called \emph{slipperiness}, which may be useful for getting a fully general classical oracle separation between QMA and QCMA. |
نوع الوثيقة: | Working Paper |
URL الوصول: | http://arxiv.org/abs/2402.00298 |
رقم الأكسشن: | edsarx.2402.00298 |
قاعدة البيانات: | arXiv |
الوصف غير متاح. |