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

3. Concrete Costs


    1. Add remark

      Problem 3.1.

      [Greg Kuperberg] Given: $x_0,\dots, x_{2^n-1} \in \{0,1\}$. What is the real-world cost of $$ | i_1, \dots, i_{n-1}, a \rangle \mapsto | i_1, \dots, i_{n-1}, a\oplus x_i \rangle $$ where $i = i_0 + 2i_1 + \dots + 2^{n-1}i_{n-1}$.

      Can error correction be done efficiently for this problem?


        • Add remark

          Problem 3.5.

          [Shi Bai] What are the concrete costs of quantum sieving and quantum enumeration within BKZ? Go beyond asymptotics.

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