| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

2. Competing with Grover’s algorithm


    1. Add remark

      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$?


        • Add remark

          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.