# BQP (complessità)

Nella teoria della complessità computazionale, BQP (Bounded-error Quantum Polynomial-time, "tempo polinomiale quantistico con errore limitato") è una classe di complessità a cui appartengono quei problemi che richiedono un tempo polinomiale da parte di un computer quantistico per avere una soluzione corretta con probabilità maggiore o uguale a 2/3 e quindi, corrispondentemente, con una probabilità di errore minore o uguale a 1/3. È l'analogo quantistico della classe BPP.
In altre parole, c'è un algoritmo per un computer quantistico (un algoritmo quantistico) che risolve il problema decisionale con un'alta probabilità ed è garantito che si esegue in tempo polinomiale. In qualsiasi esecuzione data dell'algoritmo, ha una probabilità al massimo di 1/3 di dare la risposta sbagliata.
Similmente ad altre classi probabilistiche con "errore limitato" la scelta di 1/3 nella definizione è arbitraria. Possiamo eseguire l'algoritmo un numero costante di volte e decidere con un voto a maggioranza di assumere qualsiasi probabilità di correttezza desiderata minore di 1, usando la disuguaglianza di Chernoff. L'analisi dettagliata mostra che la classe di complessità è invariata consentendo un errore elevato fino a 1/2 − n$^{−c}$ da un lato, o richiedendo un errore piccolo fino a 2$^{−nc}$ dall'altro, dove c è una qualsiasi costante positiva, ed n è la lunghezza dell'input.

## Definizione

BQP può essere vista anche come una famiglia uniforme di circuiti quantistici con errore limitato. Un linguaggio L è in BQP se e solo se esiste una famiglia uniforme in tempo polinomiale di circuiti quantistici $\{Q_{n}:n\in \mathbb {N} \}$, tale che
* Per tutti gli $n\in \mathbb {N}$, Q$_n$ impiega n qubit come input ed emette 1 bit come output
* Per tutti gli x in L, $\mathrm {Pr} (Q_{|x|}(x)=1)\geq {\tfrac {2}{3}}$
* Per tutti gli x not in L, $\mathrm {Pr} (Q_{|x|}(x)=0)\geq {\tfrac {2}{3}}$

## Computazione quantistica

Il numero di qubit nel computer può essere una funzione polinomiale della dimensione dell'istanza. Ad esempio, è noto che alcuni algoritmi fattorizzano un intero di n bit usando poco più di 2n qubit (algoritmo di Shor).
Solitamente, la computazione su un computer quantistico finisce con una misurazione. Questo conduce a un collasso dello stato quantistico a uno degli stati fondamentali. Si può dire che si misura che lo stato quantico è nello stato corretto con un'alta probabilità.
I computer quantistici hanno ottenuto interesse diffuso perché è noto che alcuni problemi di interesse pratico sono in BQP, ma si sospetta che siano fuori da P. Alcuni esempi rilevanti sono:
* Fattorizzazione degli interi (vedi l'algoritmo di Shor)
* Logaritmo discreto
* Simulazione di sistemi quantistici (vedi simulatore universale quantico)
* Calcolo del polinomio di Jones in certe radici unitarie

## Relazione con altre classi di complessità

Questa classe è definita per un computer quantistico e la sua classe corrispondente naturale per un computer ordinario (o una macchina di Turing più una sorgente di casualità) è BPP. Proprio come P e BPP, BQP è di per sé bassa, il che significa BQP$^{BQP}$ = BQP. Informalmente, questo è vero perché gli algoritmi in tempo polinomiale sono chiusi nell'ambito della composizione. Se un algoritmo in tempo polinomiale richiama polinomialmente come subroutine molti algoritmi in tempo polinomiale, l'algoritmo risultante è ancora in tempo polinomiale.
BQP contiene P e BPP ed è contenuta in AWPP, PP e PSPACE. Infatti, BQP è bassa per PP, vale a dire che una macchina PP non consegue nessun beneficio dall'essere in grado di risolvere istantaneamente problemi BQP, un'indicazione della possibile differenza di potenza tra queste classi similari.
    $\mathbf {P} \subseteq \mathbf {BPP} \subseteq \mathbf {BQP} \subseteq \mathbf {AWPP} \subseteq \mathbf {PP} \subseteq \mathbf {PSPACE}$
Poiché il problema di P ≟ PSPACE non è ancora stato risolto, si suppone che la prova della disuguaglianza tra BQP e le classi menzionate sopra sia difficile. La relazione tra BQP e NP non è conosciuta.
Aggiungere la post-selezione a BQP dà come risultato la classe di complessità PostBQP che è uguale a PP.