[Quantum Seminar] Andrew Huang | Separating Quantum and Classical Advice with Good Codes скачать в хорошем качестве

[Quantum Seminar] Andrew Huang | Separating Quantum and Classical Advice with Good Codes

Separating Quantum and Classical Advice with Good Codes Abstract. We show an unconditional classical oracle separation between the class of languages that can be verified using a quantum proof (𝖰𝖬𝖠) and the class of languages that can be verified with a classical proof (𝖰𝖢𝖬𝖠). Compared to the recent work of Bostanci, Haferkamp, Nirkhe, and Zhandry (STOC 2026), our proof is conceptually and technically simpler, and readily extends to other oracle separations. In particular, our techniques yield the first unconditional classical oracle separation between the class of languages that can be decided with quantum advice (𝖡𝖰𝖯/𝗊𝗉𝗈𝗅𝗒) and the class of languages that can be decided with classical advice (𝖡𝖰𝖯/𝗉𝗈𝗅𝗒), improving on the quantum oracle separation of Aaronson and Kuperberg (CCC 2007) and the classically-accessible classical oracle separation of Li, Liu, Pelecanos and Yamakawa (ITCS 2024). Our oracles are based on the code intersection problem introduced by Yamakawa and Zhandry (FOCS 2022), combined with codes that have extremely good list-recovery properties. About. https://scholar.google.com/citations?... arXiv.* https://arxiv.org/abs/2602.09385 Host. IIIT Hyderabad