Mostrar código-fonte de BQP

{{unsolved|ciência da computação|Qual a relação entre '''BQP''' e '''NP'''?}}
[[Imagem:BQP complexity class diagram.svg|thumb|A relação suspeita entre '''BQP''' para outros espaços de problemas<ref>Michael Nielsen and Isaac Chuang (2000). ''Quantum Computation and Quantum Information''. Cambridge: Cambridge University Press. ISBN 0-521-63503-9.</ref>]]
Em [[Complexidade computacional|Teoria da Complexidade Computacional]], '''BQP''' (''do inglês'' bounded error quantum polynomial time) é a classe de [[Problema de decisão|problemas de decisão]] solúveis por um [[computador quântico]] em [[Complexidade temporal|tempo polinomial]], com uma probabilidade de erro de até 1/3 para todas as instâncias. É a classe quântica análoga da classe de complexidade '''[[BPP]]'''.

Em outras palavras, existe um [[algoritmo]] para um computador quântico (um [[algoritmo quântico]]) que resolve o problema de decisão com ''alta'' probabilidade e é garantido de executar em tempo polinomial. Em qualquer dada execução do algoritmo, ele tem uma probabilidade de até 1/3 de que vai dar uma resposta errada.

Similarmente a outras classes probabilisticas "de erro limitado", a escolha de 1/3 na definição é arbitrária. Pode-se executar o algoritmo um número constante de vezes e tomar uma maioria para alcançar qualquer probabilidade de corretude menor que 1 desejada, utilizando o [[limitante de chernoff]]. Análises detalhadas mostram que a classe de complexidade é inalterada admitindo um erro tão alto quando <math>{1/2} - {n^{-c}}</math> por um lado, ou exigindo um erro tão pequeno quanto <math>2^{n^{-c}}</math> por outro lado, onde <math>c</math> é qualquer constante positiva, e <math>n</math> é o tamanho da entrada.

==Definição==
'''BQP''' pode também ser vista como uma família uniforme de [[circuitos quânticos]] de erro limitado. Uma linguagem ''L'' está em '''BQP''' se e somente se, existe uma família de tempo polinomial de circuitos quânticos <math>\{Q_n:n \in \mathbb{N}\}</math>, tal que
* Para todo <math>n \in \mathbb{N}</math>, ''<math>Q_n</math>'' toma ''n'' qubits como entrada e dá como saída 1 bit
* Para todo <math>x</math> em ''L'', <math>\mathrm{Pr}(Q_{|x|}(x)=1)\geq \tfrac{2}{3}</math>
* Para todo <math>x</math> que não esta em ''L'', <math>\mathrm{Pr}(Q_{|x|}(x)=0)\geq  \tfrac{2}{3}</math>

== Computação Quântica ==
O número de [[qubit]]s no computador é permitido que seja uma [[função polinomial]] do tamanho da instância. Por exemplo, algoritmos que são conhecidos por fatorar um inteiro de <math>n</math>-bits usando apenas <math>2n</math> qubits ([[Algoritmo de Shor]]).

Normalmente, computação em um computador quântico termina com uma medição. isso leva a um [[colapso de função de onda]] do estado quântico a um dos [[Base Quântica|estados base]]. Pode ser dito que o estado quântico é medido para estar no estado correto com uma probabilidade alta.

Computadores quânticos tem ganho um largo interesse por alguns problemas de interesse prático também sabidos de estar em '''BQP''', mas suspeitos de estarem fora de  '''P'''. Alguns exemplos proeminentes são:
*[[Fatoração de inteiros]] (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]]<ref name="Shor"/>
*Simulação de sistemas quânticos (ver [[Simulador Quântico]])
*Computar o [[Polinômio de Jones]] em certas raízes de unidade

