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:1511.08682 · Leibniz international proceedings in informatics

Polynomials, Quantum Query Complexity, and Grothendieck's Inequality

Scott Aaronson, Andris Ambainis, Jānis Iraids, Martins Kokainis, Juris Smotrovs

Published Nov 27, 2015• 31 citations
arXivHTMLPDF

Abstract

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.

DOI
10.4230/lipics.ccc.2016.25

Related papers

Optimal inequalities for completely bounded polynomials and the limitations of quantum query algorithms

Francisco Escudero Gutiérrez, Miquel Saucedo, Carlos Palazuelos

We consider the problem of establishing limitations on the power of quantum query algorithms via the completely bounded polynomial method. In particular, we prove several optimal functional inequalities involving different notions of completely bounded polynomials. These inequalities lead to limiting theorems for the power of quantum query algorithms that improve on prior works. 1. An optimal root-influence bound for block-multilinear polynomials. Prior work showed that block-multilinear polynomials $p$ of degree $t$ satisfy a root-influence bound, $\|p\|_{\text{cb}}\geq \sum_i \sqrt{\mathrm{Inf}_i[p]}/t^2$, which is stronger than the bound appearing in the Aaronson-Ambainis conjecture. We find the optimal constant in that inequality: $\|p\|_{\text{cb}}\geq \sum_i \sqrt{\mathrm{Inf}_i[p]}/t$. Since the amplitudes of quantum algorithms that query disjoint blocks of inputs-such as $t$-fold forrelation- are block-multilinear polynomials with $\|p\|_{\text{cb}}\leq 1,$ our inequality shows that they satisfy $t\geq \sum_i\sqrt{\mathrm{Inf}_i[p]}$. We prove that this inequality yields both a more efficient classical simulation than prior results based on the Aaronson-Ambainis argument, and a qualitative improvement: all classical queries are nonadaptive. 2. Optimal Fourier growth of the highest level of quantum query algorithms. We show that for every polynomial $p$ defined on $\{-1,1\}^n$ of degree $2t$, the Fourier Growth at the level $2t,$ namely $\|\widehat p_{2t}\|_{\ell_1}$, satisfies $\|\widehat p_{2t}\|_{\ell_1}\leq (en/(2t-1))^{\frac{2t-1}{2}}\|p\|_{\text{cb}}$. This is optimal up to the factor $e$, as witnessed by $2t$-fold forrelation. As quantum query algorithms that make $t$ queries (to the whole input) satisfy $\|p\|_{\text{cb}}\leq 1$, this yields a Fourier growth bound for these algorithms, partially resolving a question by Girish (STOC, 2026).

quant-pharXiv:2609.05201•Sep 7, 2026•2 citations

Quantum Query Algorithms Are Completely Bounded Forms

Srinivasan Arunachalam, Jop Briët, Carlos Palazuelos

