Algorisme quàntic

L'algorisme de Deutsch-Jozsa va ser proposat per David Deutsch i Richard Jozsa en 1992 i va ser millorat posteriorment per Richard Cleve, Artur Ekert, Chiara Macchiavello, i Michele Mosca el 1998.^[2][3] La seva funció és determinar si una funció de tipus caixa negra és «constant» o «balancejada».${\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}}$ Això és, donada una funció que per a una entrada de n bits dona un sol bit de sortida, determinar si la sortida és independent de l'entrada o si per a la meitat de les entrades és 0 i per a l'altra meitat és 1. El plantejament del problema exclou totes les altres possibles funcions. L'algorisme no té quasi utilitat pràctica, però és un dels primers exemples d'un algorisme quàntic que s'ha demostrat que és exponencialment més ràpid que qualsevol possible algorisme clàssic determinista.

L'algorisme de Shor, proposat per Peter Shor en 1995 i relacionat amb l'aritmètica modular, descompon en factors un nombre N en temps ${\displaystyle {\mathcal {O}}(\log N)^{3}}$ i espai ${\displaystyle {\mathcal {O}}(\log N)}$ ^[4] És responsable de bona part de l'atenció que se li ha dedicat a la computació quàntica, per la seva relació amb el problema RSA d'importància fonamental en criptografia.

L'algorisme de Grover, publicat per Lov Grover el 1996, va demostrar que un problema d'utilitat pràctica podia ser resolt més ràpidament que el millor algorisme clàssic possible.^[5] L'algorisme realitza una cerca en una base de dades desordenada amb N entrades en un nombre de passos d'ordre ${\displaystyle {\mathcal {O}}({\sqrt {N}})}$ , consumint un espai de memòria d'ordre ${\displaystyle {\mathcal {O}}(\log N)}$ .

El desenvolupament de la primera Correcció d'errors quàntics, proposta també per Peter Shor en 1995, va ser el primer pas cap a la computació quàntica a prova d'errors.^[6] Va suposar un avanç significatiu perquè per les lleis mecànica quàntica no és possible usar les estratègies habituals per a la detecció i correcció d'errors de la computació clàssica.