Advances in Quantum Algorithms & Devices: Quantum Monte Carlo versus Quantum Adiabatic Optimization

Опубликовано 22 июня 2016, 0:25

How many queries are needed to determine a polynomial F(X)? We look at this question when F(X) is defined over a finite field GF(q) and has degree d, such that d+1 queries are obviously sufficient. Shamir's Secret Sharing protocol is based on the result that d+1 classical queries are also needed as no interpolation is possible based on only d values of F. Here we look at how many quantum queries are sufficient to perform the same task. Earlier work by [Kane & Kutin 2009] and [Meyer & Pommersheim 2010] proved that at least d/2+1/2 quantum queries are needed, while [Boneh and Zhandry 2012] showed that d quantum queries are sufficient. In this talk we will describe a quantum algorithm that uses only d/2+1/2 queries and that has a constant success probability. Our algorithm relies on the analysis of the classical Moment Problem defined over finite fields. (Joint work with Andrew Childs)