6. Miscellaneous

Problem 6.1.
[John Schanck] Parameters: $n \geq 2$ and $\alpha > 0$. Given independent uniformly random $x_1, x_2, \dots\in S^{n1} = \{v \in \mathbb R^n : \v\_2 = 1\}$, how quickly can we find a subsequence that covers $S^{n1}$? (Here, “covers" means that every point of $S^{n1}$ 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 noncrypto instances?
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 publickey crypto, available at http://aimpl.org/quantumalg.