Quantum algorithm for multivariate polynomial interpolation

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

m a t h b b F_{q}

,

m a t h b b R

, and

m a t h b b C

. We show that

k_{m a t h b b C}

and

2 k_{m a t h b b C}

queries suffice to achieve probability

1

for

m a t h b b C

and

m a t h b b R

, respectively, where

k_{m a t h b b C} = s m a s h l c e i l f r a c 1 n + 1 n + d c h o o s e d c e i l

except for

d = 2

and four other special cases. For

m a t h b b F_{q}

, we show that

s m a s h l c e i l f r a c d n + d n + d c h o o s e d c e i l

queries suffice to achieve probability approaching

1

for large field order

q

. The classical query complexity of this problem is

s m a s h n + d c h o o s e d

, so our result provides a speedup by a factor of

n + 1

,

f r a c n + 1 2

, and

f r a c n + d d

for

m a t h b b C

,

m a t h b b R

, and

m a t h b b F_{q}

, 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

m a t h b b F_{q}

, we conjecture that

2 k_{m a t h b b C}

queries also suffice to achieve probability approaching

1

for large field order

q

, although we leave this as an open problem.

Recommendations

Cites Work

Cited In (5)

This page was built for publication: Quantum algorithm for multivariate polynomial interpolation