Title | Quantum algorithm for multivariate polynomial interpolation |

Publication Type | Journal Article |

Year of Publication | 2018 |

Authors | Chen, J, Childs, AM, Hung, S-H |

Journal | Proceedings of The Royal Society A |

Volume | 474 |

Issue | 2209 |

Date Published | 2018/01/17 |

Abstract | How many quantum queries are required to determine the coefficients of a degree-d polynomial in n variables? We present and analyze quantum algorithms for this multivariate polynomial interpolation problem over the fields Fq, R, and C. We show that kC and 2kC queries suffice to achieve probability 1 for C and R, respectively, where kC = ⌈ 1 n+1 ( n+d d )⌉ except for d = 2 and four other special cases. For Fq, we show that ⌈ d n+d ( n+d d )⌉ queries suffice to achieve probability approaching 1 for large field order q. The classical query complexity of this problem is ( n+d d ), so our result provides a speedup by a factor of n + 1, n+1 2 , and n+d d for C, R, and Fq, respectively. Thus we find a much larger gap between classical and quantum algorithms than the univariate case, where the speedup is by a factor of 2. For the case of Fq, we conjecture that 2kC queries also suffice to achieve probability approaching 1 for large field order q, although we leave this as an open problem. |

URL | http://rspa.royalsocietypublishing.org/content/474/2209/20170480 |

DOI | 10.1098/rspa.2017.0480 |