Algoritmo quantistico

Un algoritmo quantistico è un algoritmo progettato per essere eseguito su un modello realistico di computazione quantistica. Il modello più comunemente usato è quello del circuito quantistico.^[1]^[2] Come un algoritmo classico è una sequenza finita di istruzioni, o una procedura passo passo per risolvere un problema, progettato per essere eseguito su un computer classico, così un algoritmo quantistico è una procedura passo passo progettata per essere eseguita su un quantum computer. Sebbene tutti gli algoritmi classici possono anche essere eseguiti su un computer quantistico,^[3] il termine "algoritmo quantistico" viene solitamente usato per quegli algoritmi che sembrano intrinsecamente quantistici, o che usano caratteristiche peculiari della computazione quantistica come la sovrapposizione degli stati o l'entanglement quantistico.

I problemi indecidibili con i computer classici rimangono indecidibili anche con i computer quantistici.^[1] Ciò che rende gli algoritmi quantistici degni di interesse è che potrebbero essere in grado di risolvere alcuni problemi più velocemente dei computer classici perché la sovrapposizione degli stati e l'entanglement quantistico che vengono sfruttati dagli algoritmi quantistici non possono essere simulati efficacemente sui computer classici (supremazia quantistica).

Gli algoritmi più conosciuti sono l'algoritmo di fattorizzazione di Shor e l'algoritmo di Grover per cercare in un database indifferenziato. L'algoritmo di Shor gira molto più velocemente del miglior algoritmo classico conosciuto per la fattorizzazione, il crivello dei campi di numeri generale.^[4] L'algoritmo di Grover gira quadraticamente più veloce della ricerca sequenziale.