Content deleted Content added
Bender2k14 (talk | contribs) m →Evaluating NAND trees: This form for c is better both visually and for understanding |
Bender2k14 (talk | contribs) →Evaluating NAND trees: Added the reference which solve the problem for the stand query model |
||
Line 157:
===Evaluating NAND trees===
The problem is to compute the value of a formula given by a balanced binary tree with bits at the leaves, and NAND gates at the inner vertices.<ref>{{cite web |url=http://scottaaronson.com/blog/?p=207 |title=NAND now for something completely different |author=[[Scott Aaronson]] |date=2007-02-03 |work=Shtetl-Optimized |accessdate=2009-12-17}}</ref> This problem requires Θ(''N''<sup>c</sup>) queries using randomness<ref>{{cite conference |url=http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/SW86/SW86.pdf |title=Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees |first1=Michael E. |last1=Saks |first2=Avi |last2=Wigderson |year=1986 |conference=FOCS |publisher=IEEE |___location=Toronto, Ontario, Canada |pages=29-38}}</ref> (where <math>c = \log_2[(1+\sqrt{33})/4] \approx 0.754</math>), but can be solved in Θ(''N''<sup>0.5</sup>) queries by a quantum algorithm. No better quantum algorithm was known until one was found for the unconventional Hamiltonian oracle model.<ref>E. Farhi, [[Jeffrey Goldstone|J. Goldstone]], and S. Gutmann, A quantum algorithm for the Hamiltonian NAND tree, Theory of Computing 4 (2008), no. 1, 169–190, quant-ph/0702144</ref> The same result for the standard setting soon followed.<ref>{{Citation |last=Ambainis |first=Andris |title=A nearly optimal discrete query quantum algorithm for evaluating NAND formulas |year=2007 |url=http://arxiv.org/abs/0704.3628}}</ref>
===Group Commutativity===
| |||