2026-07-21T19:19:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19600 2024-03-06T11:04:26Z ddc:004 open_access

Classical vs Quantum Advice and Proofs Under Classically-Accessible Oracle Li, Xingjian Liu, Qipeng Pelecanos, Angelos Yamakawa, Takashi quantum computation computational complexity It is a long-standing open question to construct a classical oracle relative to which BQP/qpoly ≠ BQP/poly or QMA ≠ QCMA. In this paper, we construct classically-accessible classical oracles relative to which BQP/qpoly ≠ BQP/poly and QMA ≠ QCMA. Here, classically-accessible classical oracles are oracles that can be accessed only classically even for quantum algorithms. Based on a similar technique, we also show an alternative proof for the separation of QMA and QCMA relative to a distributional quantumly-accessible classical oracle, which was recently shown by Natarajan and Nirkhe. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xingjian Li and Qipeng Liu and Angelos Pelecanos and Takashi Yamakawa 2024 Is Part Of LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2024.72 urn:nbn:de:0030-drops-196009 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.72 eng https://creativecommons.org/licenses/by/4.0/legalcode