Li, Xingjian
[Author];
Liu, Qipeng
[Author];
Pelecanos, Angelos
[Author];
Yamakawa, Takashi
[Author]
;
Xingjian Li and Qipeng Liu and Angelos Pelecanos and Takashi Yamakawa
[Contributor]
Classical vs Quantum Advice and Proofs Under Classically-Accessible Oracle
Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
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.