Quantum computers and Turing Machine

1) Come hai sottolineato, gran parte della teoria su "ciò che può essere calcolato" si basa su di essa. Per questo, è essenziale sapere come opera internamente. Una macchina di Turing non è una scatola nera. Una proprietà favorevole delle macchine di Turing è la loro località di cambiamento. Ogni passaggio cambia solo pochissimo, cioè lo stato interno (pensiamolo come numero), la lettera sul nastro e la posizione sul nastro. Quest'ultimo può essere modificato solo di 1 passo a sinistra oa destra. In questo modello tutti gli input sono in forma di ciò che è scritto sul nastro. Il contenuto del nastro viene modificato solo dalla macchina. Quindi - nessuna interazione.

2) Una macchina o un linguaggio di programmazione si chiama Turing completo, se è in grado di simulare tutte le macchine di Turing. Quindi, le macchine di Turing non deterministiche sono complete di Turing, perché possono simulare una macchina di Turing semplicemente non usando il non-determinismo. È interessante notare come un Turing deterministico possa simulare uno non deterministico, semplicemente cercando tutti i possibili risultati di risultati non deterministici in sequenza. Questo è un approccio a forza bruta e non molto efficiente. Non è chiaro se esiste un modo efficace per farlo. A proposito, la maggior parte degli informatici non pensa che si possa fare.

Per quanto riguarda la tua risposta a questo - le macchine di Turing dovrebbero fermarsi. In questo contesto significa che il calcolo è finito e ha un risultato. Potresti pensare che significhi che la macchina si ghiaccia. Ma è il contrario. Una macchina congelata (ad esempio il tuo computer desktop) non si fermava, quando doveva e sapeva che ti aspettavi per sempre e non puoi fare nulla (ma riavviare). Il non-determinismo non ha alcun effetto su un arresto o meno della macchina.

3) L'unico modo conosciuto per simulare un dispositivo di calcolo quantistico utilizza il non determinismo. Come detto al punto 2), possiamo simulare il non-determinismo, ma non in modo efficiente. E probabilmente non lo faremo mai.

I computer quantistici sono ancora entro i limiti di Turing-complete. Puoi simularne esattamente uno con una macchina normale, richiederebbe semplicemente un tempo esponenziale. Naturalmente, le classi di complessità non sono necessariamente le stesse - per esempio, la fattorizzazione discreta è un problema NP-hard su un computer classico ma un algoritmo quantistico può farlo in un tempo lineare.

I computer quantistici non infrangono fondamentalmente le regole del calcolo. Nessun computer quantistico può risolvere il problema dell'arresto, o qualcosa del genere. Possono semplicemente eseguire alcuni tipi di calcolo molto, molto più velocemente di un computer classico. È esattamente come avere una macchina classica esponenzialmente più veloce.

Sebbene i computer quantistici possano essere più veloci dei computer classici, non possono risolvere i problemi che i computer classici non sono in grado di risolvere. Una macchina di Turing può simulare questi computer quantistici, quindi un tale computer quantistico non potrebbe mai risolvere un problema indecidibile come il problema dell'arresto. C'è un malinteso comune che i computer quantistici possano risolvere problemi NP-completi in tempo polinomiale. Questo non è noto per essere vero, ed è generalmente sospettato di essere falso. L'esistenza di computer quantistici "standard" non smentisce la tesi di Church-Turing. La macchina D-Wave sta risolvendo i problemi usando la tecnologia quantistica ma non è un "uso generale" o un computer standard in alcun senso del termine. Che faccia quello che fa è grandioso e sarà affascinante vedere cosa ci riserva il futuro. Vedi i riferimenti citati nella voce di Wikipedia.