2.1k citations · 8.3k across the 34 of their papers we have counts for
Showing 1997Show all
2 papers · 1 filter
quant-ph1997★ 12 cited
Quantum Mechanical Square Root Speedup in a Structured Search Problem
Edward Farhi, Sam Gutmann
An unstructured search for one item out of N can be performed quantum mechanically in time of order square root of N whereas classically this requires of order N steps. This raises…
quant-ph1997★ 1.2k cited
Quantum Computation and Decision Trees
Edward Farhi, Sam Gutmann
Many interesting computational problems can be reformulated in terms of decision trees. A natural classical algorithm is to then run a random walk on the tree, starting at the root…