BQP

En teoria de la complexitat computacional, BQP (temps polinomial quàntic en error acotat) és la classe de problemes de decisió decidibles per un ordenador quàntic en temps polinomial en una provabilitat d'error de com a molt 1/3 per a totes les instàncies. És l'anàlec quàntic a la classe de complexitat BPP.

Un problema de decisió pertany a BQP si existix un algoritme quàntic (un algoritme que s'eixecuta en un ordenador quàntic) que resol el problema de decisió en alta provabilitat i que s'eixecuta en temps polinomial. Una eixecució de l'algoritme resoldrà correctament el problema de decisió en una provabilitat d'a lo manco 2/3.

Definició

BQP pot vore's com el conjunt dels llenguages associats a certes famílies uniformes de circuits quàntics. Un llenguage L pertany a BQP si i solament si existix una família polinomial uniforme de circuits quàntics $\{Q_n:n\in \mathbb{N}\}$, tal que:

• Per a tot $n\in \mathbb{N}$, Q_n pren n qubits com a entrada i produïx 1 bit com a eixida
• Per a cada x en L $\mathrm{P}\mathrm{r}(Q_{|x|}(x)=1)\ge \frac{2}{3}$
• Per a cada x que no estiga en L, $\mathrm{P}\mathrm{r}(Q_{|x|}(x)=0)\ge \frac{2}{3}$

Alternativament BQP pot ser definida en térmens de màquines de Turing quàntiques. Un llenguage L pertany a BQP si i solament si existix una màquina de Turing quàntica polinomial que accepta L en una provabilitat d'error de com a molt 1/3 per a totes les instàncies.

Com ocorre en atres classes provabilístiques en "error acotat", l'elecció d'1/3 en la definició és arbitrària. Podem eixecutar l'algoritme un número constant de voltes i decidir per majoria per a conseguir qualsevol provabilitat d'error desijada major que 0 utilisant les cotes de Chernoff. La classe de complexitat tampoc canvia si permetem un error tan gran com 1/2 − n^−c, a on c és qualsevol constant positiva i n és la llongitut de l'entrada.

Computació quàntica

El número de qubits en l'ordenador és una funció polinomial del tamany de l'entrada. Per eixemple, en el cas del algoritme de Shor, un sancer expressat en n-bits pot factorizarse utilisant aproximadament 2n qubits.

Normalment els càlculs en un ordenador quàntic terminen en una medició. Açò du al colapse d'un estat quàntic a un dels estats de la base. L'estat quàntic medit serà l'estat correcte en alta provabilitat.

La computació quàntica ha despertat interés degut a que hi ha problemes de caràcter pràctic que es creu que no pertanyen a P pero sí pertanyen a la classe BQP. Alguns eixemples són:

• Factorización sancera (vore algoritme de Shor).
• Logaritmo discret.

Simulació de sistemes quàntics. Aproximació del polinomi de Jones a certes raïls de l'unitat.

Vore també

• Teoria de la complexitat quàntica