Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1701.03990 · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences

Quantum algorithm for multivariate polynomial interpolation

Jianxin Chen, Andrew M. Childs, Shih-Han Hung

Published Jan 1, 2018• 8 citations
arXivHTMLPDF

Abstract

How many quantum queries are required to determine the coefficients of a degree- d polynomial in n variables? We present and analyse quantum algorithms for this multivariate polynomial interpolation problem over the fields F q , R and C . We show that k C and 2 k C queries suffice to achieve probability 1 for C and R , respectively, where k C = ⌈ ( 1 / ( n + 1 ) ) ( n + d d ) ⌉ except for d =2 and four other special cases. For F q , 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 speed-up by a factor of n +1, ( n +1)/2 and ( n + d )/ d for C , R and F q

DOI
10.1098/rspa.2017.0480

Related papers

Optimal Quantum Algorithm for Polynomial Interpolation

Andrew M. Childs, Wim van Dam, Shih-Han Hung +1 more

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. We end with a conjecture about the quantum query complexity of multivariate polynomial interpolation.

arXiv:1509.09271•Leibniz international proceedings in informatics•Sep 30, 2015•5 citations

Quantum Algorithms for Multivariable Polynomial Transformations: From Efficient Synthesis to Quantum Channel Transformations

Zheyu Shen, Yusen Wu, Xiao Yuan +2 more

Polynomial transformations are basic primitives in quantum algorithms: quantum signal processing and singular value transformation compile univariate polynomials into circuits with query complexity essentially set by degree. Multivariable transformations of noncommuting matrices, however, lack a comparable synthesis theory. We develop a complete constructive theory under joint block access for all polynomials contractive on the prescribed matrix domain. Given a compact finite-state description of a degree-$D$ polynomial $P$ and $0<τ<1$, we synthesize $P$ with $(1+τ)$-optimal normalization using $O(D/\sqrtτ)$ queries, and exactly $D$ under row-block access, matching a degree lower bound. The complete circuit realization is classically computable in polynomial time with polylogarithmic dependence on accuracy. The key to our construction is a finite algorithmic Schur--Agler theorem: the coefficient recurrence defines a polynomial-dimensional continuation space supporting a complete semidefinite certificate for contractivity on the prescribed domain. Factoring this certificate yields the contractive realization underlying the query algorithm. Beyond matrix transformations, our framework lifts multivariable polynomial synthesis to quantum channel transformations. Given coherent Kraus access $K=\{K_a\}_a$, we synthesize any finite jointly contractive family of noncommutative polynomial maps $K\mapsto\{F_b(K)\}_b$ as completely positive operations, allowing coherent interference among Kraus histories. Furthermore, channel-level transformations specified by causal Choi data can be synthesized explicitly as fixed-order quantum combs. Collectively, these results point to a broader program: multivariable approximation as a language for multi-operator quantum algorithms and higher-order quantum information processing.

quant-pharXiv:2610.08714•Oct 7, 2026•0 citations

Optimal Quantum Algorithm for Vector Interpolation

Sophie M. Decoppet

In this paper we study the functions that can be learned through the polynomial interpolation quantum algorithm designed by Childs et al. This algorithm was initially intended to find the coefficients of a multivariate polynomial function defined on finite fields $\mathbb{F}_q$. We extend its scope to vector inner product functions of the form $\mathcal{O}_{\mathbf{s}}(\mathbf{v}) = \mathbf{s}\cdot\mathbf{v}$ where the goal is to find the vector $\mathbf{s} \in \mathbb{F}_q^n$. We examine the necessary conditions on the domain $\mathcal{V}$ of $\mathcal{O}_{\mathbf{s}}$ and prove that the algorithm is optimal for such functions. Furthermore, we show that the success probability approaches 1 for large $q$ and large domain order $|\mathcal{V}|.$ Finally, we provide a conservative formula for the number of queries required to achieve this success probability.

arXiv:2212.03939•Dec 7, 2022•0 citations

Multivariate quantum signal processing with optimal query complexity

Mingrui Jing, Xin Wang, Zhan Yu +1 more

