Optimal quantum algorithm for polynomial interpolation
This work provides an optimal quantum algorithm for polynomial interpolation, impacting quantum cryptography by enhancing attack efficiency, though it is incremental as it builds on known lower bounds.
The paper tackles the problem of determining the coefficients of a degree-d polynomial over GF(q) with quantum queries, achieving a lower bound of d/2+1/2 queries for bounded error, which improves upon previous results and has implications for quantum attacks on cryptographic protocols.
We consider the number of quantum queries required to determine the coefficients of a degree-d polynomial over GF(q). A lower bound shown independently by Kane and Kutin and by Meyer and Pommersheim shows that d/2+1/2 quantum queries are needed to solve this problem with bounded error, whereas an algorithm of Boneh and Zhandry shows that d quantum queries are sufficient. We show that the lower bound is achievable: d/2+1/2 quantum queries suffice to determine the polynomial with bounded error. Furthermore, we show that d/2+1 queries suffice to achieve probability approaching 1 for large q. These upper bounds improve results of Boneh and Zhandry on the insecurity of cryptographic protocols against quantum attacks. We also show that our algorithm's success probability as a function of the number of queries is precisely optimal. Furthermore, the algorithm can be implemented with gate complexity poly(log q) with negligible decrease in the success probability. We end with a conjecture about the quantum query complexity of multivariate polynomial interpolation.