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

Abstract

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|_cb≥ ∑_i √(Inf_i[p])/t², which is stronger than the bound appearing in the Aaronson-Ambainis conjecture. We find the optimal constant in that inequality: |p|_cb≥ ∑_i √(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|_cb≤ 1, our inequality shows that they satisfy t≥ ∑_i√(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}ⁿ of degree 2t, the Fourier Growth at the level 2t, namely |p̂_2t|_ℓ₁, satisfies |p̂_2t|_ℓ₁≤ (en/(2t−1))^(2t−1)/2|p|_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|_cb≤ 1, this yields a Fourier growth bound for these algorithms, partially resolving a question by Girish (STOC, 2026).

Optimal square size for separating the operator and completely bounded norms of Schur multipliers on S^4
Cédric Arhancet
HAL19 Aug 2026PreprintCC BY-NC-ND 4.0Full textAlgebra & number theory Analysis & PDEsHALarXiv
Correlation inequalities for volume polynomials
June Huh, Mateusz Michałek, Botong Wang +1
arXiv25 Oct 2026PreprintCC BY 4.0Full textAlgebra & number theory Combinatorics & discrete mathematicsarXiv
Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalities
Jun-Hyun Kim, Ahmet Alacaoglu
arXiv24 Sep 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
Sharp Bernstein--Nikolskii inequalities for polynomials and entire functions of exponential type
D. V. Gorbachev
arXiv25 Sep 2026PreprintarXiv licenceFull textAnalysis & PDEsarXiv
Scott-type inequalities for trinomial h^*-polynomials
Akiyoshi Tsuchiya
arXiv26 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{gutierrez2026optimal,
  title = {{Optimal inequalities for completely bounded polynomials and the limitations of quantum query algorithms}},
  author = {Francisco Escudero Gutiérrez and Miquel Saucedo and Carlos Palazuelos},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.05201},
  eprint = {2609.05201},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.05201},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Optimal inequalities for completely bounded polynomials and the limitations of quantum query algorithms
AU  - Francisco Escudero Gutiérrez
AU  - Miquel Saucedo
AU  - Carlos Palazuelos
PY  - 2026
DA  - 2026/09/04
PB  - arXiv
DO  - 10.48550/arxiv.2609.05201
UR  - https://arxiv.org/abs/2609.05201
AB  - 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|_cb≥ ∑_i √(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|_cb≥ ∑_i √(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|_cb≤ 1, our inequality shows that they satisfy t≥ ∑_i√(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 |p̂_2t|_ℓ_1, satisfies |p̂_2t|_ℓ_1≤ (en/(2t−1))^(2t−1)/2|p|_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|_cb≤ 1, this yields a Fourier growth bound for these algorithms, partially resolving a question by Girish (STOC, 2026).
ER  -

Abstract

Related

Cite