Algoritmi quantistici e classi di complessità

Solitamente il concetto di difficoltà è piuttosto soggettivo, ma per un matematico questa parola ha un significato diverso: anche con l’aiuto dei più potenti computer può essere impossibile trovare la soluzione di un sudoku, risolvere l’enigma del commesso viaggiatore o scomporre un numero nei suoi fattori primi; in questo senso le classi di complessità computazionale quantificano il concetto di difficoltà secondo le leggi dell’informatica classica. Una macchina quantistica, però, non segue le leggi classiche e costituisce un nuovo punto di vista in una frontiera della ricerca legata alla risoluzione dei celebri problemi del millennio: gli algoritmi quantistici implementano le proprietà straordinarie e misteriose della teoria dei quanti che, quando applicate lucidamente, danno luogo a risultati sorprendenti.