Content deleted Content added
Bender2k14 (talk | contribs) m →Computing knot invariants: Fixed a problem with author links in a reference |
Bender2k14 (talk | contribs) m Combined two identical references into one |
||
Line 15:
==Overview==
Quantum algorithms are usually described, in the commonly-used circuit model of quantum computation, by a [[quantum circuit]] which acts on some input [[qubit]]s and terminates with a [[measurement]]. A quantum circuit consists of simple [[quantum gate]]s which act on at most a fixed number of qubits, usually 2 or 3. Quantum algorithms may also be stated in other models of quantum computation, such as the [[Hamiltonian oracle model]].<ref name=Hamiltonian_NAND_Tree>{{Cite journal
| last = Farhi
| first = E.
Line 158:
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 |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 type of formula 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 for this case was known until one was found for the unconventional Hamiltonian oracle model.<ref
Fast quantum algorithms for more complicated formulas are also known.<ref>{{cite conference |url=http://doi.acm.org/10.1145/1374376.1374394 |title=Span-program-based quantum algorithm for evaluating formulas |first1=Ben W. |last1=Reichardt |first2=Robert |last2=Spalek |year=2008 |conference=STOC '08 |conferenceurl=http://www.informatik.uni-trier.de/~ley/db/conf/stoc/stoc2008.html |booktitle=Proceedings of the 40th annual ACM symposium on Theory of computing |publisher=ACM |___location=Victoria, British Columbia, Canada |pages=103-112 |isbn=978-1-60558-047-0 |doi=10.1145/1374376.1374394}}</ref>
| |||