Ricerca
Separazione tramite oracolo classico di QMA dalla gerarchia QCMA e crittografia quantistica anche quando P = QCMA
Nota: questo lavoro è in fase di sottomissione a STOC'27 e il manoscritto completo è quindi disponibile pubblicamente sul sito web della conferenza dal 3 novembre 2026.
- arXiv
- 2611.26574
- Pubblicato
- 2026-11-19
- Autori
- Alper Cakan
Abstract degli autori
Nota: questo lavoro è in fase di sottomissione a STOC'27 e il manoscritto completo è quindi disponibile pubblicamente sul sito web della conferenza dal 3 novembre 2026. Ispirandoci al problema Codeword-Hash Structure, introdotto recentemente da Cakan (arXiV, 2026) per separare $\mathsf{QMA}$ da $\mathsf{QCIP}$, introduciamo un nuovo problema, chiamato Codeword-Hash pairs in Noise ($\mathsf{CHN}$), e dimostriamo che, nel modello di complessità di query, appartiene a $\mathsf{QMA}$ ma è difficile per la gerarchia $\mathsf{QCMA}$, $\mathsf{QCMAH} = \bigcup_{d\geq1}\mathsf{QCMA}^{\mathsf{QCMA}^{\cdots^{\mathsf{QCMA}}}}$, l’analogo di $\mathsf{PH}=\bigcup_{d\ge1}\mathsf{NP}^{\mathsf{NP}^{\cdots^{\mathsf{NP}}}}$ con testimone classico e verificatore quantistico. Usando questo problema, mostriamo che esiste un oracolo classico ${O}$ tale che $\mathsf{P}^{O}=\mathsf{BQP}^{O}=\mathsf{QCMA}^{O} =\mathsf{QCMAH}^{O} \subset \mathsf{QMA}^{O} \text{ but } \mathsf{QMA}^{O}\not\subseteq\mathsf{QCMAH}^{O},$ mostrando così che un vantaggio derivante da uno stato quantistico o da una dimostrazione quantistica potrebbe esistere anche se i computer classici sono in grado di risolvere efficientemente qualsiasi problema verificabile quantisticamente con una dimostrazione classica. Inoltre, usando il nostro problema, mostriamo che possono esistere diverse primitive crittografiche quantistiche anche quando $\mathsf{P} = \mathsf{QCMA}$ e che quindi non esistono né funzioni unidirezionali computabili quantisticamente né un vantaggio computazionale quantistico (verificabile). In particolare, rispetto a un oracolo classico ${O}$ per cui $\mathsf{P}^{O}=\mathsf{BQP}^{O}=\mathsf{QCMA}^{O}=\mathsf{QCMAH}^{O}$, esistono stati pseudocasuali con chiavi classiche e sistemi di cifratura a chiave pubblica con chiavi quantistiche di decifratura protette dalla copia e chiavi pubbliche e testi cifrati classici, tra le altre primitive, dando risposta a una domanda aperta di Kretschmer, Qian e Tal (STOC 2025).
Il riassunto di questo paper è disponibile solo in inglese: leggilo nella pagina inglese.
Leggi il paper originale su arXiv