BQP (complessità)

Da Wikipedia, l'enciclopedia libera.
Lista di problemi irrisolti in informatica
Qual è la relazione tra BQP ed NP?
La presunta relazione di BQP con gli spazi di altri problemi.[1]

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 − nc da un lato, o richiedendo un errore piccolo fino a 2nc dall'altro, dove c è una qualsiasi costante positiva, ed n è la lunghezza dell'input.

Definizione[modifica | modifica sorgente]

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}, Qn 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[modifica | modifica sorgente]

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 ahnno 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:

Relazione con altre classi di complessità[modifica | modifica sorgente]

Questa classe è definita per un computer quantistico e la sua classe corrispodnente 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 BQPBQP = 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.

\mathbf{P} \subseteq \mathbf{BPP} \subseteq \mathbf{BQP}\subseteq \mathbf{AWPP} \subseteq \mathbf{PP} \subseteq \mathbf{PSPACE}

Poiché il problema di PPSPACE 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]

Note[modifica | modifica sorgente]

  1. ^ Michael Nielsen e Isaac Chuang (2000). Quantum Computation and Quantum Information. Cambridge, Cambridge University Press. ISBN 0-521-63503-9.
  2. ^ a b arXiv:quant-ph/9508027v2 Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Peter W. Shor
  3. ^ Lance Fortnow e John Rogers, Complexity limitations on Quantum computation in J. Comput. Syst. Sci., vol. 59, nº 2, Boston, MA, Academic Press, 1999, pp. 240–252. DOI:10.1006/jcss.1999.1651, ISSN 0022-0000.
  4. ^ L. Adleman, J. DeMarrais e M.-D. Huang. "Quantum computability". SIAM J. Comput., 26(5):1524–1540, 1997.
  5. ^ a b Bernstein and Vazirani, Quantum complexity theory, SIAM Journal on Computing, 26(5):1411-1473, 1997. [1]
  6. ^ Scott Aaronson, Quantum computing, postselection, and probabilistic polynomial-time in Proceedings of the Royal Society A, vol. 461, nº 2063, 2005, pp. 3473–3482. DOI:10.1098/rspa.2005.1546. Prestampa disponibile su [2]
  7. ^ Scott Aaronson, Complexity Class of the Week: PP in Computational Complexity Weblog, 11 gennaio 2004. URL consultato il 2 maggio 2008.