Title | Optimal quantum algorithm for polynomial interpolation |

Publication Type | Journal Article |

Year of Publication | 2016 |

Authors | Childs, AM, van Dam, W, Hung, S-H, Shparlinski, IE |

Journal | 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) |

Volume | 55 |

Pages | 16:1--16:13 |

Date Published | 2016/03/01 |

ISSN | 1868-8969 |

ISBN Number | 978-3-95977-013-2 |

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'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. |

URL | http://arxiv.org/abs/1509.09271 |

DOI | 10.4230/LIPIcs.ICALP.2016.16 |