Skip to main content

Optimal quantum algorithm for polynomial interpolation

Abstract

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.

Publication Details

Authors
Publication Type
Journal Article
Year of Publication
2016
Journal
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Volume
55
Date Published
03/2016
Pagination
16:1–16:13
ISSN
1868-8969