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 wikitesto]

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 , tale che

  • Per tutti gli , Qn impiega n qubit come input ed emette 1 bit come output
  • Per tutti gli x in L,
  • Per tutti gli x not in L,

Computazione quantistica[modifica | modifica wikitesto]

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:

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

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.

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 wikitesto]

  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 (PDF), 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, su Computational Complexity Weblog, 11 gennaio 2004. URL consultato il 2 maggio 2008.