



01532nas a2200193   4500008004100000020002200041022001400063245005900077210005900136260001500195300001600210490000700226520098400233100002301217700001701240700001901257700002601276856003601302       2016                        eng d  a978-3-95977-013-2  a1868-896900aOptimal quantum algorithm for polynomial interpolation0 aOptimal quantum algorithm for polynomial interpolation  c2016/03/01  a16:1--16:130 v553 a<p>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&#39;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.</p>1 aChilds, Andrew, M.1 avan Dam, Wim1 aHung, Shih-Han1 aShparlinski, Igor, E.  uhttp://arxiv.org/abs/1509.09271