Vai al contenuto
Quantum.world

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