Editing Quantum algorithm (section)

===Formula evaluation===
A formula is a tree with a gate at each internal node and an input bit at each leaf node. The problem is to evaluate the formula, which is the output of the root node, given oracle access to the input.

A well studied formula is the balanced binary tree with only NAND gates.<ref>
{{cite web
 |last=Aaronson |first=S.
 |date=3 February 2007
 |title=NAND now for something completely different
 |url=http://scottaaronson.com/blog/?p=207
 |work=Shtetl-Optimized
 |access-date=2009-12-17
}}</ref> This type of formula requires <math>\Theta(N^c)</math> queries using randomness,<ref>
{{cite conference
 |last1=Saks |first1=M.E.
 |last2=Wigderson |first2=A.
 |year=1986
 |title=Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees
 |url=http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/SW86/SW86.pdf
 |book-title=Proceedings of the 27th Annual Symposium on Foundations of Computer Science
 |pages=29–38
 |publisher=[[IEEE]]
 |doi=10.1109/SFCS.1986.44
 |isbn=0-8186-0740-8
}}</ref> where <math>c = \log_2(1+\sqrt{33})/4 \approx 0.754</math>. With a quantum algorithm, however, it can be solved in <math>\Theta(N^{1/2})</math> queries. No better quantum algorithm for this case was known until one was found for the unconventional Hamiltonian oracle model.<ref name=Hamiltonian_NAND_Tree/> The same result for the standard setting soon followed.<ref>
{{cite arXiv
 |last=Ambainis |first=A.
 |year=2007
 |title=A nearly optimal discrete query quantum algorithm for evaluating NAND formulas
 |class=quant-ph
 |eprint=0704.3628
}}</ref>

Fast quantum algorithms for more complicated formulas are also known.<ref>
{{cite conference
 |last1=Reichardt |first1=B. W.
 |last2=Spalek |first2=R.
 |year=2008
 |title=Span-program-based quantum algorithm for evaluating formulas
 |book-title=Proceedings of the 40th Annual ACM symposium on Theory of Computing
 |publisher=[[Association for Computing Machinery]]
 |pages=103–112
 |isbn=978-1-60558-047-0
 |doi=10.1145/1374376.1374394
|arxiv=0710.2630}}</ref>