Una barriera alla perdita d’informazione delle etichette di Fourier per gli algoritmi del coset diedrale

Abstract degli autori

Dimostriamo un teorema di impossibilità per un’ampia classe di algoritmi quantistici per il problema del coset diedrale (DCP). Consideriamo lo schema di campionamento di Fourier e misurazione della somma di sottoinsieme proposto da Regev (SIAM Journal on Computing, 2004), uno dei principali approcci per risolvere il DCP. Supponiamo che, dopo aver misurato gli $n-1$ bit meno significativi della somma di sottoinsieme, l’algoritmo scarti $ω(\log n)$ bit da ciascuna delle etichette di Fourier. Dimostriamo allora che l’algoritmo non può riuscire a risolvere il DCP. Questo mostra che qualsiasi algoritmo che segua questo schema deve fare ampio uso delle etichette di Fourier e costituisce quindi una guida utile per sviluppare algoritmi per il DCP. Come applicazione principale, mostriamo che il recente algoritmo di Simon (IACR ePrint:2026/1591, 11 agosto 2026) non risolve il DCP. Mostriamo che, dopo la misurazione della somma di sottoinsieme, questo algoritmo può essere implementato (con un errore esponenzialmente piccolo) usando solo il terzo più significativo delle etichette di Fourier, ed è quindi soggetto al nostro teorema generale di impossibilità. Per facilitare la verificabilità, rendiamo disponibile il codice Lean 4 dei nostri risultati.