Informazione e computazione quantistica: applicazioni
Mario Rasetti
Schemi diversi di computazione quantistica
La computazione e la teoria dell’informazione quantistiche sono ormai entrate nel complesso [...] . La varianza di tali osservabili è troppo grande per permettere il calcolo esatto dei polinomi di Jones in tempopolinomiale, anche con un computer quantistico, ma è possibile verificare che si riesce, con gli algoritmi proposti, ad approssimarli ...
Leggi Tutto
complessita computazionale
complessità computazionale o complessità di calcolo, teoria che, nell’ambito della teoria della computazione, analizza le risorse (quali il tempo e la memoria) necessarie per [...] Ciò vuol dire che esiste un algoritmo di verifica, dipendente da K e dai dati del problema, che controlla in tempopolinomiale l’esistenza di una soluzione del problema avente le proprietà richieste. Non si conosce, per esempio, nel caso generale se ...
Leggi Tutto
computazione quantistica
computazióne quantìstica locuz. sost. f. – Nella scienza dell'informazione, computazione basata sulla trattazione del dato quantistico. La c. q. ha introdotto un campo nuovo [...] dovrebbe permettere una maggiore velocità di calcolo in un computer quantistico. La computazione quantistica consente di scomporre in tempopolinomiale in fattori primi un numero intero che sia il prodotto di due numeri primi molto grandi. In tal ...
Leggi Tutto
millennio, problemi del
millènnio, problèmi del locuz. sost. m. pl. – Selezione di sette problemi matematici proposti nel 2000 dal Clay mathematics institute (CMI) di Cambridge nel Massachusetts, che [...] di complessità computazionale P, cui appartengono i problemi che possono essere risolti con un algoritmo deterministico in un tempopolinomiale, e NP, cui appartengono i problemi che possono essere verificati (ma non risolti) nello stesso modo. In ...
Leggi Tutto
problemi NP-completi
Mauro Cappelli
I problemi di decisione possono essere classificati prescindendo dall’algoritmo usato per risolverli. Sono state individuate le classi di problemi P, NP e NP-completi. [...] Infatti, se un problema R è nella classe NP-completa, allora per definizione tutti i problemi in NP possono essere ridotti in tempopolinomiale a R; ma se R∈P, allora ciò proverebbe che P =NP in contrasto con la congettura. Ci si può chiedere allora ...
Leggi Tutto
problemi P e NP
problemi P e NP classi di problemi costituite sulla base della loro → complessità computazionale, cioè della intrinseca difficoltà della loro risoluzione. Un problema appartiene alla [...] problema NP, se, posto in una qualsiasi forma di riconoscimento o di decisione, è verificabile in tempopolinomiale. Non si tratta perciò di decidere in tempopolinomiale se l’istanza è affermativa o meno, ma di verificare il problema in ...
Leggi Tutto
crittografia quantistica
crittografìa quantìstica locuz. sost. f. – Metodologia crittografica basata su opportuni sistemi di comunicazione quantistici. Uno fra i più interessanti risultati della moderna [...] deriva dall’algoritmo di Shor (ideato dallo statunitense Peter Shor nel 1994; v. ), capace di fattorizzare in tempopolinomiale un numero intero prodotto di due primi, un algoritmo, cioè, che trasforma un problema classico NP (Nondeterministic ...
Leggi Tutto
algoritmo quantistico
algoritmo quantìstico locuz. sost. m. – Algoritmo sviluppato secondo la logica della computazione quantistica (v.). Lo studio di a. q. è stato sostanzialmente improntato alla ricerca [...] di metodi di calcolo capaci di risolvere, in tempopolinomiale, problemi che non hanno soluzione polinomiale nel contesto classico. La struttura della meccanica quantistica mette infatti naturalmente a disposizione di chi costruisce l’algoritmo due ...
Leggi Tutto
complessita computazionale NP
complessità computazionale NP locuzione con cui si indica la complessità di calcolo di un problema di decisione (un problema cioè la cui soluzione può essere soltanto «sì» [...] oppure «no») che è verificabile in un tempopolinomiale (correlato alla dimensione del problema): non si decide, quindi, in tempopolinomiale se una particolare istanza del problema (cioè i valori assunti dai parametri che vi compaiono) è affermativa ...
Leggi Tutto
complessita computazionale P
complessità computazionale P locuzione con cui si indica la complessità di calcolo di un problema di decisione (un problema cioè la cui soluzione può essere soltanto «sì» [...] risolubile in un tempopolinomiale (correlato alla dimensione del problema). In sostanza per un problema di complessità computazionale P esiste un algoritmo di soluzione il cui tempo di risoluzione è funzione polinomiale delle dimensioni dei valori ...
Leggi Tutto