~ Un computer quantistico ~ per risolvere P vs NP

Un computer quantistico

Kane_QC

In un computer classico, la quantità di dati viene misurata in bit, mentre in un computer quantico l’unità di misura è il qubit.

Il principio che sta alla base del computer quantico, è che le proprietà quantistiche delle particelle possono essere utilizzate per rappresentare strutture di dati, e che il complesso meccanismo della meccanica quantistica possa essere sfruttato per eseguire operazioni su tali dati.

Domanda:
Con Algoritmo di fattorizzazione di Shor su un computer quantistico questo algoritmo ha una complessità computazionale polinomiale. si Avete letto bene (possibilita di calcolo in tempi Brevi)

algoritmodishor-120128074349-phpapp02-thumbnail-4

Riflessione:

Se tramite questo Algoritmo si è dimostrato di poter risolvere equazioni in tempi P (cioè in tempi brevi per un calcolatore), perché Esso comunque non risolve il problema di P=NP?

La questione è che Shor non può usare tale algoritmo per problemi NP Completi.

[Un ruolo importante in questa discussione è giocato dall’insieme dei problemi NP-completi, che possono essere intuitivamente descritti come quei problemi che sicuramente non apparterrebbero a P se P fosse diverso da NP. Al contrario, dimostrando anche per un solo problema NP-completo la sua appartenenza a P, si otterrebbe una dimostrazione che P e NP sono equivalenti. In un certo senso, i problemi NP-completi sono quelli che meno probabilmente appartengono anche a P.]f.te wikipedia

problemi cioè che sicuramente sappiamo non essere risolti in tempi P (cioè Brevi),
ma solo per problemi di risoluzione di cui noi non abbiamo certezza siano in NP.

[Non esiste una macchina quantistica scalabile che implementi la versione descritta dell’algoritmo di Shor. Versioni compilate, ossia ridotte per casi specifici, sono invece già state eseguite: ad esempio su sistemi ottici lineari, dove i qubit sono codificati nella polarizzazione dei fotoni.]f.te wikipedia

Considerazioni Mie:
Rimango Affascinato comunque da tale metodo di calcolo quantistico,
poiché significa comunque cominciare a porre le basi per un approccio serio al problema.

See You G.R.R.