== Relacionamento com outras classes de complexidade ==
Essa classe é definida por um computador quântico e sua classe correspondente natural para um computador normal (ou uma [[Máquina de Turing]] mais uma fonte de aleatoriedade) é {{math|[[Bounded-error probabilistic polynomial|BPP]]}}. Assim como {{math|P}} e {{math|BPP}}, {{math|BQP}} é de [[Complexidade computacional|baixa complexidade]] por si mesmo, que significa {{math|BQP}}<sup>{{math|BQP}}</sup> = {{math|BQP}}. Informalmente, isso é verdadeiro porque algoritmos de tempo polinomial são fechados por composição. Se um algoritmo de tempo polinomial chama como uma subrotina polinomial muitos algoritmos de tempo polinomial, o algoritmo resultante continua executando em tempo polinomial.

{{math|BQP}} contém {{math|[[P (complexity)|P]]}} e {{math|[[Bounded-error probabilistic polynomial|BPP]]}} e esta contido em {{math|[[Almost Wide Probabilistic Polynomial-Time|AWPP]]}},<ref>{{citar periódico|último1 =Fortnow |primeiro1 =Lance |último2 =Rogers |primeiro2 =John |título=Complexity limitations on Quantum computation | url=http://people.cs.uchicago.edu/~fortnow/papers/quantum.pdf |publicado=[[Academic Press]] |local=Boston, MA |ano=1999 |periódico=J. Comput. Syst. Sci. | issn=0022-0000 | volume=59 |número=2 |páginas=240–252 | doi=10.1006/jcss.1999.1651 | postscript=<!--None-->}}</ref> {{math|[[PP (complexity)|PP]]}}<ref>L. Adleman, J. DeMarrais, and M.-D. Huang. Quantum computability. SIAM J. Comput.,
26(5):1524–1540, 1997.</ref> e {{math|[[PSPACE]]}}.<ref name=BernVazi>Bernstein and Vazirani, Quantum complexity theory, [[SIAM Journal on Computing]], 26(5):1411-1473, 1997. [http://www.cs.berkeley.edu/~vazirani/bv.ps]</ref>
De fato, {{math|BQP}} é de [[Complexidade computacional|baixa complexidade]] para {{math|PP}}, significando que uma máquina {{math|PP}} não conseguem se beneficiar por serem capazes de resolver instantaneamente problemas {{math|BQP}}, um indicativo da possível diferença do poder dessas classes similares.
:<ce>P \subseteq BPP \subseteq BQP\subseteq AWPP \subseteq PP \subseteq PSPACE</ce>

Como o problema {{math|P ≟ PSPACE}} ainda não foi resolvido, o problema da diferença entre {{math|BQP}} e as classes mencionadas acima é supostamente difícil.<ref name=BernVazi/> A relação entre {{math|BQP}} e {{math|[[NP]]}} não é conhecida.

Adicionar [[postselection]] à {{math|BQP}} resulta na classe de complexidade {{math|[[PostBQP]]}} que é igual à {{math|[[PP]]}}.<ref name="PostBQP=PP">{{citar periódico|último =Aaronson|primeiro =Scott|ano=2005|título=Quantum computing, postselection, and probabilistic polynomial-time|periódico=Proceedings of the Royal Society A|volume=461|número=2063|páginas=3473–3482|doi=10.1098/rspa.2005.1546}}.  Preprint available at [http://arxiv.org/abs/quant-ph/0412187]</ref><ref>{{citar web|url=http://weblog.fortnow.com/2004/01/complexity-class-of-week-pp-by-guest.html|título=Complexity Class of the Week: PP|último =Aaronson|primeiro =Scott|data=2004-01-11|obra=Computational Complexity Weblog|acessodata=2008-05-02}}</ref>

==Ligações externas==
*[https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#bqp Complexity Zoo link to BQP]

{{Referências}}

{{DEFAULTSORT:Bqp}}
[[Categoria:Complexidade]]
[[Categoria:Ciência_da_computação_teórica]]
[[Categoria:Computação quântica]]