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

6. Miscellaneous


    1. Add remark

      Problem 6.1.

      [John Schanck] Parameters: $n \geq 2$ and $\alpha > 0$. Given independent uniformly random $x_1, x_2, \dots\in S^{n-1} = \{v \in \mathbb R^n : \|v\|_2 = 1\}$, how quickly can we find a subsequence that covers $S^{n-1}$? (Here, “covers" means that every point of $S^{n-1}$ is within angle $\alpha$ of a point in the subsequence.) For example, consider the case when $n = 1000$ and $\alpha = 75^\circ$.


        • Add remark

          Problem 6.2.

          [Michele Mosca] Does HHL break crypto? (See recent paper.)

          Understand condition number over $\mathbb C$ of matrix of coefficients of $f_1, f_2, \dots$ (original equations), $xf_1, xyf_2, \dots$ (only monomial terms).


            • Add remark

              Problem 6.3.

              [Greg Kuperberg] Is there a crypto problem that is solved by Simon’s algorithm without superposition attackers? Which hidden subgroup problems have crypto applications? Or non-crypto instances?
                1. Remark. “Instance": e.g. algorithm for $x\mapsto 2^x\bmod n$ in Shor’s algorithm.


                    • Add remark

                      Problem 6.4.

                      [Dan Bernstein] Compute short units in the ring of integers of $\mathbb Q[x]/(x^{312} - x^{156} -1)$. How short can they be, and how fast can you find them?

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