PostBQP (Complexitat)
En teoria de la complexitat, la classe de complexitat postBQP és el conjunt de tots els problemes que es poden solucionar amb temps polinòmic per una Màquina de Turing quàntica amb post-selecció amb un error fitat (en el sentit que l'algorisme és correcte almenys 2/3 de les vegades per totes les entrades).[1][2]
La post-selecció no es considera que sigui una característica realista per un ordinador (ni per un de quàntic), però des del punt de vista teòric són unes màquines interessants.
Relació amb d'altres classes
[modifica]Treient una de les dues característiques (que sigui una màquina quàntica o que tingui post-selecció) a la classe s'obtenen les següents classes, que son subconjunts de PostBQP:[3]
- BQP és la classe resultant de treure la post-selecció a PostBQP
- BPPPATH és la mateixa classe que PostBQP excepte que enlloc d'una màquina quàntica, l'algorisme és aleatori i clàssic amb post-selecció.
Afegir post-selecció a una màquina de Turing quàntica pot semblar que li dona més potència, però es va demostrar que PostBQP és igual a la classe PP.[1]
Referències
[modifica]- ↑ 1,0 1,1 Aaronson, Scott «Quantum Computing, Postselection, and Probabilistic Polynomial-Time». arXiv:quant-ph/0412187, 23-12-2004.
- ↑ «Complexity Zoo:P - Complexity Zoo». Arxivat de l'original el 2018-01-19. [Consulta: 8 gener 2019].
- ↑ «SIAM (Society for Industrial and Applied Mathematics)». DOI: 10.1137/s0097539792240467. [Consulta: 8 gener 2019].
| Considerades tractables | |
|---|---|
| Suposadament intractables | UP · NP · NP-complet · NP-hard · co-NP · co-NP-complet · AM · QMA · PH · ⊕P · PP · ♯P · ♯P-complet · IP · PSPACE · PSPACE-complet |
| Considerades intractables | |
| Jerarquia de classes | |
| Families de classes | |
