Problema di Simon

Nella teoria della complessità computazionale e nella computazione quantistica, il problema di Simon è un problema computazionale che può essere risolto in maniera esponenzialmente più veloce su un computer quantistico rispetto a un computer classico (o tradizionale). Il problema di Simon incorpora l'uso di una scatola nera (black box). I problemi con la scatola nera danno agli algoritmi quantistici un vantaggio rispetto agli algoritmi classici. Il problema in sé è di poco interesse pratico perché ci sono poche situazioni realistiche in cui ci sia bisogno di risolvere il problema di Simon. Tuttavia, il problema è comunque importante perché si può dimostrare che un algoritmo quantistico può risolvere questo problema in modo esponenzialmente più veloce rispetto a un qualsiasi algoritmo classico conosciuto. Questo è il primo esempio di problema computazionale che può essere risolto in un tempo polinomiale su un computer quantistico. Il problema fu ideato da Daniel Simon nel 1994. Simon mostrò un algoritmo quantistico, spesso detto algoritmo di Simon, che risolve il problema richiedendo esponenzialmente meno tempo computazionale (o più precisamente, chiamate) rispetto al miglior algoritmo classico. Nell'algoritmo di Simon è necessario effettuare un numero lineare di chiamate, mentre l'algoritmo classico ne necessita un numero esponenziale. Questo problema dà una separazione dell'oracolo tra le classi di complessità BPP e BQP, a differenza della separazione data dall'algoritmo di Deutsch-Jozsa, che separa P e EQP. La separazione è esponenziale (relativa a un oracolo) tra la complessità classica e quantistica. L'algoritmo di Simon fu inoltre l'ispirazione per l'algoritmo di Shor. Entrambi i problemi sono casi particolari del problema del sottogruppo nascosto abeliano, per il quale sono conosciuti algoritmi quantistici efficienti.