2026-07-20T11:57:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6298 2024-03-06T10:37:39Z ddc:004 open_access

Optimal Quantum Algorithm for Polynomial Interpolation Childs, Andrew M. van Dam, Wim Hung, Shih-Han Shparlinski, Igor E. Quantum algorithms query complexity polynomial interpolation finite fields 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andrew M. Childs and Wim van Dam and Shih-Han Hung and Igor E. Shparlinski 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.16 urn:nbn:de:0030-drops-62985 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.16 eng https://creativecommons.org/licenses/by/3.0/legalcode