Polynomial transformations of data encoded in quantum operations are a building block of quantum algorithms, and their query complexity measures how often those operations are used. For multiple variables, existing methods either realize restricted polynomial families or implement monomials separately at a query cost exponential in the number of variables. We present a quantum circuit that implements every multivariate trigonometric polynomial up to an explicit normalization. The circuit processes one variable coherently over the frequency components of the remaining variables, allowing all components to share the same signal queries. Each variable is queried exactly as many times as its degree in the polynomial, and we prove that this query complexity is optimal. We further extend the construction to commuting unitaries. The resulting circuit applies the multivariate polynomial simultaneously across their shared eigenbasis, using the minimum numbers of forward and inverse queries to each unitary. We also study trainable rotations with fixed preparation and a local readout of the last input. At query depth at least two, independent uniform initialization gives every active readout gradient a variance lower bound set by its squared branch weight and the inverse square root of the depth, uniformly over data states and dimensions. For supervised squared loss, retaining sample correlations gives an initialization gradient-variance bound in terms of targets and input spectra. This also bounds the expected loss decrease after the first exact gradient step with a specified step size. These results provide a scalable and practical solution for developing multivariate quantum algorithms and quantum learning models.

quant-pharXiv:2610.03393•Oct 5, 2026•0 citations

The quantum query complexity of learning multilinear polynomials

Ashley Montanaro

In this note we study the number of quantum queries required to identify an unknown multilinear polynomial of degree d in n variables over a finite field F_q. Any bounded-error classical algorithm for this task requires Omega(n^d) queries to the polynomial. We give an exact quantum algorithm that uses O(n^(d-1)) queries for constant d, which is optimal. In the case q=2, this gives a quantum algorithm that uses O(n^(d-1)) queries to identify a codeword picked from the binary Reed-Muller code of order d.

arXiv:1105.3310•May 17, 2011•0 citations

Quantum estimates for classical polynomial optimization

Oleg Evnin

The problem of finding lower and upper bounds on multivariate homogeneous polynomials is both difficult and important given its applications to questions ranging from dynamical stability in complex potential landscapes to data analysis. From the standpoint of tensor eigenvalue theory, the question is equivalent to finding the smallest and the largest eigenvalues of the coefficient tensor corresponding to the given polynomial. Standard approaches outlined in the literature amount to running nonlinear iterations in search for the optimal rays along which the growth of the polynomial is fastest or slowest. Unlike the case of matrices (or their corresponding multivariate quadratic forms) convergence of such algorithms for higher-rank tensors is capricious due to the complex topography of polynomial objective functions. In this essay, a very different strategy, inspired by quantum-mechanical variational methods, is introduced for finding bounds on polynomials. The original polynomial is replaced by an operator acting in a suitably chosen (large) space of states, such that in an appropriate "classical" limit this operator approaches the original polynomial expression made of commutative variables. As a result, approximating the smallest and largest eigenvalues of the coefficient tensor, and thus finding bounds on polynomials, amounts to diagonalizing the resulting quantum operator, represented as a large matrix, and then inspecting the smallest and largest eigenvalues of this matrix. This approach is then successfully applied to standard test examples from tensor eigenvalue literature and other problems of interest in mathematical physics including Strichartz-type inequalities.

