Grover’s tiny claw algorithm

[This post is based on a talk by Jean-François Biasse at the SIAM Conference on Applied Algebraic Geometry at 12/7/2019]

The complexity of algorithms is typically expressed in an asymptotic way, ignoring all constant factors and sometimes even logarithmic factors. In practice however, these constants can play a large role in the efficiency and very often memory-time trade-offs can be made as well. This is even more so prevalent in the case of quantum algorithms, where parts of the computations can be made on classical computers as well.

The problem of finding a $2^n$-isogeny between two supersingular elliptic curves boils down to finding a route in a 3-regular graph with roughly $\sqrt{p/12}$ vertices for some very large prime $p$. The graph is an expander graph, and there are no known methods of efficiently manoeuvring in this graph, so we need to resort to generic (quantum) algorithms to attack any protocols relying on this hard problem. One of these is Tani’s claw finding algorithm, which extends a claw from both the starting point and ending point, until a connection is made somewhere in the middle. Another one is Grover’s algorithm which searches through all possible paths in superposition. The former has cost $O(p^{1/6})$ for circuit depth, whereas the latter has cost $O(p^{1/4})$. In a recent paper by Jacques and Shank though, it was shown that when we account for memory usage (so using depth x width metric), Grover is competitive with Tani despite a worse gate complexity.

Biasse and Pring found a way to adapt Grover’s search algorithm slightly to offload some of the work to a classical computer, improving on the constants of $O(p^{1/4})$. In particular, if $C_n$ is the cost of evaluating a degree $2^n$-isogeny, then Grover’s algorithm has complexity $O(p^{1/4}{C}_n)$, whereas their new technique brings this down to $O(p^{1/4}{C}_n^{1/2}(\log p{)}^{1/2})$. The basic idea is that they perform a classical computation of all $2^k$-isogenies around the endpoint (so a small claw), and then only need to search through a superposition of all $2^{n-k}$-isogenies originating from the starting point.

Grover’s algorithm from a very high level works with a quantum circuit $U_f$ (which can be represented by a unitary matrix) that results in a 0 for almost all inputs, and a 1 for a specific input (that we are looking for), while simultaneously flipping the sign of this particular input. Using an ancillary qubit $|y⟩$, this can be easily written down as $U_f|x⟩|y⟩=|x⟩|y\oplus f(x)⟩$. This quantum circuit $U_f$ needs to be repeated $O(\sqrt{N})$ before we can perform a measurement, where $N$ is the size of the domain we are looking over (in our case $\sqrt{p/12}$). The trick they made to change Grover’s search was basically incorporating all the $j$-invariants of the $2^k$-isogenous curves from the ending point to the oracle $U_f$, instead of just that one. In qubit notation this implies $$U_f|x_1,\dots ,x_{n-k}⟩|0^k⟩|y⟩=|x_1,\dots ,x_{n-k}⟩|0^k⟩|y{\oplus }_{z_1,\dots ,z_k}f(x_1,\dots ,x_{n-k},z_1,\dots ,z_k⟩.$$

Offloading a part of the computations to a classical computer with this method does not seem to improve asymptotic bounds, but improves the hidden constants with regards to circuit depth. So the conjectured hard isogeny problems are still surviving quantum computers for now.