Impatto dei computer quantistici, oltre ai nuovi algoritmi

La cosa con il calcolo quantistico è che non lo sappiamo ancora .

Alcuni pensieri:

• Se realizziamo mai un vero computer quantistico, è probabile essere significativamente più veloce dei computer classici, quando la velocità viene misurata in modo simile.
• Se sarà più veloce, non sappiamo quanto più velocemente fino a quando ne costruiamo uno. Gli attuali prototipi sono tutt'altro che completi e persino le dimostrazioni "indicative" della tecnologia sono discutibili.
• Il calcolo quantistico offre una scorciatoia potenziale per determinate operazioni, in quanto può utilizzare varie forme di trucchi della meccanica quantistica per produrre risultati "inconoscibili" in precedenza con valori di input.
• Tuttavia, i risultati quantistici sono probabilistici; non è concreto come dire "è veloce", perché devi renderlo veloce e giusto . Non facile da fare.
• Se riesci a trovare una scorciatoia quantistica per un problema e costruisci un computer quantistico e implementa tale scorciatoia all'interno del computer e trova il modo di ottenerlo con p > 0.5, sei su pista.
• Il grande "potenziale" è per l'algoritmo di Shor, che potrebbe ridurre la complessità computazionale del factoring semiprime in una classe sufficientemente bassa per poter calcolare in modo fattibile numeri molto grandi in un tempo più breve rispetto ai classici algoritmi .
• È un grande "se". Non sappiamo se effettivamente ridurrà la complessità computazionale, né sappiamo se è possibile implementare in modo efficiente. Anche se riusciremo a raggiungere entrambi, non sapremo quanto otterremo una riduzione della complessità. La speranza è che otterremo O ((log N) ³ ), ma noi non lo sappiamo realmente se potremo mai raggiungerlo in un'implementazione reale. E anche se questo è il caso, richiede ancora massiccia quantità di calcolo, che ci riporta al secondo punto che ho fatto: non sappiamo quanto i computer quantistici possano essere veramente veloci.
• Anche se rompiamo problemi di factoring semiprime come RSA, la crittografia quantistica porta nuovi problemi che non possono essere risolti facilmente, il che significa che avremo ancora un nuovo modo per tenere le cose al sicuro.

Non ho capito completamente la tua domanda, ma farò un tentativo. Per quanto mi ricordi, quel computer quantistico ti consentirà di risolvere in modo efficiente una classe di problemi che è BQP (secondo il factoring della conoscenza corrente è in BQP), che è più grande di P, ma non consiste in tutto il NP. Quindi non ti permetteranno di risolvere NP in modo efficiente.

L'algoritmo di Grovers fornirà un incremento di sqrt (n) per i problemi NP-completi. Quindi se hai stati 2 ^ n, applicando l'algoritmo di Grovers sarai in grado di ridurlo a 2 ^ (n / 2), che è veramente buono, ma comunque esponenziale.

Ci sono altri algoritmi che possono essere già usati. Mentre la fattorizzazione primaria relativa è il problema più comunemente usato per la crittografia asimmetrica, ci sono una serie di altri problemi noti (che non riesco a ricordare in cima alla mia testa al momento) che al momento non hanno un algoritmo quantistico noto da risolvere . Quindi nel breve termine, se / quando i computer quantistici esistono, abbiamo ancora un certo numero di algoritmi che si ritiene siano sicuri.

Il rovescio della medaglia è che se si diffondono, potremmo essere in grado di fare uso di crittografia quantistica diffusa come Quantum Key Distribution. L'idea di base, a quanto ho capito, è che è possibile utilizzare i principi della meccanica quantistica per garantire che vi sia un solo trasmettitore e un solo ricevitore dell'informazione in modo che diventi fisicamente impossibile per un utente malintenzionato ottenere un accesso significativo alle informazioni poiché se c'erano due persone che leggevano i dati, sarebbe diventato un casino confuso.