Diferència entre revisions de la pàgina «BQP (complexitat)»

m
corregit enllaç
m (corregit enllaç)
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 (complexitat)|P]] i [[BPP (complexitat)|BPP]], BQP compleix que '''BQP<sup>BQP</sup>''' = '''BQP.'''
 
BQP conté P i BPP i està continguda dins [[AWPP (complexitat)|AWPP]], [[PP (complexitat)|PP]] i [[PSPACE]].<ref>{{Ref-publicació|cognom=Fortnow|nom=Lance|cognom2=Rogers|nom2=John|article=Complexity Limitations on Quantum Computation|publicació=Journal of Computer and System Sciences|url=https://linkinghub.elsevier.com/retrieve/pii/S0022000099916513|volum=59|exemplar=2|data=1999-10|pàgines=240–252|doi=10.1006/jcss.1999.1651|issn=0022-0000}}</ref> Les relacions conegudes son les següents:<blockquote><math>{\mathsf {P\subseteq BPP\subseteq BQP\subseteq AWPP\subseteq PP\subseteq PSPACE}}</math></blockquote>La relació entre BQP i [[NP (Complexitat)|NP]] no es coneix. Afegint postselecció a BQP dona la classe de complexitat [[PostBQP (Complexitat)|PostBQP]] que es equivalent a PP.<ref>{{Ref-publicació|cognom=Aaronson|nom=Scott|article=Quantum computing, postselection, and probabilistic polynomial-time|publicació=Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences|llengua=en|url=http://rspa.royalsocietypublishing.org/content/461/2063/3473|volum=461|exemplar=2063|data=2005-11-08|pàgines=3473–3482|doi=10.1098/rspa.2005.1546|issn=1364-5021}}</ref>
 
== Referències ==
3.227

modificacions