The quantum query complexity of learning multilinear polynomials

DOI10.1016/J.IPL.2012.03.002MaRDI QIDQ436558zbMATH OpenOpenAlexFDO

Authors Ashley Montanaro

Publication date 25 July 2012

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1105.3310

zbMATH Keywords

computational complexityReed-Muller codesquantum query complexity

Mathematics Subject Classification ID

Computational learning theory (68Q32) Quantum algorithms and complexity in the theory of computing (68Q12)

Abstract: 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.

Recommendations

• Identifying generalized Reed-Muller codewords by quantum queries
• Quantum algorithm for multivariate polynomial interpolation
• Polynomials, quantum query complexity, and Grothendieck's inequality
• scientific article; zbMATH DE number 6820205
• Efficient quantum algorithm for identifying hidden polynomials

Cites work

• scientific article; zbMATH DE number 5605071 (Why is no real title available?)
• scientific article; zbMATH DE number 1406113 (Why is no real title available?)
• Elements of Information Theory
• Quantum Algorithms for Some Hidden Shift Problems
• Quantum Algorithms to Solve the Hidden Shift Problem for Quadratics and for Functions of Large Gowers Norm
• Quantum Complexity Theory
• Sharp quantum versus classical query complexity separations
• Testing Polynomials over General Fields

Cited in

(11)

• Optimal quantum sample complexity of learning algorithms
• A quantum algorithm for Viterbi decoding of classical convolutional codes
• Efficient quantum algorithm for identifying hidden polynomials
• Quantum algorithms and approximating polynomials for composed functions with shared inputs
• Quantum query complexity of multilinear identity testing
• Polynomial degree vs. quantum query complexity
• Quantum interpolation of polynomials
• Identifying generalized Reed-Muller codewords by quantum queries
• Quantum learning Boolean linear functions w.r.t. product distributions
• Quantum algorithm for multivariate polynomial interpolation
• Classical and quantum function reconstruction via character evaluation

This page was built for publication: The quantum query complexity of learning multilinear polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q436558)