Metraipolis › archive › dc_97dae3f960cb

Optimal inequalities for completely bounded polynomials and the limitations of quantum query algorithms — arXiv:2609.05201

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.05201
License (as archived): CC0-1.0
Archived: 2026-10-16T23:55:10.970Z
SHA-256 of the archived text: 792a9d79decfacd47813d3899bbb125d4e882dcbb41b1f12d160f2a7e335bc46
Stable URL of this page: https://metraipolis.com/documento/dc_97dae3f960cb

How to cite

Optimal inequalities for completely bounded polynomials and the limitations of quantum query algorithms — arXiv:2609.05201 — arXiv (en), https://arxiv.org/abs/2609.05201 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_97dae3f960cb (Metraipolis archive dc_97dae3f960cb, sha256 792a9d79decfacd47813d3899bbb125d4e882dcbb41b1f12d160f2a7e335bc46)

BibTeX

@misc{dc97dae3f960cb,
  title = {Optimal inequalities for completely bounded polynomials and the limitations of quantum query algorithms — arXiv:2609.05201},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.05201},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_97dae3f960cb; sha256 792a9d79decfacd47813d3899bbb125d4e882dcbb41b1f12d160f2a7e335bc46},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.05201. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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).

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-07 in cs.CC).
Categorie arXiv: Quantum Physics (quant-ph) ; Computational Complexity (cs.CC); Functional Analysis (math.FA).
Pagina del lavoro: https://arxiv.org/abs/2609.05201 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T23:23:07.983Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-09-07?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).