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

Quantum Information and Computation

Quantum interpolation of polynomials

Daniel M. Kane, Samuel Kutin

Published Jan 1, 2011• 7 citations
Publisher

Abstract

Can a quantum computer efficiently interpolate polynomials? We consider black-box algorithms that seek to learn information about a polynomial $f$ from input/output pairs $(x_i, f(x_i))$. We define a more general class of \emph{$(d,S)$-independent} function properties, where, outside of a set $S$ of exceptions, knowing $d$ input values does not help one predict the answer. There are essentially two strategies to computing such a function: query $d+1$ random input values, or search for one of the $|S|$ exceptions. We show that, up to constant factors, we cannot beat these two approaches.

DOI
10.26421/qic11.1-2-7

Related papers

Quantum interpolation of polynomilas

Daniel M. Kane, Samuel Kutin

Can a quantum computer efficiently interpolate polynomials? We consider black-boxalgorithms that seek to learn information about a polynomial f from input/output pairs(xi, f(xi)). We define a more general class of (d, S)-independent function properties,where, outside of a set S of exceptions, knowing d input values does not help one predictthe answer. There are essentially two strategies to computing such a function: queryd + 1 random input values, or search for one of the |S| exceptions. We show that, up toconstant factors, we cannot beat these two approaches.

•Jan 1, 2011•7 citations

Quantum interpolation of polynomials

Daniel M. Kane, Samuel Kutin

We consider quantum interpolation of polynomials. We imagine a quantum computer with black-box access to input/output pairs (x_i, f(x_i)), where f is a degree-d polynomial, and we wish to compute f(0). We give asymptotically tight quantum lower bounds for this problem, even in the case where 0 is among the possible values of x_i.

arXiv:0909.5683•Sep 30, 2009•0 citations

Quantum algorithms and learning theory

Srinivasan Arunachalam

This thesis studies strengths and weaknesses of quantum computers. In the first part we present three contributions to quantum algorithms. 1) consider a search space of N elements. One of these elements is "marked" and our goal is to find this. We describe a quantum algorithm to solve this problem using essentially sqrt{N} queries and other operations, improving over the gate count of Grover's algorithm. 2) We give a succinct characterization of quantum algorithms in terms of polynomials, and develop a new technique for showing upper and lower bounds on quantum query complexity based on this. 3) One generic technique used to compute the minimum of a given function is "gradient descent". We present a quantum gradient-calculation algorithm and a gradient-optimization algorithm that is quadratically faster than classical algorithms. In the second part of this thesis we look at quantum learning theory. 1) We survey quantum learning theory, describing the main results known for three models of learning, using classical as well as quantum data: exact learning from membership queries, the probably approximately correct (PAC) learning model, and the agnostic learning model. 2) We then consider if a quantum learner can PAC-learn a given concept class from fewer quantum examples. We give a negative answer by showing that quantum examples are not more powerful than classical random examples, both for PAC learning and for agnostic learning.

•Apr 25, 2018•1 citation

Quantum Computational Complexity Theory and Lower Bounds

Phillip Kaye, Raymond Laflamme, Michele Mosca

We have seen in the previous chapters that quantum computers seem to be more powerful than classical computers for certain problems. There are limits on the power of quantum computers, however. Since a classical computer can simulate a quantum computer, a quantum computer can only compute the same set of functions that a classical computer can. The advantage of using a quantum computer is that the amount of resources needed by a quantum algorithm might be much less than what is needed by the best classical algorithm. In Section 9.1 we briefly define some classical and quantum complexity classes and give some relationships between them. Most of the interesting questions relating classical and quantum complexity classes remain open. For example, we do not yet know if a quantum computer is capable of efficiently solving an NP-complete problem (defined later). One can prove upper bounds on the difficulty of a problem by providing an algorithm that solves that problem, and proving that it will work within in a given running time. But how does one prove a lower bound on the computational complexity of a problem? For example, if we wish to find the product of two n-bit numbers, computing the answer requires outputting roughly 2n bits and that requires Ω(n) steps (in any computing model with finite-sized gates). The best-known upper bound for integer multiplication is O(n log n log log n) steps. It has proved extremely difficult to derive non-trivial lower bounds on the computational complexity of a problem. Most of the known non-trivial lower bounds are in the ‘black-box’ model (for both classical and quantum computing), where we only query the input via a ‘black-box’ of a specific form. We discuss the black-box model in more detail in Section 9.2. We then sketch several approaches for proving black-box lower bounds. The first technique has been called the ‘hybrid method’ and was used to prove that quantum searching requires Ω(√n) queries to succeed with constant probability. The second technique is called the ‘polynomial method’. We then describe a technique based on ‘block sensitivity’, and conclude with a technique known as the ‘adversary method’.

Oxford University Press eBooks•Nov 16, 2006•0 citations

Quantum algorithm for multivariate polynomial interpolation

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

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

arXiv:1701.03990•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•Jan 1, 2018•8 citations

Equivalences and Separations Between Quantum and Classical Learnability

Rocco A. Servedio, Steven J. Gortler

