1. Optimal Quantum Algorithm for Polynomial Interpolation
- Author
-
Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, Shparlinski, I, Childs, AM, van Dam, W, Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, Shparlinski, I, Childs, AM, and van Dam, W
- Abstract
We consider the number of quantum queries required to determine the coefficients of a degree-d polynomial over F_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.
- Published
- 2016