Ver el código de «BQP»

En [[teoría de la complejidad computacional]], '''BQP''' (tiempo polinomial cuántico con error acotado) es la clase de [[Problema de decisión|problemas de decisión]] decidibles por un [[ordenador cuántico]] en [[tiempo polinomial]] con una probabilidad de error de como mucho 1/3 para todas las instancias.<ref name=Chuang2000>{{cita libro |apellido=Nielsen|apellido2=Chuang|nombre=Michael|nombre2=Isaac|título= Quantum Computation and Quantum Information|idioma=en|edición=décima |año=2000 |editorial=Cambridge University Press|isbn=0-521-63503-9}}</ref> Es el análogo cuántico a la clase de complejidad '''[[BPP (clase de complejidad)|BPP]]'''.

Un problema de decisión pertenece a '''BQP''' si existe un [[algoritmo cuántico]] (un [[algoritmo]] que se ejecuta en un ordenador cuántico) que resuelve el problema de decisión con ''alta'' probabilidad y que se ejecuta en tiempo polinomial. Una ejecución del algoritmo resolverá correctamente el problema de decisión con una probabilidad de al menos 2/3.

==Definición==

'''BQP''' puede verse como el conjunto de los lenguajes asociados a ciertas familias uniformes de [[circuito cuántico|circuitos cuánticos]].<ref name=Chuang2000/> Un lenguaje ''L'' pertenece a '''BQP''' si y solo si existe una familia polinomial uniforme de circuitos cuánticos <math>\{Q_n:n \in \mathbb{N}\}</math>, tal que:
* Para todo <math>n \in \mathbb{N}</math>, ''Q<sub>n</sub>'' toma ''n'' qubits como entrada y produce 1 bit como salida
* Para cada ''x'' en ''L'' <math>\mathrm{Pr}(Q_{|x|}(x)=1)\geq \tfrac{2}{3}</math>
* Para cada ''x'' que no esté en ''L'', <math>\mathrm{Pr}(Q_{|x|}(x)=0)\geq  \tfrac{2}{3}</math>