We consider quantum versions of two well-studied models of learning Boolean functions: Angluin's model of exact learning from membership queries and Valiant's probably approximately correct (PAC) model of learning from random examples. For each of these two learning models we establish a polynomial relationship between the number of quantum or classical queries required for learning. These results contrast known results that show that testing black-box functions for various properties, as opposed to learning, can require exponentially more classical queries than quantum queries. We also show that, under a widely held computational hardness assumption (the intractability of factoring Blum integers), there is a class of Boolean functions which is polynomial-time learnable in the quantum version but not the classical version of each learning model. For the model of exact learning from membership queries, we establish a stronger separation by showing that if any one-way function exists, then there is a class of functions which is polynomial-time learnable in the quantum setting but not in the classical setting. Thus, while quantum and classical learning are equally powerful from an information theory perspective, the models are different when viewed from a computational complexity perspective.

SIAM Journal on Computing•Jan 1, 2004•121 citations
Can a quantum computer efficiently interpolate polynomials? We consider black-box algorithms that seek to learn information about a polynomial fff from input/output pairs (xi,f(xi))(x_i, f(x_i))(xi​,f(xi​)). We define a more general class of \emph{(d,S)(d,S)(d,S)-independent} function properties, where, outside of a set SSS of exceptions, knowing ddd input values does not help one predict the answer. There are essentially two strategies to computing such a function: query d+1d+1d+1 random input values, or search for one of the ∣S∣|S|∣S∣ exceptions. We show that, up to constant factors, we cannot beat these two approaches.
Can a quantum computer efficiently interpolate polynomials? We consider black-boxalgorithms that seek to learn information about a polynomial f from input/output pairs(xi, f(xi)). We define a more general class of (d, S)-independent function properties,where, outside of a set S of exceptions, knowing d input values does not help one predictthe answer. There are essentially two strategies to computing such a function: queryd + 1 random input values, or search for one of the |S| exceptions. We show that, up toconstant factors, we cannot beat these two approaches.
This thesis studies strengths and weaknesses of quantum computers. In the first part we present three contributions to quantum algorithms. 1) consider a search space of N elements. One of these elements is "marked" and our goal is to find this. We describe a quantum algorithm to solve this problem using essentially sqrt{N} queries and other operations, improving over the gate count of Grover's algorithm. 2) We give a succinct characterization of quantum algorithms in terms of polynomials, and develop a new technique for showing upper and lower bounds on quantum query complexity based on this. 3) One generic technique used to compute the minimum of a given function is "gradient descent". We present a quantum gradient-calculation algorithm and a gradient-optimization algorithm that is quadratically faster than classical algorithms. In the second part of this thesis we look at quantum learning theory. 1) We survey quantum learning theory, describing the main results known for three models of learning, using classical as well as quantum data: exact learning from membership queries, the probably approximately correct (PAC) learning model, and the agnostic learning model. 2) We then consider if a quantum learner can PAC-learn a given concept class from fewer quantum examples. We give a negative answer by showing that quantum examples are not more powerful than classical random examples, both for PAC learning and for agnostic learning.
We have seen in the previous chapters that quantum computers seem to be more powerful than classical computers for certain problems. There are limits on the power of quantum computers, however. Since a classical computer can simulate a quantum computer, a quantum computer can only compute the same set of functions that a classical computer can. The advantage of using a quantum computer is that the amount of resources needed by a quantum algorithm might be much less than what is needed by the best classical algorithm. In Section 9.1 we briefly define some classical and quantum complexity classes and give some relationships between them. Most of the interesting questions relating classical and quantum complexity classes remain open. For example, we do not yet know if a quantum computer is capable of efficiently solving an NP-complete problem (defined later). One can prove upper bounds on the difficulty of a problem by providing an algorithm that solves that problem, and proving that it will work within in a given running time. But how does one prove a lower bound on the computational complexity of a problem? For example, if we wish to find the product of two n-bit numbers, computing the answer requires outputting roughly 2n bits and that requires Ω(n) steps (in any computing model with finite-sized gates). The best-known upper bound for integer multiplication is O(n log n log log n) steps. It has proved extremely difficult to derive non-trivial lower bounds on the computational complexity of a problem. Most of the known non-trivial lower bounds are in the ‘black-box’ model (for both classical and quantum computing), where we only query the input via a ‘black-box’ of a specific form. We discuss the black-box model in more detail in Section 9.2. We then sketch several approaches for proving black-box lower bounds. The first technique has been called the ‘hybrid method’ and was used to prove that quantum searching requires Ω(√n) queries to succeed with constant probability. The second technique is called the ‘polynomial method’. We then describe a technique based on ‘block sensitivity’, and conclude with a technique known as the ‘adversary method’.
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 quantum versions of two well-studied models of learning Boolean functions: Angluin's model of exact learning from membership queries and Valiant's probably approximately correct (PAC) model of learning from random examples. For each of these two learning models we establish a polynomial relationship between the number of quantum or classical queries required for learning. These results contrast known results that show that testing black-box functions for various properties, as opposed to learning, can require exponentially more classical queries than quantum queries. We also show that, under a widely held computational hardness assumption (the intractability of factoring Blum integers), there is a class of Boolean functions which is polynomial-time learnable in the quantum version but not the classical version of each learning model. For the model of exact learning from membership queries, we establish a stronger separation by showing that if any one-way function exists, then there is a class of functions which is polynomial-time learnable in the quantum setting but not in the classical setting. Thus, while quantum and classical learning are equally powerful from an information theory perspective, the models are different when viewed from a computational complexity perspective.