Algorisme quàntic
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ó.
Algorismes d'importància històrica
[modifica]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.
Referències
[modifica]- ↑ Mosca, Michele «Quantum Algorithms». arxiv:0808.0369, 03-08-2008 [Consulta: 18 agost 2010].
- ↑ David Deutsch and Richard Jozsa «Rapid solutions of problems by quantum computation». Proceedings of the Royal Society of London A, 439, 1992, pàg. 553.
- ↑ R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca «Quantum algorithms revisited» (PDF). Proceedings of the Royal Society of London A, 454, 1998, pàg. 339–354.
- ↑ Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (anglès)
- ↑ Grover, L.K.: A fast quantum mechanical algorithm for database search, Proceedings, 28th Annual ACM Symposium on the Theory of Computing, (May 1996) p. 212
- ↑ W.Shor, Peter «Scheme for reducing decoherence in quantum computer memory». Physical Reviews A, 1995.
Enllaços externs
[modifica]- El zoo d'algorismes quàntics: Una llista completa d'algorismes quàntics que són més ràpids que els algorismes clàssics més ràpids coneguts.
Bibliografia addicional
[modifica]- Michael Nielsen and Isaac Chuang. Quantum Computation and Quantum Information. Cambridge: Cambridge University Press, 2000. ISBN 0-521-63503-9. OCLC 174527496.
- J.Preskill, Lecture Noti for Physics: Quàntum Information and Computation