Algoritme quàntic

Algoritme quàntic

Transformada quàntica de Fourier sobre tres qubits, basada en l'aplicació reiterada de la porta quàntica d'Hadamard i de portes de canvi de fase.

Un algoritme quàntic és un algoritme que s'eixecuta en un modele realista de computació quàntica, com el model de circuit quàntic, com el que s'ilustra en la figura. La teoria de la complexitat computacional li assigna la classe BQP als algoritmes que poden ser resolts en un computador quàntic en temps polinòmic en un marge d'error promig inferior a 1/4. En l'anàlisis dels algoritmes quàntics és habitual comparar la cota superior asintòtica en el millor algoritme clàssic conegut, o, si el problema està resolt, en el millor algoritme clàssic possible. S'usa la notació de Landau per a definir la relació entre la talla de l'entrada del problema i el número de passos necessaris per a resoldre-ho, o el número de posicions de memòria que s'utilisen durant la seua resolució.

Algoritmes d'importància històrica

Vore també: Algoritme de Deutsch-Jozsa, Algoritme de Shor, Algoritme de Grover, i Algoritme de Bernstein–Vazirani

l'algoritme de Deutsch-Jozsa va ser propost per David Deutsch i Richard Jozsa en 1992 i va ser millorat posteriorment per Richard Cleve, Artur Ekert, Chiara Macchiavello, i Michele Mosca en 1998. La seua funció és determinar si una funció de tipo caixa negra $f:\{0,1{\}}^n\to \{0,1\}$ és «constant» o «balancejada». Açò és, donada una funció que per a una entrada de n bits dona un sol bit d'eixida, determinar si l'eixida és independent de l'entrada o si per a la mitat de les entrades és 0 i per a l'atra mitat és 1. El plantejament del problema exclou totes les atres possibles funcions. L'algoritme no té a penes utilitat pràctica, pero és un dels primers eixemples d'un algoritme quàntic que s'ha demostrat que és exponencialment més ràpit que qualsevol possible algoritme clàssic determinista.

l'algoritme de Shor, propost per Peter Shor en 1995 i relacionat en l'aritmètica modular, descompon en factors un número N en temps $𝒪(\log N{)}^3$ i espai $𝒪(\log N)$. És responsable de bona part de l'atenció que se li ha dedicat a la computació quàntica, per la seua relació en el problema RSA d'importància fonamental en criptografia.

l'algoritme de Grover, publicat per Lov Grover en 1996, va demostrar que un problema d'utilitat pràctica podia ser resolt més ràpidament que el millor algoritme clàssic possible. L'algoritme realisa una busca en una base de senyes desordenada en N entrades en un número de passos d'orde $𝒪(\sqrt{N})$, consumint un espai de memòria d'orde $𝒪(\log N)$.

El desenroll de la primera correcció d'errors quàntica, proposta també per Peter Shor en 1995, va ser el primer pas cap a la computació quàntica a prova d'errors. Va supondre un alvanç significatiu perque 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.

Bibliografia adicional

• Michael Nielsen and Isaac Chuang (2000). Quàntum Computation and Quàntum Information, Cambridge: Cambridge University Press. OCLC 174527496. ISBN 0-521-63503-9.

• J.Preskill, Lecture Note for Physics: Quàntum Information and Computation [1] archivat en Wayback Machine.