
2. Competing with Grover’s algorithm

1. Problem 2.1.

[Mike Hamburg] Given a function $f:\{0,1\}^n \to \{0,1,2\}$, find $x\in \{0,1\}^n$ to maximize $f(x)$. Measure average resulting $f(x)$ if, e.g., $f$ has one 1, one 2, and all other values 0. Or consider the function $f:\{0,1\}^n \to \{0,1,2, \dots, 1000\}$. Or consider $f$ which is i.i.d.

Is it possible to do better than Grover search for $x$ such that $f(x) \geq T$ for threshold $T$?
• Problem 2.3.

[Mike Hamburg] Find $x,y$ distinct with $f(x) = f(y) = 1$. Consider the case where there are many solutions at low density. How quickly can this be done? Faster than Grover?

More generally, find distinct $x_1,\dots, x_m$ such that $f(x_1) = \dots = f(x_m) = 1$. Can you do better than $m$ preimage searches?

Cite this as: AimPL: Quantum algorithms for analysis of public-key crypto, available at http://aimpl.org/quantumalg.