The quantum query complexity of learning multilinear polynomials
From MaRDI portal
Publication:436558
DOI10.1016/J.IPL.2012.03.002zbMATH Open1243.68198arXiv1105.3310OpenAlexW2049554200MaRDI QIDQ436558FDOQ436558
Authors: Ashley Montanaro 
Publication date: 25 July 2012
Published in: Information Processing Letters (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1105.3310
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
Computational learning theory (68Q32) Quantum algorithms and complexity in the theory of computing (68Q12)
Cites Work
- Elements of Information Theory
- Quantum Complexity Theory
- Testing Polynomials over General Fields
- Title not available (Why is that?)
- Sharp quantum versus classical query complexity separations
- Quantum Algorithms to Solve the Hidden Shift Problem for Quadratics and for Functions of Large Gowers Norm
- Title not available (Why is that?)
- Quantum Algorithms for Some Hidden Shift Problems
Cited In (10)
- A quantum algorithm for Viterbi decoding of classical convolutional codes
- Efficient quantum algorithm for identifying hidden polynomials
- Quantum query complexity of multilinear identity testing
- Identifying Generalized Reed-Muller Codewords by Quantum Queries
- Polynomial degree vs. quantum query complexity
- Quantum interpolation of polynomials
- Title not available (Why is that?)
- 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)