We prove a characterization of $t$-query quantum algorithms in terms of the unit ball of a space of degree-$(2t)$ polynomials. Based on this, we obtain a refined notion of approximate polynomial degree that equals the quantum query complexity, answering a question of Aaronson et al. [``Polynomials, Quantum Query Complexity, and Grothendieck's Inequality,” in Proceedings of the 31st Conference on Computational Complexity, CCC 2016, Schloss Dagstuh, 2016, pp. 25:1--25:19]. Our proof is based on a fundamental result of Christensen and Sinclair [ J. Funct. Anal., 72 (1987), pp. 151--181] that generalizes the well-known Stinespring representation for quantum channels to multilinear forms. Using our characterization, we show that many polynomials of degree four are far from those coming from two-query quantum algorithms. We also give a simple and short proof of one of the results of Aaronson et al. showing an equivalence between one-query quantum algorithms and bounded quadratic polynomials.

arXiv:1711.07285•SIAM Journal on Computing•Jan 1, 2019•34 citations

Quantum Query Algorithms are Completely Bounded Forms

Srinivasan Arunachalam, Jop Briët, Carlos Palazuelos

We prove a characterization of quantum query algorithms in terms of polynomials satisfying a certain (completely bounded) norm constraint. Based on this, we obtain a refined notion of approximate polynomial degree that equals the quantum query complexity, answering a question of Aaronson et al. (CCC'16). Using this characterization, we show that many polynomials of degree at least 4 are far from those coming from quantum query algorithms. Our proof is based on a fundamental result of Christensen and Sinclair (J. Funct. Anal., 1987) that generalizes the well-known Stinespring representation for quantum channels to multilinear forms. We also give a simple and short proof of one of the results of Aaronson et al. showing an equivalence between one-query quantum algorithms and bounded quadratic polynomials.

Leibniz international proceedings in informatics•Jan 1, 2018•1 citation

Quantum computing, norms and polynomials

Francisco Escudero Gutiérrez

In this thesis, Quantum computing, norms, and polynomials, we investigate the interplay between quantum mechanics, complexity theory, and functional analysis, three central areas of physics, computer science, and mathematics, respectively. The unifying theme throughout the thesis is the dynamic exchange between quantum computing and functional analysis: we explore new applications of functional inequalities in quantum computing, and, in the process, establish novel results in functional analysis itself. In the first part, we study quantum query algorithms through their correspondence with completely bounded polynomials, as established in earlier work. We begin by revisiting this correspondence, extending it, and presenting it in a new form. Building on this foundation, we draw an analogy between quantum query algorithms and the Grothendieck inequality. Finally, we conclude this part by employing completely bounded polynomials to solve a special case of one of the main open problems in quantum query complexity, the Aaronson–Ambainis conjecture. In the second part, we turn to quantum learning theory, which seeks to determine how much information must be extracted from a quantum system to fully characterize it. We begin by applying existing versions of the Bohnenblust–Hille inequalities and deriving new ones to obtain results in the learning of low-degree quantum objects. We conclude by presenting some of the first results in the emerging area of Hamiltonian testing and learning. We also include a third part, as a bonus, where we gather three new proofs, that we find elegant and concise, of known results related to the analysis of Boolean functions.

•Mar 26, 2026•0 citations

Grothendieck inequalities characterize converses to the polynomial method

Jop Briët, Francisco Escudero Gutiérrez, Sander Gribling

A surprising 'converse to the polynomial method' of Aaronson et al. (CCC'16) shows that any bounded quadratic polynomial can be computed exactly in expectation by a 1-query algorithm up to a universal multiplicative factor related to the famous Grothendieck constant. Here we show that such a result does not generalize to quartic polynomials and 2-query algorithms, even when we allow for additive approximations. We also show that the additive approximation implied by their result is tight for bounded bilinear forms, which gives a new characterization of the Grothendieck constant in terms of 1-query quantum algorithms. Along the way we provide reformulations of the completely bounded norm of a form, and its dual norm.

arXiv:2212.08559•Quantum•Nov 18, 2024•3 citations

The quantum query complexity of approximating the median and related statistics

Ashwin Nayak, Felix Wu

Let X = (z,, , z,-,) be a sequence of n numbers.For 6 > 0, we say that 5; is an e-approximate median if the number of elements strictly less than zi and the number of elements strictly greater than zi are each less than (1 + 6):.We consider the quantum query complexity of computing an c-approximate median, given the sequence X as an oracle.We prove a lower bound of n(min{t,n}) queries for any quantum algorithm that computes an r-approximate median with any constant probability greater than l/2.We also show how an c-approximate median may be computed with 0( $ log(t) log log( $)) oracle queries, which rep resents an improvement over an earlier algorithm due to Grover [ll, 121.Thus, the lower bound we obtain is essentially optimal.The upper and the lower bound both hold in the comparison tree model as well.Our lower bound result is an application of the polynomial paradigm recently introduced to quantum complexity theory by Be& et ol.[l].The main ingredient in the proof is a polynomial degree lower bound far real multilinear polynomials that "approximate" symmetric partial boolean functions.The degree bound extends a result of Patti[15] and also immediately yields lower bounds for the problems of approximating the kth-smallest element, approximating the mean of a sequence of numbers, and approximately counting the number of ones of a boolean function.All bounds obtained come within a polylogarithmic factor of the optimal (as we show by presenting algorithms where no such optimal or near optimal algorithms were known), thus demonstrating the power of the polynomial method.

arXiv:quant-ph/9804066•ACM Symposium on Theory of Computing (STOC)•May 1, 1999•224 citations
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.
We consider the problem of establishing limitations on the power of quantum query algorithms via the completely bounded polynomial method. In particular, we prove several optimal functional inequalities involving different notions of completely bounded polynomials. These inequalities lead to limiting theorems for the power of quantum query algorithms that improve on prior works. 1. An optimal root-influence bound for block-multilinear polynomials. Prior work showed that block-multilinear polynomials ppp of degree ttt satisfy a root-influence bound, ∥p∥cb≥∑iInfi[p]/t2\|p\|_{\text{cb}}\geq \sum_i \sqrt{\mathrm{Inf}_i[p]}/t^2∥p∥cb​≥∑i​Infi​[p]​/t2, which is stronger than the bound appearing in the Aaronson-Ambainis conjecture. We find the optimal constant in that inequality: ∥p∥cb≥∑iInfi[p]/t\|p\|_{\text{cb}}\geq \sum_i \sqrt{\mathrm{Inf}_i[p]}/t∥p∥cb​≥∑i​Infi​[p]​/t. Since the amplitudes of quantum algorithms that query disjoint blocks of inputs-such as ttt-fold forrelation- are block-multilinear polynomials with ∥p∥cb≤1,\|p\|_{\text{cb}}\leq 1,∥p∥cb​≤1, our inequality shows that they satisfy t≥∑iInfi[p]t\geq \sum_i\sqrt{\mathrm{Inf}_i[p]}t≥∑i​Infi​[p]​. We prove that this inequality yields both a more efficient classical simulation than prior results based on the Aaronson-Ambainis argument, and a qualitative improvement: all classical queries are nonadaptive. 2. Optimal Fourier growth of the highest level of quantum query algorithms. We show that for every polynomial ppp defined on {−1,1}n\{-1,1\}^n{−1,1}n of degree 2t2t2t, the Fourier Growth at the level 2t,2t,2t, namely ∥p^2t∥ℓ1\|\widehat p_{2t}\|_{\ell_1}∥p​2t​∥ℓ1​​, satisfies ∥p^2t∥ℓ1≤(en/(2t−1))2t−12∥p∥cb\|\widehat p_{2t}\|_{\ell_1}\leq (en/(2t-1))^{\frac{2t-1}{2}}\|p\|_{\text{cb}}∥p​2t​∥ℓ1​​≤(en/(2t−1))22t−1​∥p∥cb​. This is optimal up to the factor eee, as witnessed by 2t2t2t-fold forrelation. As quantum query algorithms that make ttt queries (to the whole input) satisfy ∥p∥cb≤1\|p\|_{\text{cb}}\leq 1∥p∥cb​≤1, this yields a Fourier growth bound for these algorithms, partially resolving a question by Girish (STOC, 2026).
We prove a characterization of ttt-query quantum algorithms in terms of the unit ball of a space of degree-(2t)(2t)(2t) polynomials. Based on this, we obtain a refined notion of approximate polynomial degree that equals the quantum query complexity, answering a question of Aaronson et al. [``Polynomials, Quantum Query Complexity, and Grothendieck's Inequality,” in Proceedings of the 31st Conference on Computational Complexity, CCC 2016, Schloss Dagstuh, 2016, pp. 25:1--25:19]. Our proof is based on a fundamental result of Christensen and Sinclair [ J. Funct. Anal., 72 (1987), pp. 151--181] that generalizes the well-known Stinespring representation for quantum channels to multilinear forms. Using our characterization, we show that many polynomials of degree four are far from those coming from two-query quantum algorithms. We also give a simple and short proof of one of the results of Aaronson et al. showing an equivalence between one-query quantum algorithms and bounded quadratic polynomials.
We prove a characterization of quantum query algorithms in terms of polynomials satisfying a certain (completely bounded) norm constraint. Based on this, we obtain a refined notion of approximate polynomial degree that equals the quantum query complexity, answering a question of Aaronson et al. (CCC'16). Using this characterization, we show that many polynomials of degree at least 4 are far from those coming from quantum query algorithms. Our proof is based on a fundamental result of Christensen and Sinclair (J. Funct. Anal., 1987) that generalizes the well-known Stinespring representation for quantum channels to multilinear forms. We also give a simple and short proof of one of the results of Aaronson et al. showing an equivalence between one-query quantum algorithms and bounded quadratic polynomials.
In this thesis, Quantum computing, norms, and polynomials, we investigate the interplay between quantum mechanics, complexity theory, and functional analysis, three central areas of physics, computer science, and mathematics, respectively. The unifying theme throughout the thesis is the dynamic exchange between quantum computing and functional analysis: we explore new applications of functional inequalities in quantum computing, and, in the process, establish novel results in functional analysis itself. In the first part, we study quantum query algorithms through their correspondence with completely bounded polynomials, as established in earlier work. We begin by revisiting this correspondence, extending it, and presenting it in a new form. Building on this foundation, we draw an analogy between quantum query algorithms and the Grothendieck inequality. Finally, we conclude this part by employing completely bounded polynomials to solve a special case of one of the main open problems in quantum query complexity, the Aaronson–Ambainis conjecture. In the second part, we turn to quantum learning theory, which seeks to determine how much information must be extracted from a quantum system to fully characterize it. We begin by applying existing versions of the Bohnenblust–Hille inequalities and deriving new ones to obtain results in the learning of low-degree quantum objects. We conclude by presenting some of the first results in the emerging area of Hamiltonian testing and learning. We also include a third part, as a bonus, where we gather three new proofs, that we find elegant and concise, of known results related to the analysis of Boolean functions.
A surprising 'converse to the polynomial method' of Aaronson et al. (CCC'16) shows that any bounded quadratic polynomial can be computed exactly in expectation by a 1-query algorithm up to a universal multiplicative factor related to the famous Grothendieck constant. Here we show that such a result does not generalize to quartic polynomials and 2-query algorithms, even when we allow for additive approximations. We also show that the additive approximation implied by their result is tight for bounded bilinear forms, which gives a new characterization of the Grothendieck constant in terms of 1-query quantum algorithms. Along the way we provide reformulations of the completely bounded norm of a form, and its dual norm.
Let X = (z,, , z,-,) be a sequence of n numbers.For 6 > 0, we say that 5; is an e-approximate median if the number of elements strictly less than zi and the number of elements strictly greater than zi are each less than (1 + 6):.We consider the quantum query complexity of computing an c-approximate median, given the sequence X as an oracle.We prove a lower bound of n(min{t,n}) queries for any quantum algorithm that computes an r-approximate median with any constant probability greater than l/2.We also show how an c-approximate median may be computed with 0( $ log(t) log log( $)) oracle queries, which rep resents an improvement over an earlier algorithm due to Grover [ll, 121.Thus, the lower bound we obtain is essentially optimal.The upper and the lower bound both hold in the comparison tree model as well.Our lower bound result is an application of the polynomial paradigm recently introduced to quantum complexity theory by Be& et ol.[l].The main ingredient in the proof is a polynomial degree lower bound far real multilinear polynomials that "approximate" symmetric partial boolean functions.The degree bound extends a result of Patti[15] and also immediately yields lower bounds for the problems of approximating the kth-smallest element, approximating the mean of a sequence of numbers, and approximately counting the number of ones of a boolean function.All bounds obtained come within a polylogarithmic factor of the optimal (as we show by presenting algorithms where no such optimal or near optimal algorithms were known), thus demonstrating the power of the polynomial method.