Optimal quantum algorithm for polynomial interpolation

Andrew M. Childs; Shih Han Hung; Wim Van Dam; Igor E. Shparlinski

doi:10.4230/LIPIcs.ICALP.2016.16

Optimal quantum algorithm for polynomial interpolation

Andrew M. Childs, Shih Han Hung, Wim Van Dam, Igor E. Shparlinski

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

5 Citations (Scopus)

90 Downloads (Pure)

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.

Original language	English
Title of host publication	43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Editors	Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, Davide Sangiorgi
Publisher	Dagstuhl Publishing
Pages	1-13
Number of pages	13
ISBN (Electronic)	9783959770132
DOIs	https://doi.org/10.4230/LIPIcs.ICALP.2016.16
Publication status	Published - 1 Aug 2016
Externally published	Yes
Event	43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016 - Rome, Italy Duration: 12 Jul 2016 → 15 Jul 2016

Other

Other	43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016
Country/Territory	Italy
City	Rome
Period	12/07/16 → 15/07/16

Bibliographical note

Version archived for private and non-commercial use with the permission of the author/s and according to publisher conditions. For further rights please contact the publisher.

Keywords

Finite fields
Polynomial interpolation
Quantum algorithms
Query complexity

Access to Document

10.4230/LIPIcs.ICALP.2016.16

Publisher version (open access)Final published version, 494 KBLicence: CC BY

Cite this

Childs, A. M., Hung, S. H., Van Dam, W., & Shparlinski, I. E. (2016). Optimal quantum algorithm for polynomial interpolation. In I. Chatzigiannakis, M. Mitzenmacher, Y. Rabani, & D. Sangiorgi (Eds.), 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) (pp. 1-13). Article 16 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ICALP.2016.16

@inproceedings{f032f75b48d24ad88e96de6d2123c165,

title = "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 Fq. 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.",

keywords = "Finite fields, Polynomial interpolation, Quantum algorithms, Query complexity",

author = "Childs, {Andrew M.} and Hung, {Shih Han} and {Van Dam}, Wim and Shparlinski, {Igor E.}",

note = "Version archived for private and non-commercial use with the permission of the author/s and according to publisher conditions. For further rights please contact the publisher.; 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016 ; Conference date: 12-07-2016 Through 15-07-2016",

year = "2016",

month = aug,

day = "1",

doi = "10.4230/LIPIcs.ICALP.2016.16",

language = "English",

pages = "1--13",

editor = "Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi",

booktitle = "43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)",

publisher = "Dagstuhl Publishing",

address = "Germany",

}

Childs, AM, Hung, SH, Van Dam, W & Shparlinski, IE 2016, Optimal quantum algorithm for polynomial interpolation. in I Chatzigiannakis, M Mitzenmacher, Y Rabani & D Sangiorgi (eds), 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)., 16, Dagstuhl Publishing, pp. 1-13, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Rome, Italy, 12/07/16. https://doi.org/10.4230/LIPIcs.ICALP.2016.16

Optimal quantum algorithm for polynomial interpolation. / Childs, Andrew M.; Hung, Shih Han; Van Dam, Wim et al.
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). ed. / Ioannis Chatzigiannakis; Michael Mitzenmacher; Yuval Rabani; Davide Sangiorgi. Dagstuhl Publishing, 2016. p. 1-13 16.

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - Optimal quantum algorithm for polynomial interpolation

AU - Childs, Andrew M.

AU - Hung, Shih Han

AU - Van Dam, Wim

AU - Shparlinski, Igor E.

N1 - Version archived for private and non-commercial use with the permission of the author/s and according to publisher conditions. For further rights please contact the publisher.

PY - 2016/8/1

Y1 - 2016/8/1

N2 - We consider the number of quantum queries required to determine the coefficients of a degree-d polynomial over Fq. 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.

AB - We consider the number of quantum queries required to determine the coefficients of a degree-d polynomial over Fq. 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.

KW - Finite fields

KW - Polynomial interpolation

KW - Quantum algorithms

KW - Query complexity

UR - http://www.scopus.com/inward/record.url?scp=85012877222&partnerID=8YFLogxK

UR - http://purl.org/au-research/grants/arc/DP140100118

U2 - 10.4230/LIPIcs.ICALP.2016.16

DO - 10.4230/LIPIcs.ICALP.2016.16

M3 - Conference proceeding contribution

AN - SCOPUS:85012877222

SP - 1

EP - 13

BT - 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

A2 - Chatzigiannakis, Ioannis

A2 - Mitzenmacher, Michael

A2 - Rabani, Yuval

A2 - Sangiorgi, Davide

PB - Dagstuhl Publishing

T2 - 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016

Y2 - 12 July 2016 through 15 July 2016

ER -

Optimal quantum algorithm for polynomial interpolation

Abstract

Other

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

New Applications of Additive Combinatorics in Number Theory and Graph Theory

Cite this

Optimal quantum algorithm for polynomial interpolation

Abstract

Other

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Projects

New Applications of Additive Combinatorics in Number Theory and Graph Theory

Cite this