Modelo de árvore de decisão: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Linha 40:
===Árvore de decisão quântica===
A complexidade de uma árvore de decisão quântica '''<math>Q_2(f)</math>''' é a profundidade da árvore quântica de menor profundidade que dá o resultado <math>f(x)</math> com a probabilidade de pelo menos <math>2/3</math> para todo <math>x\in \{0,1\}^n </math>. Outra quantidade, '''<math>Q_E(f)</math>''', é definida como a profundidade da árvore de menor profundidade que dá o resultado <math>f(x)</math> com probabilidade 1 em todos os casos (ou seja, computa <math>f</math> exatamente. <math>Q_2(f)</math> e <math>Q_E(f)</math> são comumente conhecidas como '''complexidades de pedidos quânticos''', porque a definição direta de uma árvore de decisão quântica é mais complicada do que o caso clássico. Da mesma forma que o caso randomizado, definimos <math>Q_0(f)</math> e <math>Q_1(f)</math>.
==Relação entre diferentes modelos==
Segue imediatamente as definições de que todas as funções <math>f</math> Booleanas de <math>n</math>-bits,
<math>Q_2(f) \leq R_2(f) \leq R_1(f) \leq R_0(f) \leq D(f) \leq n</math>, e<math>Q_2(f) \leq Q_E(f) \leq D(f) \leq n</math>.
Blum and Impagliazzo,<ref name="BlumImpagliazzo 1995">{{cite conference | last = Blum | first=M. | coauthors=Impagliazzo, R. | title=Generic oracles and oracle classes | year=1987 | booktitle=Proceedings of 18th IEEE FOCS | pages=118–126}}</ref> Hartmanis and Hemachandra,<ref name="HartmanisHemachandra">{{Citation | last1=Hartmanis | first1=J. | last2 = Hemachandra | first2=L. | year = 1987 | contribution=One-way functions, robustness, and non-isomorphism of NP-complete sets | title=Technical Report DCS TR86-796, Cornell University}}</ref> e Tardos<ref name="Tardos">{{cite journal | last=Tardos | first=G. | title=Query complexity, or why is it difficult to separate ''NP''<sup>''A''</sup> ∩ ''coNP''<sup>''A''</sup> from ''P''<sup>''A''</sup> by random oracles ''A''? | journal=Combinatorica | year=1989 | pages=385–392|volume=9 | doi=10.1007/BF02125350}}</ref> descobriram que <math>D(f) \leq R_0(f)^2</math>. Noam Nisan descobriu que a árvore randomizada de Monte Carlo também é polinomialmente relacionada à complexidade da árvore de decisão determinística: <math>D(f) = O(R_2(f)^3)</math>.<ref name="Nisan">{{cite conference | last=Nisan | first=N. | authorlink = Noam Nisan | title=CREW PRAMs and decision trees | year=1989 | booktitle=Proceedings of 21st ACM STOC | pages=327–335}}</ref> (Nisan também mostrou que <math>D(f) = O(R_1(f)^2)</math>.) Um corolário deste resultado é que <math>R_0(f) = O(R_2(f)^3)</math>. Essa inequalidade pode ser flexível, porém; não há nenhum exemplo conhecido de uma separação super-linear entre <math>R_0(f)</math> e<math>R_2(f)</math>.<ref name="Santha 1995">{{Citation | last = Santha | first=Miklos | title=On the Monte Carlo Boolean Decision Tree Complexity of Read-Once Formulae | year=1995 |url=http://www.lri.fr/~santha/Papers/s95.ps.gz}} (ps format)</ref>
A complexidade da árvore de decisão <math>Q_2(f)</math> também é polinomialmente relacionada à <math>D(f)</math>. Midrijanis mostrou que <math>D(f) = O(Q_E(f)^3)</math>,<ref name="Midrijanis">{{Citation | last=Midrijanis | first=Gatis | year = 2004 | contribution= Exact quantum query complexity for total Boolean functions | title = arXiv:quant-ph/0403168 | arxiv=quant-ph/0403168}}</ref><ref name="Midrijanis2">{{Citation | last=Midrijanis | first=Gatis | year = 2005 | contribution= On randomized and quantum query complexities | title = arXiv:quant-ph/0501142 | arxiv=quant-ph/0501142}}</ref> improving a quartic bound due to Beals et al.<ref name="Beals">{{cite journal | last=Beals | first=R. | coauthors=Buhrman, H.; Cleve, R.; Mosca, M.; de Wolf, R. | year = 2001 | title= Exact quantum query complexity for total Boolean functions | journal =Journal of ACM | volume=47 | pages=778–797}}</ref> Beals et al. também mostrou que <math>D(f) = O(Q_2(f)^6)</math>, e isto ainda é o melhor limite conhecido. Porém, a maior lacuna entre pedidos determinísticos e quânticos é apenas quadrático. Uma lacuna quadrática é atingida para o [[Algoritmo de Grover]]; <math>D(OR_n) = n</math> enquanto <math>Q_2(OR_n) = \Theta(\sqrt{n})</math>.
É importante perceber que estas relacões polinomiais são válidas apenas para funções Booleanas ''totais''. Para For [[Função parcial|funções booleanas parciais]], que contêm um subconjunto de <math>\{0,1\}^n</math>, uma separação exponencial entre <math>Q_E(f)</math> e <math>D(f)</math> é possível; o primeiro exemplo de tal problema foi descoberto por [[Deutsch and Jozsa]]. O mesmo exemplo também dá uma separação exponencial entre <math>R_2(f)</math> e <math>D(f)</math>.
Essas relações podem ser sumarizadas pelas seguintes inequalidades, das quais são verdadeiras até fatores constantes:<ref name="Midrijanis2" />
*<math>D(f) \leq R_0(f)^2</math><ref name="BlumImpagliazzo 1995" /><ref name="HartmanisHemachandra" /><ref name="Tardos" />
*<math>D(f)\leq R_1(f)R_2(f)</math><ref name="Nisan" />
*<math>D(f) \leq R_2(f)^3</math><ref name="Nisan" />
*<math>R_0(f) \leq R_2(f)^2 \log N</math><ref name="Midrijanis2" />
*<math>D(f) \leq Q_2(f)^6</math><ref name="Beals" />
*<math>D(f) \leq Q_E(f)^2Q_2(f)^2</math><ref name="Beals" />
*<math>D(f) \leq Q_1(f)^2Q_2(f)^2</math><ref>H. Buhrman, R. Cleve, R. de Wolf, and Ch. Zalka. Bounds for Small-Error and Zero-Error Quantum Algorithms. In 40th IEEE Symposium on Foundations of Computer Science (FOCS'99), pp.358-368. cs.CC/9904019, 1999.</ref>
*<math>R_0(f) \leq Q_1(f)Q_2(f)^2 \log N</math><ref>S. Aaronson. Quantum Certificate Complexity. IEEE Conference on Computational Complexity, pp. 171-178, 2003.</ref>
*<math>D(f) \leq Q_1(f)Q_2(f)^2</math><ref name="Midrijanis2" />
{{ref-section}}
| |||