Un algorisme quàntic és un algorisme que s'executa en un model realista de computació quàntica, com el model de circuit quàntic, com el que s'il·lustra en la figura.[1] La teoria de la complexitat computacional li assigna la classe BQP als algorismes que poden ser resolts en un computador quàntic en temps polinòmic amb un marge d'error mitjà inferior a 1/4. En l'anàlisi dels algorismes quàntics és habitual comparar la cota superior asimptòtica amb el millor algorisme clàssic conegut, o, si el problema està resolt, amb el millor algorisme clàssic possible. S'usa la notació de Landau per definir la relació entre la talla de l'entrada del problema i el nombre de passos necessaris per resoldre-ho, o el nombre de posicions de memòria que s'utilitzen durant la seva resolució.
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». 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 i espai [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 , consumint un espai de memòria d'ordre .
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.
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
