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:1105.3310 · Information Processing Letters

The quantum query complexity of learning multilinear polynomials

Ashley Montanaro

Published Mar 6, 2012• 17 citations
arXivHTMLPDF
DOI
10.1016/j.ipl.2012.03.002

Related papers

An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree

Andris Ambainis, Aleksandrs Belovs

arXiv:2301.09218•Computational Complexity•Oct 3, 2025•2 citations

Polynomial degree vs. quantum query complexity

Andris Ambainis

arXiv:quant-ph/0305028•Journal of Computer and System Sciences•Nov 30, 2005•175 citations

Exact quantum query complexity of weight decision problems via Chebyshev polynomials

Xiaoyu He, Xiaoming Sun, Guang Yang +1 more

arXiv:1801.05717•Science China Information Sciences•Jan 11, 2023•21 citations

Polynomials, Quantum Query Complexity, and Grothendieck's Inequality

Scott Aaronson, Andris Ambainis, Jānis Iraids +2 more

We show an equivalence between 1-query quantum algorithms and representations by degree-2 polynomials. Namely, a partial Boolean function f is computable by a 1-query quantum algorithm with error bounded by epsilon<1/2 iff f can be approximated by a degree-2 polynomial with error bounded by epsilon'<1/2. This result holds for two different notions of approximation by a polynomial: the standard definition of Nisan and Szegedy and the approximation by block-multilinear polynomials recently introduced by Aaronson and Ambainis [Aaronson/Ambainis, STOC 2015]. The proof uses Grothendieck's inequality to relate two matrix norms, with one norm corresponding to polynomial approximations and the other norm corresponding to quantum algorithms. We also show two results for polynomials of higher degree. First, there is a total Boolean function which requires ~Omega(n) quantum queries but can be represented by a block-multilinear polynomial of degree ~O(sqrt(n)). Thus, in the general case (for an arbitrary number of queries), block-multilinear polynomials are not equivalent to quantum algorithms. Second, for any constant degree k, the two notions of approximation by a polynomial (the standard and the block-multilinear) are equivalent. As a consequence, we solve an open problem from [Aaronson/Ambainis, STOC 2015], showing that one can estimate the value of any bounded degree-k polynomial p:{0,1}^n -> [-1,1] with O(n^{1-1/(2k)) queries.

arXiv:1511.08682•Leibniz international proceedings in informatics•Nov 27, 2015•31 citations

The Quantum Query Complexity of Algebraic Properties

Sebastian Dörn, Thomas Thierauf

Lecture notes in computer science•Aug 27, 2007•20 citations

Quantum Query Complexity of Multilinear Identity Testing

V. Arvind, Partha Mukhopadhyay

Motivated by the quantum algorithm in \cite{MN05} for testing commutativity of black-box groups, we study the following problem: Given a black-box finite ring $R=\angle{r_1,...,r_k}$ where $\{r_1,r_2,...,r_k\}$ is an additive generating set for $R$ and a multilinear polynomial $f(x_1,...,x_m)$ over $R$ also accessed as a black-box function $f:R^m\to R$ (where we allow the indeterminates $x_1,...,x_m$ to be commuting or noncommuting), we study the problem of testing if $f$ is an \emph{identity} for the ring $R$. More precisely, the problem is to test if $f(a_1,a_2,...,a_m)=0$ for all $a_i\in R$. We give a quantum algorithm with query complexity $O(m(1+α)^{m/2} k^{\frac{m}{m+1}})$ assuming $k\geq (1+1/α)^{m+1}$. Towards a lower bound, we also discuss a reduction from a version of $m$-collision to this problem. We also observe a randomized test with query complexity $4^mmk$ and constant success probability and a deterministic test with $k^m$ query complexity.

arXiv:0807.1412•Jul 9, 2008•1 citation
We show an equivalence between 1-query quantum algorithms and representations by degree-2 polynomials. Namely, a partial Boolean function f is computable by a 1-query quantum algorithm with error bounded by epsilon<1/2 iff f can be approximated by a degree-2 polynomial with error bounded by epsilon'<1/2. This result holds for two different notions of approximation by a polynomial: the standard definition of Nisan and Szegedy and the approximation by block-multilinear polynomials recently introduced by Aaronson and Ambainis [Aaronson/Ambainis, STOC 2015]. The proof uses Grothendieck's inequality to relate two matrix norms, with one norm corresponding to polynomial approximations and the other norm corresponding to quantum algorithms. We also show two results for polynomials of higher degree. First, there is a total Boolean function which requires ~Omega(n) quantum queries but can be represented by a block-multilinear polynomial of degree ~O(sqrt(n)). Thus, in the general case (for an arbitrary number of queries), block-multilinear polynomials are not equivalent to quantum algorithms. Second, for any constant degree k, the two notions of approximation by a polynomial (the standard and the block-multilinear) are equivalent. As a consequence, we solve an open problem from [Aaronson/Ambainis, STOC 2015], showing that one can estimate the value of any bounded degree-k polynomial p:{0,1}^n -> [-1,1] with O(n^{1-1/(2k)) queries.
Motivated by the quantum algorithm in \cite{MN05} for testing commutativity of black-box groups, we study the following problem: Given a black-box finite ring R=∠r1,...,rkR=\angle{r_1,...,r_k}R=∠r1​,...,rk​ where {r1,r2,...,rk}\{r_1,r_2,...,r_k\}{r1​,r2​,...,rk​} is an additive generating set for RRR and a multilinear polynomial f(x1,...,xm)f(x_1,...,x_m)f(x1​,...,xm​) over RRR also accessed as a black-box function f:Rm→Rf:R^m\to Rf:Rm→R (where we allow the indeterminates x1,...,xmx_1,...,x_mx1​,...,xm​ to be commuting or noncommuting), we study the problem of testing if fff is an \emph{identity} for the ring RRR. More precisely, the problem is to test if f(a1,a2,...,am)=0f(a_1,a_2,...,a_m)=0f(a1​,a2​,...,am​)=0 for all ai∈Ra_i\in Rai​∈R. We give a quantum algorithm with query complexity O(m(1+α)m/2kmm+1)O(m(1+α)^{m/2} k^{\frac{m}{m+1}})O(m(1+α)m/2km+1m​) assuming k≥(1+1/α)m+1k\geq (1+1/α)^{m+1}k≥(1+1/α)m+1. Towards a lower bound, we also discuss a reduction from a version of mmm-collision to this problem. We also observe a randomized test with query complexity 4mmk4^mmk4mmk and constant success probability and a deterministic test with kmk^mkm query complexity.