Source-linked AI summary
Optimal inequalities for completely bounded polynomials and the limitations of quantum query algorithms
Francisco Escudero Gutiérrez, Miquel Saucedo, Carlos Palazuelos
TL;DR
The paper studies limitations on quantum query algorithms, motivated by the possibility that exponential speedups require structured input domains. It uses completely bounded polynomial inequalities to derive classical simulation results, including deterministic nonadaptive approximations for amplitudes of block-disjoint query algorithms.
Problem
The paper addresses how to delineate limitations on exponential quantum speedups and when quantum query algorithms can be classically simulated on Boolean inputs.
Method
The paper proves functional inequalities involving completely bounded polynomial norms and applies the characterization of quantum query algorithms through these norms.
Results
At most t^2/ε^2δ nonadaptive queries deterministically ε-approximate amplitudes on at least a (1−δ)-fraction of inputs for algorithms querying t disjoint input blocks.
Takeaways & Limitations
The resulting simulation improves prior bounds by saving a factor of 1/δ and ensuring that all classical queries are nonadaptive.
Takeaways & Limitations
The Fourier-growth proof technique does not provide tight upper bounds for intermediate degrees s∈[2t−2] because its key matrix identity fails for multi-indices with repeated elements.
Abstract
from arXiv · showhide
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).
1 Introduction
The paper develops completely bounded polynomial inequalities to limit quantum query algorithms, improving classical simulation results and Fourier-growth bounds. Its main results optimally strengthen root-influence control for block-multilinear polynomials and highest-level Fourier growth for standard quantum algorithms.
- Motivation: Quantum query acceptance probabilities are bounded polynomials of degree at most 2t, linking query complexity to Fourier analysis and polynomial inequalities.The Aaronson–Ambainis conjecture seeks influence-based limitations for bounded low-degree polynomials, but remains open in general.
- Root-influence bound: Theorem 1.3 finds the optimal constant in the completely bounded root-influence inequality for block-multilinear polynomials.The inequality is tight, witnessed by the product polynomial a(x1,...,xt)=x1(1)···xt(1).
- Root-influence bound: t-query algorithms querying disjoint input blocks satisfy a total root-influence bound that enables efficient classical simulation with non-adaptive queries.The resulting deterministic simulation uses O(t^2/ε^2δ) queries on at least a (1−δ)-fraction of inputs, improving the prior O(t^3/(ε^4δ^3)) adaptive simulation.
- Classical simulation: Theorem 1.4 gives a junta approximation using at most (Σ_i√Inf_i[p])^2/(ε^2δ) variables and error ε on a (1−δ)-fraction of inputs.For general bounded degree-t polynomials, this yields exp(O(t)) non-adaptive-query simulation almost everywhere, although the address function prevents an efficient simulation for all bounded polynomials.
- Fourier growth: Theorem 1.6 establishes a nearly tight upper bound on the level-2t Fourier growth of t-query quantum algorithms, resolving the highest-level case of Girish’s question.The bound is ∥p̂_2t∥_ℓ1 ≤ (en/(2t−1))^(t−1/2), while 2t-fold forrelation attains (n/2t)^(t−1/2).
- Fourier growth: The Fourier-growth proof is limited to the highest and second-highest levels because repeated indices invalidate a key matrix identity at lower degrees.The paper also generalizes the Fourier-growth result to algorithms with bounded adaptivity and quantifies limitations from parallel queries.
2 Preliminaries
The preliminaries define the norms, Fourier quantities, multilinear representations, and query-algorithm refinements used to analyze completely bounded polynomials.
- Fourier analysis: Fourier characters form an orthonormal basis on the Boolean cube, and Parseval’s identity relates Fourier coefficients to polynomial norms.The section also defines variance and Fourier growth through degree-level coefficient norms.
- Influences and norms: The influence of a variable is defined by the expected squared change under flipping that coordinate, while maximum influence and variance quantify polynomial sensitivity.These quantities are taken under the uniform measure on the Boolean cube.
- Completely bounded norms: The completely bounded norm is defined for polynomials and multilinear forms using matrix-valued substitutions, while for linear forms it equals the infinity norm.The notation section also defines tensor powers, multi-indices, and the odd-occurrence set S_i.
- Multilinear forms and block-multilinear polynomials: A t-linear form is linear in each factor, and block-multilinear polynomials use disjoint variable blocks whose completely bounded norm is defined through the corresponding multilinear form.The block ordering specifies how variables from the t blocks enter the form.
- Quantum query polynomial method: A t-query quantum algorithm’s acceptance probability is represented by a 2t-linear form evaluated on repeated copies of (x,1^n), with bounded operator-norm matrices encoding the computation.This representation underlies the completely bounded polynomial method.
- Specialized query models: For algorithms querying disjoint input blocks, amplitudes have t-linear representations, while parallel non-adaptive amplitudes have linear-form representations.Acceptance probabilities for disjoint-block algorithms can be expressed as sums of squared amplitudes.
- Bounded adaptivity: The paper extends the polynomial-method representation to algorithms with bounded adaptivity by expressing acceptance probabilities through a 2r-linear form across query rounds.The total number of queries is t = Σ_i t_i, and the representation tracks the query count in each round.
3 Optimal root-influence conjecture for completely bounded block-multilinear polynomials
The section proves optimal functional inequalities for completely bounded block-multilinear polynomials and derives stronger classical simulations for associated quantum-query amplitudes. The resulting simulations improve efficiency and use non-adaptive classical queries.
- Root-influence inequality: Theorem 3.1 establishes a functional inequality for block-multilinear polynomials of degree t, serving as the basis for the section’s corollaries.Its proof combines the main estimate with auxiliary constructions involving orthonormal sets, matrices, and trace norms.
- Root-influence inequality: Theorem 1.3 gives the root-influence bound for completely bounded block-multilinear polynomials, and the constant is optimal.The witness is a product polynomial with completely bounded norm 1.
- Simulation results: The simulation results are organized by progressively stronger functional-analytic assumptions, with stronger assumptions yielding more efficient simulations.The section compares the Aaronson–Ambainis result with two newer simulation results.
- Simulation results: Theorem 1.4 provides a deterministic classical approximation using at most (Σ_i√Inf_i[p])^2/(ε^2δ) queries on a (1−δ)-fraction of inputs.The approximation has error ε, and the resulting algorithm is non-adaptive.
4 Sharp Fourier Growth for high-degree levels of quantum algorithms
This section establishes sharp Fourier-growth bounds for the highest-degree level of acceptance probabilities of quantum query algorithms, treating sequential and bounded-adaptivity settings.
- 4.1 The standard case: Theorem 1.6 bounds the level-2t Fourier growth of acceptance probabilities for t-query sequential quantum algorithms.The section assumes 2t ≤ n because Boolean-cube polynomials have no monomials of degree greater than n.
- 4.1 The standard case: The proof represents the polynomial through a completely bounded 2t-linear form and evaluates that form on operator-norm-bounded matrices.A coefficient-relating lemma connects Fourier coefficients of the polynomial with those of its multilinear form.
- 4.1 The standard case: The proof exploits that degree-2t monomials correspond to multi-indices with no repeated elements.Repeated elements would make the relevant matrix evaluation vanish, which is why the argument does not extend directly to lower levels.
- 4.1 The standard case: The technique does not provide tight upper bounds for Fourier levels s ≤ 2t−2.The stated obstruction is the presence of repeated elements in the multi-indices associated with those levels.
- 4.2 Bounded adaptivity: The same Fourier-growth strategy extends to adaptive algorithms with bounded rounds of adaptivity.Theorem 4.3 parameterizes the result by the queries per round, their maximum, and the total number of queries.
5 Classical simulation of non-adaptive quantum query algorithms
This section shows that non-adaptive quantum query algorithms can be simulated by non-adaptive randomized classical algorithms using Fourier-coefficient bounds for their amplitudes.
- Simulation result: Non-adaptive quantum query algorithms can be efficiently simulated by classical non-adaptive query algorithms.The argument relies on the equality between the ℓ1 norm of linear-form tensor coefficients and the completely bounded norm.
- Amplitude bounds: The amplitudes of t-query non-adaptive quantum algorithms have bounded Fourier-coefficient ℓ1 norm.This follows from the linear-form representation and the completely bounded norm bound.
- Simulation result: Corollary 1.8 applies this construction to acceptance probabilities of algorithms that measure all qubits and accept on r measurement outcomes.It gives a non-adaptive randomized classical estimator with additive error ε and success probability at least 1−δ.
- Polynomial simulation: For a degree-t polynomial, a non-adaptive randomized classical algorithm estimates its value with error at most ε∥p̂∥1 and failure probability at most δ.The sampling procedure uses O(log(1/δ)/ε^2) samples.
- Polynomial simulation: The simulation queries t times the number of sampled terms, and all queried input entries are accessed simultaneously.Thus, the classical algorithm makes no adaptive query choices.