BQP (complexitat)
En complexitat computacional, BQP (bounded-error quantum polynomial time) és la classe de complexitat que conté els problemes de decisió que es poden resoldre amb un computador quàntic usant una quantitat de temps de computació polinòmic, amb una probabilitat d'error de com a molt 1/3 a totes les instàncies.[1] És la classe anàloga quàntica de la classe BPP.
Un problema de decisió és de la classe BQP si existeix un algorisme quàntic (un algorisme que funciona en un computador quàntic) que resol el problema de decisió amb una alta probabilitat i es garanteix que ho fa en temps polinòmic. Una execució de l'algorisme soluciona el problema amb una probabilitat d'almenys 2/3.
Definició
BQP es pot veure com els llenguatges associats a certes families de circuits quàntics amb un error fitat. Un llenguatge L és a BQP si i només si existeix una família de circuits quàntics de complexitat polinòmica en temps tal que:
- per tot , Qn agafa n qubits com entrada i 1 bit de sortida.
- per tot x a L,
- per tot x no a L,
També es pot definir BQP en termes de màquines de Turing quàntiques. Un llenguatge L és a BQP si i només si existeix una màquina de Turing quàntica polinòmica que accepta L amb un error d'almenys 1/3 per totes les instàncies.[2]
Relació amb d'altres classes
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1d/BQP_complexity_class_diagram.svg/220px-BQP_complexity_class_diagram.svg.png)
La classe està definida per un computador quàntic i la seva correspondència natural per un computador ordinari (o una màquina de Turing i una font d'atzar) és la classe BPP. Com les classes P i BPP, BQP compleix que BQPBQP = BQP.
BQP conté P i BPP i està continguda dins AWPP, PP i PSPACE.[3] Les relacions conegudes són les següents:
La relació entre BQP i NP no es coneix. Afegint postselecció a BQP dona la classe de complexitat PostBQP que es equivalent a PP.[4]
Referències
- ↑ 1974-, Nielsen, Michael A.,. Quantum computation and quantum information. Cambridge: Cambridge University Press, 2000. ISBN 0521632358.
- ↑ Bernstein, Ethan; Vazirani, Umesh «Quantum Complexity Theory» (en anglès). SIAM Journal on Computing, 26, 5, 1997-10, pàg. 1411–1473. DOI: 10.1137/s0097539796300921. ISSN: 0097-5397.
- ↑ Fortnow, Lance; Rogers, John «Complexity Limitations on Quantum Computation». Journal of Computer and System Sciences, 59, 2, 1999-10, pàg. 240–252. DOI: 10.1006/jcss.1999.1651. ISSN: 0022-0000.
- ↑ Aaronson, Scott «Quantum computing, postselection, and probabilistic polynomial-time» (en anglès). Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 461, 2063, 08-11-2005, pàg. 3473–3482. DOI: 10.1098/rspa.2005.1546. ISSN: 1364-5021.