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:0909.5683

Quantum interpolation of polynomials

Daniel M. Kane, Samuel Kutin

Published Sep 30, 2009• 6 citations
arXivHTMLPDF

Abstract

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.
DOI
10.48550/arxiv.0909.5683

Related papers

Quantum interpolation of polynomials

Daniel M. Kane, Samuel Kutin

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.

Quantum Information and Computation•Jan 1, 2011•8 citations

Quantum lower bounds by polynomials

Robert Beals, Harry Buhrman, Richard Cleve +2 more

We examine the number of queries to input variables that a quantum algorithm requires to compute Boolean functions on {0,1} N in the black-box model. We show that the exponential quantum speed-up obtained for partial functions (i.e., problems involving a promise on the input) by Deutsch and Jozsa, Simon, and Shor cannot be obtained for any total function: if a quantum algorithm computes some total Boolean function f with small error probability using T black-box queries, then there is a classical deterministic algorithm that computes f exactly with O ( Ts 6 ) queries. We also give asymptotically tight characterizations of T for all symmetric f in the exact, zero-error, and bounded-error settings. Finally, we give new precise bounds for AND, OR, and PARITY. Our results are a quantum extension of the so-called polynomial method, which has been successfully applied in classical complexity theory, and also a quantum extension of results by Nisan about a polynomial relationship between randomized and deterministic decision tree complexity.

arXiv:quant-ph/9802049•Journal of the ACM•Jul 1, 2001•922 citations

Quantum lower bounds by polynomials

Robert Beals, Harry Buhrman, Richard Cleve +2 more

We examine the number T of queries that a quantum network requires to compute several Boolean functions on {0,1}/sup N/ in the black-box model. We show that, in the black-box model, the exponential quantum speed-up obtained for partial functions (i.e. problems involving a promise on the input) by Deutsch and Jozsa and by Simon cannot be obtained for any total function: if a quantum algorithm computes some total Boolean function f with bounded-error using T black-box queries then there is a classical deterministic algorithm that computes f exactly with O(T/sup 6/) queries. We also give asymptotically tight characterizations of T for all symmetric f in the exact, zero-error, and bounded-error settings. Finally, we give new precise bounds for AND, OR, and PARITY. Our results are a quantum extension of the so-called polynomial method, which has been successfully applied in classical complexity theory, and also a quantum extension of results by Nisan about a polynomial relationship between randomized and deterministic decision tree complexity.

Annual Symposium on Foundations of Computer Science•Nov 27, 2002•185 citations

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

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•10 citations

Lower bounds of quantum black-box complexity and degree of approximation polynomials by influence of Boolean variables

Yaoyun Shi

We prove that, to compute a Boolean function $f$ on $N$ variables with error probability $ε$, any quantum black-box algorithm has to query at least $\frac{1 - 2\sqrtε}{2} ρ_f N = \frac{1 - 2\sqrtε}{2} \bar{S}_f$ times, where $ρ_f$ is the average influence of variables in $f$, and $\bar{S}_f$ is the average sensitivity. It's interesting to contrast this result with the known lower bound of $Ω(\sqrt{S_f})$, where $S_f$ is the sensitivity of $f$. This lower bound is tight for some functions. We also show for any polynomial $\tilde{f}$ that approximates $f$ with error probability $ε$, $deg(\tilde{f}) \ge 1/4 (1 - \frac{3 ε}{1 + ε})^2 ρ_f N$. This bound can be better than previous known lower bound of $Ω(\sqrt{BS_f})$ for some functions. Our technique may be of intest itself: we apply Fourier analysis to functions mapping $\{0, 1\}^N$ to unit vectors in a Hilbert space. From this viewpoint, the state of the quantum computer at step $t$ can be written as $\sum_{s\in \{0, 1\}^N, |s| \le t} \hatϕ_s (-1)^ {s \cdot x}$, which is handy for lower bound analysis.

arXiv:quant-ph/9904107•Apr 29, 1999•7 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.
We examine the number of queries to input variables that a quantum algorithm requires to compute Boolean functions on {0,1} N in the black-box model. We show that the exponential quantum speed-up obtained for partial functions (i.e., problems involving a promise on the input) by Deutsch and Jozsa, Simon, and Shor cannot be obtained for any total function: if a quantum algorithm computes some total Boolean function f with small error probability using T black-box queries, then there is a classical deterministic algorithm that computes f exactly with O ( Ts 6 ) queries. We also give asymptotically tight characterizations of T for all symmetric f in the exact, zero-error, and bounded-error settings. Finally, we give new precise bounds for AND, OR, and PARITY. Our results are a quantum extension of the so-called polynomial method, which has been successfully applied in classical complexity theory, and also a quantum extension of results by Nisan about a polynomial relationship between randomized and deterministic decision tree complexity.
We examine the number T of queries that a quantum network requires to compute several Boolean functions on {0,1}/sup N/ in the black-box model. We show that, in the black-box model, the exponential quantum speed-up obtained for partial functions (i.e. problems involving a promise on the input) by Deutsch and Jozsa and by Simon cannot be obtained for any total function: if a quantum algorithm computes some total Boolean function f with bounded-error using T black-box queries then there is a classical deterministic algorithm that computes f exactly with O(T/sup 6/) queries. We also give asymptotically tight characterizations of T for all symmetric f in the exact, zero-error, and bounded-error settings. Finally, we give new precise bounds for AND, OR, and PARITY. Our results are a quantum extension of the so-called polynomial method, which has been successfully applied in classical complexity theory, and also a quantum extension of results by Nisan about a polynomial relationship between randomized and deterministic decision tree complexity.
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’.
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.
We prove that, to compute a Boolean function fff on NNN variables with error probability εεε, any quantum black-box algorithm has to query at least 1−2ε2ρfN=1−2ε2Sˉf\frac{1 - 2\sqrtε}{2} ρ_f N = \frac{1 - 2\sqrtε}{2} \bar{S}_f21−2ε​​ρf​N=21−2ε​​Sˉf​ times, where ρfρ_fρf​ is the average influence of variables in fff, and Sˉf\bar{S}_fSˉf​ is the average sensitivity. It's interesting to contrast this result with the known lower bound of Ω(Sf)Ω(\sqrt{S_f})Ω(Sf​​), where SfS_fSf​ is the sensitivity of fff. This lower bound is tight for some functions. We also show for any polynomial f~\tilde{f}f~​ that approximates fff with error probability εεε, deg(f~)≥1/4(1−3ε1+ε)2ρfNdeg(\tilde{f}) \ge 1/4 (1 - \frac{3 ε}{1 + ε})^2 ρ_f Ndeg(f~​)≥1/4(1−1+ε3ε​)2ρf​N. This bound can be better than previous known lower bound of Ω(BSf)Ω(\sqrt{BS_f})Ω(BSf​​) for some functions. Our technique may be of intest itself: we apply Fourier analysis to functions mapping {0,1}N\{0, 1\}^N{0,1}N to unit vectors in a Hilbert space. From this viewpoint, the state of the quantum computer at step ttt can be written as ∑s∈{0,1}N,∣s∣≤tϕ^s(−1)s⋅x\sum_{s\in \{0, 1\}^N, |s| \le t} \hatϕ_s (-1)^ {s \cdot x}∑s∈{0,1}N,∣s∣≤t​ϕ^​s​(−1)s⋅x, which is handy for lower bound analysis.