The table maker's quantum search

Abstract

We show that quantum search can be used to compute the hardness to round an elementary function, that is, to determine the minimum working precision required to compute the values of an elementary function correctly rounded to a target precision of $n$ digits for all possible precision-$n$ floating-point inputs in a given interval. For elementary functions $f$ related to the exponential function, quantum search takes time $\tilde{O}(2^{n/2}\log (1/\hat{I}´))$ to return, with probability $1-\hat{I}´$, the hardness to round $f$ over all $n$-bit floating-point inputs in a given binade. For periodic elementary functions in large binades, standalone quantum search yields an asymptotic speedup over the best known classical algorithms and heuristics. We then estimate the resources required for a fault-tolerant implementation of the proposed algorithm for the $\sin$ and $\cos$ functions in double precision. We find that, although the algorithm can in principle compete with the fastest known practical method for computing the hardness to round over all binades in the format, it requires qubit coherence times that are unrealistically long for present technology.

13 pages, 0 figures, accepted paper @ 33rd IEEE International Symposium on Computer Arithmetic 2026 (ARITH 2026)