Revision as of 20:13, 8 December 2010 edit Bender2k14 (talk \| contribs) Extended confirmed users 1,999 edits m →Triangle-finding problem: Improved a referenced by using a template ← Previous edit		Revision as of 21:05, 8 December 2010 edit undo Bender2k14 (talk \| contribs) Extended confirmed users 1,999 edits →Evaluating NAND trees: The exponent was incorrect rounded. Fixed this and added more details about where it comes from. Next edit →
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>~~0.753~~c</sup>) queries ~~classically~~using randomness (where <math>c = \log_2(1+\sqrt{33})-2 \approx 0.754</math>), but can be solved in Θ(''N''<sup>0.5</sup>) queries by a quantum algorithm.<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> ==BQP-complete problems==

Quantum algorithm: Difference between revisions