Quantum interpolation of polynomials

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.

• Publication year

  2009

• Venue

  arXiv.org

• Publication date

  2009-09-30

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  arXiv 0909.5683
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Quantum Computation and Quantum Information: Bibliography

  2010cited by this paper
• On Computation and Communication with Small Bias

  2007cited by this paper
• Negative weights make adversaries stronger

  2006cited by this paper
• Quantum Lower Bound for the Collision Problem with Small Range

  2005cited by this paper
• Quantum lower bounds for the collision and the element distinctness problems

  2001cited by this paper
• Quantum lower bounds by quantum arguments

  2000influential reference
• Limit on the Speed of Quantum Computation in Determining Parity

  1998cited by this paper
• Quantum lower bounds by polynomials

  1998cited by this paper
• Quantum Entanglement and the Communication Complexity of the Inner Product Function

  1997cited by this paper
• A fast quantum mechanical algorithm for database search

  1996cited by this paper
• Learning DNF over the uniform distribution using a quantum example oracle

  1995cited by this paper
• Introduction to Coding Theory

  1993cited by this paper
• On the degree of polynomials that approximate symmetric Boolean functions (preliminary version)

  1992cited by this paper
• Rapid solution of problems by quantum computation

  1992cited by this paper
• On the degree of boolean functions as real polynomials

  1992cited by this paper
• A theory of the learnable

  1984cited by this paper

• A Brief Introduction to Quantum Query Complexity

  2025cites this paper
• The Qudit ZH Calculus for Arbitrary Finite Fields: Universality and Application

  2024cites this paper
• Cosine series quantum sampling method with applications in signal and image processing

  2020cites this paper
• Quantum algorithm for multivariate polynomial interpolation

  2017cites this paper
• Quantum Oracle Classification - The Case of Group Structure

  2015cites this paper
• Cryptography in the age of quantum computers

  2015cites this paper
• Optimal Quantum Algorithm for Polynomial Interpolation

  2015cites this paper
• A Survey of Quantum Property Testing

  2013cites this paper
• Quantum-Secure Message Authentication Codes

  2013cites this paper
• APPROVED FOR PUBLIC RELEASE; DISTRIBUTION UNLIMITED

  2011cites this paper