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

## 6. Miscellaneous

1. #### 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$.
• #### 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).
• #### 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.
• #### 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.