Teoria de la complexitat quàntica

La teoria de la complexitat quàntica és el subcamp de la teoria de la complexitat computacional que s'ocupa de les classes de complexitat definides mitjançant ordinadors quàntics, un model computacional basat en la mecànica quàntica. Estudia la duresa dels problemes computacionals en relació amb aquestes classes de complexitat, així com la relació entre les classes de complexitat quàntica i les classes de complexitat clàssiques (és a dir, no quàntiques).

Dues classes de complexitat quàntica importants són BQP i QMA.

Rerefons

Una classe de complexitat és una col·lecció de problemes computacionals que es poden resoldre mitjançant un model computacional sota determinades restriccions de recursos. Per exemple, la classe de complexitat P es defineix com el conjunt de problemes resolubles per una màquina de Turing en temps polinomial. De la mateixa manera, les classes de complexitat quàntica es poden definir utilitzant models quàntics de càlcul, com el model de circuit quàntic o la màquina de Turing quàntica equivalent. Un dels principals objectius de la teoria de la complexitat quàntica és esbrinar com es relacionen aquestes classes amb les classes de complexitat clàssiques com ara P, NP, BPP i PSPACE.

Una de les raons per les quals s'estudia la teoria de la complexitat quàntica són les implicacions de la computació quàntica per a la tesi moderna de Church-Turing. En resum, la tesi moderna de Church-Turing afirma que qualsevol model computacional pot ser simulat en temps polinomial amb una màquina probabilística de Turing. No obstant això, les preguntes al voltant de la tesi Church-Turing sorgeixen en el context de la computació quàntica. No és clar si la tesi Church-Turing és vàlida per al model de càlcul quàntic. Hi ha moltes proves que la tesi no s'afirma. Pot ser que una màquina probabilística de Turing no sigui possible simular models de càlcul quàntic en temps polinomial.

Tant la complexitat computacional quàntica de les funcions com la complexitat computacional clàssica de les funcions sovint s'expressen amb notació asimptòtica. Algunes formes comunes de noció asimptòtica de funcions són $O(T(n))$, $\mathrm{\Omega }(T(n))$, i $\mathrm{\Theta }(T(n))$. $O(T(n))$ expressa que alguna cosa està limitada per sobre $cT(n)$ on $c$ és una constant tal que $c>0$ i $T(n)$ és una funció de $n$, $\mathrm{\Omega }(T(n))$ expressa que alguna cosa està limitada per sota $cT(n)$ on $c$ és una constant tal que $c>0$ i $T(n)$ és una funció de $n$, i $\mathrm{\Theta }(T(n))$ expressa tots dos $O(T(n))$ i $\mathrm{\Omega }(T(n))$. Aquestes anotacions també tenen els seus propis noms. $O(T(n))$ s'anomena notació O gran, $\mathrm{\Omega }(T(n))$ s'anomena notació Big Omega, i $\mathrm{\Theta }(T(n))$ s'anomena notació Big Theta.

Visió general de les classes de complexitat

Les classes de complexitat importants P, BPP, BQP, PP i PSPACE es poden comparar basant-se en problemes de promeses. Un problema de promesa és un problema de decisió que té una entrada que se suposa seleccionada del conjunt de totes les cadenes d'entrada possibles. Un problema de la promesa és una parella $A=(A_{\text{yes}},A_{\text{no}})$, on $A_{\text{yes}}$ és el conjunt de casos sí i $A_{\text{no}}$ és el conjunt de no instàncies, i la intersecció d'aquests conjunts és buida: $A_{\text{yes}}\cap A_{\text{no}}=\varnothing$. Totes les classes de complexitat anteriors contenen problemes de promeses.

Classe de complexitat	Criteris
P	Problemes de promesa per als quals una màquina de Turing determinista de temps polinomi accepta totes les cadenes $A_{\text{yes}}$ i rebutja totes les cadenes $A_{\text{no}}$
BPP	Problemes de promesa per als quals una màquina probabilística de Turing de temps polinomi accepta totes les cadenes $A_{\text{yes}}$ amb una probabilitat d'almenys $\frac{2}{3}$, i accepta totes les cadenes a $A_{\text{no}}$ amb una probabilitat de com a màxim $\frac{1}{3}$
BQP	Promet problemes com per a funcions $a,b:\mathbb{N}\to [0,1]$, existeix una família de circuits quàntics generats en temps polinomial $Q=\{Q_n:n\in \mathbb{N}\}$, on $Q_n$ és un circuit que accepta $n$ qubits i dona una sortida d'un qubit. Un element $x$ de $A_{\text{yes}}$ és acceptat per $Q$ amb una probabilitat superior o igual a $a(\left|x\right|)$. Un element $x$ de $A_{\text{no}}$ és acceptat per $Q$ amb una probabilitat menor o igual a $b(\left|x\right|)$.
PP	Problemes de promesa per als quals una màquina probabilística de Turing de temps polinomi accepta totes les cadenes $A_{\text{yes}}$ amb una probabilitat superior a $\frac{1}{2}$, i accepta totes les cadenes a $A_{\text{no}}$ amb una probabilitat de com a màxim $\frac{1}{2}$
PSPACE	Problemes de promesa per als quals una màquina de Turing determinista, que funciona en un espai polinomial, accepta totes les cadenes de $A_{\text{yes}}$ i rebutja totes les cadenes $A_{\text{no}}$