math-phCross-listedarXiv:2607.25445•Jul 29, 2026•0 citations
How many quantum queries are required to determine the coefficients of a degree- d polynomial in n variables? We present and analyse quantum algorithms for this multivariate polynomial interpolation problem over the fields F q , R and C . We show that k C and 2 k C queries suffice to achieve probability 1 for C and R , respectively, where k C = ⌈ ( 1 / ( n + 1 ) ) ( n + d d ) ⌉ except for d =2 and four other special cases. For F q , 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 speed-up by a factor of n +1, ( n +1)/2 and ( n + d )/ d for C , R and F q
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. We end with a conjecture about the quantum query complexity of multivariate polynomial interpolation.
Polynomial transformations are basic primitives in quantum algorithms: quantum signal processing and singular value transformation compile univariate polynomials into circuits with query complexity essentially set by degree. Multivariable transformations of noncommuting matrices, however, lack a comparable synthesis theory. We develop a complete constructive theory under joint block access for all polynomials contractive on the prescribed matrix domain. Given a compact finite-state description of a degree-DDD polynomial PPP and 0<τ<10<τ<10<τ<1, we synthesize PPP with (1+τ)(1+τ)(1+τ)-optimal normalization using O(D/τ)O(D/\sqrtτ)O(D/τ​) queries, and exactly DDD under row-block access, matching a degree lower bound. The complete circuit realization is classically computable in polynomial time with polylogarithmic dependence on accuracy. The key to our construction is a finite algorithmic Schur--Agler theorem: the coefficient recurrence defines a polynomial-dimensional continuation space supporting a complete semidefinite certificate for contractivity on the prescribed domain. Factoring this certificate yields the contractive realization underlying the query algorithm. Beyond matrix transformations, our framework lifts multivariable polynomial synthesis to quantum channel transformations. Given coherent Kraus access K={Ka}aK=\{K_a\}_aK={Ka​}a​, we synthesize any finite jointly contractive family of noncommutative polynomial maps K↦{Fb(K)}bK\mapsto\{F_b(K)\}_bK↦{Fb​(K)}b​ as completely positive operations, allowing coherent interference among Kraus histories. Furthermore, channel-level transformations specified by causal Choi data can be synthesized explicitly as fixed-order quantum combs. Collectively, these results point to a broader program: multivariable approximation as a language for multi-operator quantum algorithms and higher-order quantum information processing.
In this paper we study the functions that can be learned through the polynomial interpolation quantum algorithm designed by Childs et al. This algorithm was initially intended to find the coefficients of a multivariate polynomial function defined on finite fields Fq\mathbb{F}_qFq​. We extend its scope to vector inner product functions of the form Os(v)=s⋅v\mathcal{O}_{\mathbf{s}}(\mathbf{v}) = \mathbf{s}\cdot\mathbf{v}Os​(v)=s⋅v where the goal is to find the vector s∈Fqn\mathbf{s} \in \mathbb{F}_q^ns∈Fqn​. We examine the necessary conditions on the domain V\mathcal{V}V of Os\mathcal{O}_{\mathbf{s}}Os​ and prove that the algorithm is optimal for such functions. Furthermore, we show that the success probability approaches 1 for large qqq and large domain order ∣V∣.|\mathcal{V}|.∣V∣. Finally, we provide a conservative formula for the number of queries required to achieve this success probability.
Polynomial transformations of data encoded in quantum operations are a building block of quantum algorithms, and their query complexity measures how often those operations are used. For multiple variables, existing methods either realize restricted polynomial families or implement monomials separately at a query cost exponential in the number of variables. We present a quantum circuit that implements every multivariate trigonometric polynomial up to an explicit normalization. The circuit processes one variable coherently over the frequency components of the remaining variables, allowing all components to share the same signal queries. Each variable is queried exactly as many times as its degree in the polynomial, and we prove that this query complexity is optimal. We further extend the construction to commuting unitaries. The resulting circuit applies the multivariate polynomial simultaneously across their shared eigenbasis, using the minimum numbers of forward and inverse queries to each unitary. We also study trainable rotations with fixed preparation and a local readout of the last input. At query depth at least two, independent uniform initialization gives every active readout gradient a variance lower bound set by its squared branch weight and the inverse square root of the depth, uniformly over data states and dimensions. For supervised squared loss, retaining sample correlations gives an initialization gradient-variance bound in terms of targets and input spectra. This also bounds the expected loss decrease after the first exact gradient step with a specified step size. These results provide a scalable and practical solution for developing multivariate quantum algorithms and quantum learning models.
In this note we study the number of quantum queries required to identify an unknown multilinear polynomial of degree d in n variables over a finite field F_q. Any bounded-error classical algorithm for this task requires Omega(n^d) queries to the polynomial. We give an exact quantum algorithm that uses O(n^(d-1)) queries for constant d, which is optimal. In the case q=2, this gives a quantum algorithm that uses O(n^(d-1)) queries to identify a codeword picked from the binary Reed-Muller code of order d.
The problem of finding lower and upper bounds on multivariate homogeneous polynomials is both difficult and important given its applications to questions ranging from dynamical stability in complex potential landscapes to data analysis. From the standpoint of tensor eigenvalue theory, the question is equivalent to finding the smallest and the largest eigenvalues of the coefficient tensor corresponding to the given polynomial. Standard approaches outlined in the literature amount to running nonlinear iterations in search for the optimal rays along which the growth of the polynomial is fastest or slowest. Unlike the case of matrices (or their corresponding multivariate quadratic forms) convergence of such algorithms for higher-rank tensors is capricious due to the complex topography of polynomial objective functions. In this essay, a very different strategy, inspired by quantum-mechanical variational methods, is introduced for finding bounds on polynomials. The original polynomial is replaced by an operator acting in a suitably chosen (large) space of states, such that in an appropriate "classical" limit this operator approaches the original polynomial expression made of commutative variables. As a result, approximating the smallest and largest eigenvalues of the coefficient tensor, and thus finding bounds on polynomials, amounts to diagonalizing the resulting quantum operator, represented as a large matrix, and then inspecting the smallest and largest eigenvalues of this matrix. This approach is then successfully applied to standard test examples from tensor eigenvalue literature and other problems of interest in mathematical physics including Strichartz-type inequalities.