Teoria Quàntica de la Complexitat Computacional

La teoria quàntica de la complexitat computacional és un subcampo de la teoria de la complexitat computacional que estudia les diferents classes de complexitat que existixen des de la perspectiva de la computació quàntica. La computació quàntica, que és un model de computació que es beneficia de la superposició i entrelazamiento quàntic, conduïx a una redefinició de les classes de complexitat tradicionals. Açò s'explica perque hi ha problemes que són clásicamente irresolubles en temps polinòmic, pero que per mig d'un algoritme quàntic podrien resoldre's en temps polinòmic. És important tindre en conte que la teoria de la complexitat computacional és més que una revisió de la teoria clàssica anàloga: introduïx les seues pròpies classes i ha canviat el paradigma de la computació. Les classes més importants són la BQP i la QMA.

Introducció

Una classe de complexitat és una colecció o família de problemes computacionals que poden ser resolts subjectes a unes mateixes constricció en el tamany dels recursos; generalment, com a recurs més important i que servix per a delimitar les classes, es pren el temps de càlcul necessari. Aixina, per eixemple, la classe P comprén tots aquells problemes que puguen ser resolts per una màquina de Turing clàssica en un temps polinòmic. Per temps polinòmic es referix a que el temps de resolució escala polinómicamente en el tamany del problema (per eixemple, en l'algoritme de busca el temps escala com $O(N)$. Cuánticamente, les classes de complexitat es definixen similarmente a partir del temps que li prendria a una màquina de Turing quàntica o a un ordenador quàntic en un model circuital resoldre els problemes.

Un dels objectius de la teoria quàntica de la complexitat és relacionar les classes de complexitat de les dos teories. És important notar que el temps de resolució s'ha definit per mig de models de computació universals tant per al cas clàssic com per al quàntic. Açò es deu a que si no que un problema pertanyguera o no a una classe dependria de l'estat actual de la tecnologia. Un dels aspectes més importants de la teoria és que podria provar la falsetat de la tesis moderna de Church-Turing, segons la qual tot problema computacional podria ser simulat en temps polinòmic per una màquina de Turing provabilística (que donara la solució en precisió finita). Encara que existixen evidències que ho sugerixen, la tesis moderna de Church-Turing seguix sent un problema obert en la teoria de la computació.

Abans hem usat la notació $O(N)$. És l'anomenada notació asintòtica o notació de Landau. Més generalment, per a una funció $T(N)$, que un problema siga d'una complexitat $O(T(N))$ significa que és necessari un temps $cT(N)$ per a resoldre-ho, a on $c$ és una constant que indica el temps mig per iteración o, en major generalitat, el número mig d'unitats del recurs en qüestió, i $N$ és el tamany o número de bits involucrats en el problema. Si un problema és $\Omega (T(N))$, llavors pot ser resolt en un temps menor que $cT(N)$ i similarmente si el recurs no és el temps. Finalment,$\Theta (T(N))$ engloba abdós classes.

Classes de complexitat computacional

Algunes classes rellevants són P, BPP, BQP, PP, i P-SPACE. Per a definir una classe de complexitat primer es definix lo que es coneix com un problema de promesa (de l'anglés, promise problem). Un problema de promesa és un problema computacional que rep com a variable d'entrada una cadena de caràcters d'entre un conjunt de possibles entrades i que admet per solució una resposta que no és necessàriament sí o no; per eixemple, triar una lletra de l'alfabet llatí i respondre a si és o no vocal (cas en que sí admet una resposta binaria) o prendre una paraula del diccionari i dir quàntes vocals té (resposta no binaria). El problema queda definit llavors com un parell de conjunts $(A_{yes},A_{no})$, a on $A_{yes}$ és el conjunt d'instàncies per a l'entrada de les quals es va obtindre un sí i $A_{no}$ aquell per al que es va obtindre un no. Abdós conjunts no poden tindre instàncies en comuna, per lo que $A_{yes}\cap A_{no}=\mathrm{\varnothing }$. Ademés, l'unió d'abdós conjunts no constituïx, segons lo dit abans, el conjunt de totes les possibles respostes a dit problema de promesa.

Vore també

• Teoria de la complexitat computacional
• Classes de complexitat
• Classe P
• Computació quàntica
• Màquina de Turing
• Màquina de Turing universal
• Alan Turing
• Tesis de Church-Turing
• [1]
• Anex:Problemes no resolts de les ciències de la computació
• Criptografia quàntica