Alternativamente '''BQP''' puede ser definida en términos de [[Máquina de Turing#Máquina de Turing cuántica|máquinas de Turing cuánticas]]. Un lenguaje ''L'' pertenece a '''BQP''' si y solo si existe una máquina de Turing cuántica polinomial que acepta ''L'' con una probabilidad de error de como mucho 1/3 para todas las instancias.<ref name="BernVazi">{{cite journal |last1=Bernstein |first1=Ethan |last2=Vazirani |first2=Umesh |title=Quantum Complexity Theory |journal=SIAM Journal on Computing |date=October 1997 |volume=26 |issue=5 |pages=1411–1473 |doi=10.1137/S0097539796300921 |url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.655.1186&rep=rep1&type=pdf |accessdate=23 de julio de 2018 |ref=BernVazi}}</ref>

Como ocurre con otras clases probabilísticas con "error acotado", la elección de 1/3 en la definición es arbitraria. Podemos ejecutar el algoritmo un número constante de veces y decidir por mayoría para conseguir cualquier probabilidad de error deseada mayor que 0 utilizando las [[cotas de Chernoff]]. La [[clase de complejidad]] tampoco cambia si permitimos un error tan grande como 1/2 − ''n''<sup>−''c''</sup>, donde ''c'' es cualquier constante positiva y ''n'' es la longitud de la entrada.<ref>{{cite book |last1=Barak |first1=Sanjeev Arora, Boaz |title=Computational Complexity: A Modern Approach / Sanjeev Arora and Boaz Barak |date=2009 |location=Cambridge |page=122 |url=http://www.cs.princeton.edu/theory/complexity/ |accessdate=24 de julio de 2018}}</ref>

==Computación cuántica==

El número de [[qubit]]s en el ordenador es una función polinomial del tamaño de la entrada. Por ejemplo, en el caso del [[algoritmo de Shor]], un entero expresado en ''n''-bits puede factorizarse utilizando aproximadamente 2''n'' qubits.

Normalmente los cálculos en un ordenador cuántico terminan en una [[Medición#Mecánica_cuántica|medición]]. Esto lleva al [[Colapso de la función de onda|colapso]] de un estado cuántico a uno de los [[Estado cuántico|estados de la base]]. El estado cuántico medido será el estado correcto con alta probabilidad.

La computación cuántica ha despertado interés debido a que hay problemas de carácter práctico que se cree que no pertenecen a P pero sí pertenecen a la clase BQP. Algunos ejemplos son:

*[[Factorización de enteros|Factorización entera]] (ver [[algoritmo de Shor]]).<ref name="Shor">[http://www.arxiv.org/abs/quant-ph/9508027 arXiv:quant-ph/9508027v2 ''Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer'', Peter W. Shor]</ref>
*[[Logaritmo discreto]].
*Simulación de sistemas cuánticos.
*Aproximación del [[polinomio de Jones]] a ciertas raíces de la unidad.

==Relación con otras clases de complejidad==

[[Image:BQP complexity class diagram.svg|thumb|La relación que se conjetura entre '''BQP''' y otras clases de complejidad.<ref name=Chuang2000/>]]

'''BQP''' está definida para un ordenador cuántico. Su correspondencia natural para un ordenador clásico (o una [[máquina de Turing]] junto con una fuente aleatoria) es '''[[BPP (complejidad)|BPP]]'''.

Como ocurre con '''P''' y '''BPP''', '''BQP''' verifica '''BQP'''<sup>'''BQP'''</sup> = '''BQP'''.<ref name="BernVazi"/>
Informalmente, esto es cierto ya que los algoritmos que toman un tiempo polinomial son cerrados bajo composición. Si un algoritmo polinomial llama a una [[subrutina]] polinomial un número polinomial de veces, el algoritmo resultante será también polinomial.

'''BQP''' contiene a '''[[P (clase de complejidad)|P]]''' y '''[[BPP (clase de complejidad)|BPP]]''' y está contenida en '''[[AWPP (clase de complejidad)|AWPP]]''',<ref>{{Cite journal | last1=Fortnow | first1=Lance | last2=Rogers | first2=John | title=Complexity limitations on Quantum computation | url=http://people.cs.uchicago.edu/~fortnow/papers/quantum.pdf | publisher=[[Academic Press]] | location=Boston, MA | year=1999 | journal=J. Comput. Syst. Sci. | issn=0022-0000 | volume=59 | issue=2 | pages=240–252 | doi=10.1006/jcss.1999.1651 | postscript=<!--None-->}}</ref> '''[[PP (complexity)|PP]]'''<ref>L. Adleman, J. DeMarrais, and M.-D. Huang. Quantum computability. SIAM J. Comput.,
26(5):1524–1540, 1997.</ref> y '''[[PSPACE]]'''.<ref name=BernVazi/>

'''BQP''' es [[baja (complejidad)|baja]] para '''PP''', con lo que una máquina '''PP''' no obtiene beneficio de resolver problemas en '''BQP''' instantáneamente, lo que proporciona evidencia de la posible diferencia de poder entre las dos clases. Las principales relaciones conocidas con clases de complejidad clásicas son
:<math>\mathsf{P \subseteq BPP \subseteq BQP\subseteq AWPP \subseteq PP \subseteq PSPACE}</math>

Dado que el problema de '''P ≟ PSPACE''' aún no ha sido resuelto, se supone que la demostración de la desigualdad estricta entre estas clases y '''BQP''' es difícil.<ref name=BernVazi/> No se conoce la relación entre '''BQP''' y '''[[NP (clase de complejidad)|NP]]''', aunque se conjetura que son incomparables. Desde mayo de 2018 se conoce que, relativa a un [[Máquina oráculo|oráculo]], '''BQP''' no está contenida en '''[[PH (clase de complejidad)|PH]]''' (una generalización de '''NP''').<ref>[https://eccc.weizmann.ac.il/report/2018/107/]</ref>

Añadiendo [[postselección]] a '''BQP''' obtenemos la clase de complejidad '''[[PostBQP]]''' que es igual a '''[[PP (complejidad)|PP]]'''.<ref name="PostBQP=PP">{{cite journal|title=Quantum computing, postselection, and probabilistic polynomial-time|journal=Proceedings of the Royal Society A|volume=461|issue=2063|pages=3473–3482|bibcode=2005RSPSA.461.3473A|doi=10.1098/rspa.2005.1546|year=2005|last=Aaronson|first=Scott|arxiv=quant-ph/0412187}}.  Preprint available at [https://arxiv.org/abs/quant-ph/0412187]</ref><ref>{{cite web|url=http://weblog.fortnow.com/2004/01/complexity-class-of-week-pp-by-guest.html|title=Complexity Class of the Week: PP|last=Aaronson|first=Scott|date=11 de enero de 2004|work=Computational Complexity Weblog|accessdate=2 de mayo de 2008}}</ref>

==Véase también==
* [[Teoría de la complejidad cuántica]]

==Referencias==
{{listaref}}

== Enlaces externos ==
*  [https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#bqp Enlace de Complexity Zoo a BQP] {{Wayback|url=https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#bqp |date=20130603134129 }}

{{Control de autoridades}}
[[Categoría:Clases de complejidad]]
[[Categoría:Informática cuántica]]
[[Categoría:Información cuántica]]