BQP (complexitat)

En complexitat computacional, BQP (bounded-error quantum polynomial time) és la classe de complexitat que conté els problemes de decisió que es poden resoldre amb un computador quàntic usant una quantitat de temps de computació polinòmic, amb una probabilitat d'error de com a molt 1/3 a totes les instàncies. És la classe anàloga quàntica de la classe BPP.

Un problema de decisió és de la classe BQP si existeix un algorisme quàntic (un algorisme que funciona en un computador quàntic) que resol el problema de decisió amb una alta probabilitat i es garanteix que ho fa en temps polinòmic. Una execució de l'algorisme soluciona el problema amb una probabilitat d'almenys 2/3.

Definició

BQP es pot veure com els llenguatges associats a certes families de circuits quàntics amb un error fitat. Un llenguatge L és a BQP si i només si existeix una família de circuits quàntics de complexitat polinòmica en temps $\{Q_n:n\in \mathbb{N}\}$tal que:

• per tot $n\in \mathbb{N}$, Q_n agafa n qubits com entrada i 1 bit de sortida.
• per tot x a L, $\mathrm{P}\mathrm{r}(Q_{|x|}(x)=1)\ge \frac{2}{3}$
• per tot x no a L, $\mathrm{P}\mathrm{r}(Q_{|x|}(x)=0)\ge \frac{2}{3}$

També es pot definir BQP en termes de màquines de Turing quàntiques. Un llenguatge L és a BQP si i només si existeix una màquina de Turing quàntica polinòmica que accepta L amb un error d'almenys 1/3 per totes les instàncies.

Relació amb d'altres classes

La suposada relació de BQP amb altres classes de complexitat

La classe està definida per un computador quàntic i la seva correspondència natural per un computador ordinari (o una màquina de Turing i una font d'atzar) és la classe BPP. Com les classes P i BPP, BQP compleix que BQP^BQP = BQP.

BQP conté P i BPP i està continguda dins AWPP, PP i PSPACE. Les relacions conegudes són les següents:

$𝖯\mathsf{\subseteq }𝖡𝖯𝖯\mathsf{\subseteq }𝖡𝖰𝖯\mathsf{\subseteq }𝖠𝖶𝖯𝖯\mathsf{\subseteq }𝖯𝖯\mathsf{\subseteq }𝖯𝖲𝖯𝖠𝖢𝖤$

La relació entre BQP i NP no es coneix. Afegint postselecció a BQP dona la classe de complexitat PostBQP que es equivalent a PP.