Computing

314 ◾ Computing

nding a needle in a haystack, and inverting a function. e notion is that

an unordered list of values is searched for a particular value. Utilizing

classic computation, on average, O(n) time is needed to nd a particu-

lar value. Utilizing Grover’s quantum algorithm, O(

n

) time is needed,

where n is the database size. is provides a quadratic speed-up and can

be substantial when n is large.

From the inverting a function point of view, the function f: {0, 1}

n

→ {0,1}

is evaluated in search of the unknown value, which is n bits wide, such

that value = x if f(x) is 1, x varying over the domain and only one result

of f will pro ...