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.

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 ${\displaystyle \{Q_{n}:n\in \mathbb {N} \}}$, tale che

• Per tutti gli ${\displaystyle n\in \mathbb {N} }$, Q_n impiega n qubit come input ed emette 1 bit come output
• Per tutti gli x in L, ${\displaystyle \mathrm {Pr} (Q_{|x|}(x)=1)\geq {\tfrac {2}{3}}}$
• Per tutti gli x not in L, ${\displaystyle \mathrm {Pr} (Q_{|x|}(x)=0)\geq {\tfrac {2}{3}}}$

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)^[2]
• Logaritmo discreto^[2]
• Simulazione di sistemi quantistici (vedi simulatore universale quantico)
• Calcolo del polinomio di Jones in certe radici unitarie

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,^[3] PP^[4] e PSPACE.^[5] 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.

${\displaystyle \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.^[5] 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.^[6][7]

Portale Informatica

Portale Matematica