A proof of the Aaronson-Ambainis conjecture

David Turturean

Résumé IA · arXiv: 2611.09773v1 · cs.CC

A proof of the Aaronson-Ambainis conjecture

David Turturean

Article original Soumis à arXiv le 06 Nov. 2026 60 pages. Lean formalization and reproducibility materials: https://github.com/physical-superintelligence/aaronson-ambainis Licence : NONEXCLUSIVE-DISTRIB 1.0 Aussi en : en

Comment lire ce résumé ? Guide illustré

L’essentiel

L’article prouve la conjecture d’Aaronson–Ambainis : tout polynôme borné de degré d et de variance positive possède une variable d’influence au moins polynomialement grande en la variance et le degré.

Question

Les polynômes de faible degré à valeurs bornées sur le cube discret ont-ils nécessairement une variable influente ? Cette propriété permet-elle de simuler, sur la plupart des entrées, les algorithmes quantiques à requêtes par des algorithmes classiques utilisant un nombre polynomial de requêtes ?

Méthode

L’auteur établit d’abord une borne sur le coût des lignes associées aux fonctions bornées de degré au plus d, puis relie ces lignes aux influences par des inégalités pour les fonctions booléennes et réelles, avec intégration sur les niveaux de la fonction. Le théorème principal garantit une influence d’au moins (√15/(500π⁴)) Var(f)^(5/2)/d⁶ ; dans la normalisation sur {0,1}ⁿ, la borne est au moins (Var[p]/d)⁷. La preuve est annoncée comme formalisée et vérifiée par le noyau de Lean.

Résultats

Résultat Toute fonction f : {−1,1}ⁿ → [−1,1] de degré au plus d ≥ 1 possède une variable dont l’influence satisfait la borne explicite en fonction de sa variance et de son degré.
Voir le passage dans l’article
Then there is a coordinate $j\in[n]$ with $$\operatorname{Inf}_{j}(f)\;\geq\;\frac{\sqrt{15}}{500\,\pi^{4}}\cdot\frac{\operatorname{Var}(f)^{5/2}}{d^{6}}.$$
Résultat Dans la normalisation de la conjecture, un polynôme de degré au plus d, à valeurs dans [0,1] et de variance positive, possède une variable d’influence au moins égale à (Var[p]/d)⁷.
Voir le passage dans l’article
$$\operatorname{Inf}_{i}[p]\;\geq\;\frac{8\sqrt{15}}{125\,\pi^{4}}\cdot\frac{\operatorname{Var}[p]^{5/2}}{d^{6}}\;\geq\;\Bigl(\frac{\operatorname{Var}[p]}{d}\Bigr)^{7}.$$
Résultat La conjecture de simulation classique est obtenue avec une borne explicite de (4T)⁸ ε⁻¹⁴ δ⁻⁸ requêtes classiques pour approximer la probabilité d’acceptation d’un algorithme quantique à T requêtes sur une fraction 1−δ des entrées.
Voir le passage dans l’article
For (i), the proof of [AA14, Theorem 3.3] with the exponent $7$ gives a deterministic classical algorithm that makes at most $(4T)^{8}\varepsilon^{-14}\delta^{-8}$ queries.
Interprétation des auteurs Le résultat s’étend, par les implications citées dans l’article, aux distributions produit biaisées et aux chaînes de poids de Hamming fixé.
Voir le passage dans l’article
Hence, by [GMNR, Theorem 4.3], the statements $\mathrm{AA}(\mu_{p})$ and $\mathrm{AA}(\nu_{p})$ hold for every $p\in(0,1)$, and so does the conclusion of [GMNR, Theorem 4.14].

Limites

Le théorème principal porte sur des fonctions définies sur le cube discret, bornées entre −1 et 1 et de degré au plus d ; il ne traite pas directement des modèles de calcul quantique autres que ceux couverts par les conséquences en complexité des requêtes.

Portée

Selon l’auteur, la preuve résout la conjecture ouverte et donne une borne polynomiale explicite sur l’influence d’une variable. Elle établit ainsi les conséquences annoncées pour la simulation classique sur la plupart des entrées et soutient l’idée que les accélérations quantiques superpolynomiales dans le modèle des requêtes nécessitent une structure, par exemple une promesse sur les entrées.

Rédigé par une IA à partir de l’article. Les passages cités sont vérifiés mot pour mot dans le texte analysé ; le reste peut contenir des erreurs.

Mots clés générés par l'IA : Conjecture d’Aaronson–Ambainis influence des variables polynômes booléens complexité des requêtes quantiques formalisation Lean

Pour aller plus loin

Résumé Complet
Résumé vulgarisé
Article de blog
Abstract original

L’article étudie la conjecture d’Aaronson–Ambainis, selon laquelle toute fonction polynomiale de faible degré, bornée sur le cube booléen et de variance non négligeable, doit dépendre fortement d’au moins une variable. Cette question est liée à la complexité des requêtes quantiques : la probabilité d’acceptation d’un algorithme quantique effectuant $T$ requêtes est un polynôme de degré au plus $2T$. Une variable influente permet à un algorithme classique de réduire l’incertitude en interrogeant cette variable. La conjecture prédit ainsi que, sans structure particulière imposée aux entrées, les avantages quantiques considérables ne peuvent généralement pas persister sur la plupart d’entre elles. Le résultat principal établit la conjecture avec une borne explicite. Pour toute fonction $f$ définie sur $\{-1,1\}^n$, à valeurs dans $[-1,1]$, de degré au plus $d$ et de variance $\operatorname{Var}(f)$, il existe une variable dont l’influence quadratique est au moins \[ \frac{\sqrt{15}}{500\pi^4}\,\frac{\operatorname{Var}(f)^{5/2}}{d^6}. \] Dans la convention usuelle sur $\{0,1\}^n$, cela implique qu’un polynôme de degré $d$, à valeurs dans $[0,1]$ et de variance au moins $\varepsilon$, possède une variable d’influence au moins $(\varepsilon/d)^7$. Le théorème fournit donc une dépendance polynomiale en la variance et le degré, plutôt qu’une dépendance exponentielle en $d$, comme dans les résultats généraux antérieurs rapportés par l’article. La preuve établit une chaîne d’inégalités reliant des outils combinatoires à l’analyse des polynômes. Elle introduit les « lignes », qui associent à chaque point un vecteur de poids non négatifs bornant simultanément les variations de la fonction pour tout ensemble de coordonnées retournées. Pour une fonction booléenne, ces objets correspondent aux certificats fractionnaires. Au cœur de l’argument combinatoire se trouve un théorème de bijection, démontré par l’étude d’un déterminant dont les entrées sont des monômes. Ce théorème contrôle à la fois les coordonnées qu’une bijection peut modifier et le nombre de fois où elle conserve chaque coordonnée. Il mène à une inégalité portant sur les paires de points où la fonction prend des valeurs opposées, puis à une version pondérée faisant intervenir les lignes. Pour étendre l’argument aux fonctions réelles, les auteurs appliquent cette inégalité aux ensembles de niveau de la fonction, puis intègrent sur l’ensemble des seuils. Le calcul transforme les différences de valeurs en moments d’ordre trois et fait apparaître les incréments absolus moyens par coordonnée. Une inégalité sur ces moments, évaluée autour d’une médiane, montre que, si les lignes ont un coût maximal $K$, une coordonnée possède un incrément moyen d’au moins $\operatorname{Var}(f)^{3/2}/(6K^2)$. Une étape de moyennisation sur des coordonnées de faible influence préserve une fraction de la variance et permet de convertir cette borne en une borne sur l’influence quadratique.

Une preuve quantitative de la conjecture d’Aaronson–Ambainis

Dans l’informatique quantique, une question importante est de savoir quand un algorithme quantique peut surpasser les méthodes classiques. Le degré d’un polynôme fournit un lien utile entre ces deux domaines : la probabilité d’acceptation d’un algorithme quantique qui effectue $T$ requêtes à son entrée est représentée par un polynôme de degré au plus $2T$. La conjecture d’Aaronson–Ambainis porte sur les conséquences de cette structure polynomiale.

Dans « A proof of the Aaronson-Ambainis conjecture », David Turturean établit cette conjecture avec une borne explicite. Le résultat donne une garantie quantitative sur le fait qu’un polynôme de faible degré, dont les valeurs restent bornées, doit être fortement influencé par au moins une variable dès lors que sa variance n’est pas trop faible. Cette variable peut alors fournir une piste pour réduire l’incertitude en interrogeant l’entrée.

La conjecture et son importance

Considérons une fonction définie sur le cube booléen, dont les coordonnées peuvent prendre les valeurs $-1$ ou $1$. La conjecture affirme qu’une fonction polynomiale de faible degré, bornée et présentant une variance notable ne peut pas répartir uniformément toute sa dépendance entre un très grand nombre de variables. Au moins une coordonnée doit avoir une influence importante sur sa valeur.

Cette idée éclaire la comparaison entre les algorithmes quantiques et classiques. Si une variable joue un rôle particulièrement important, un algorithme classique peut l’interroger pour obtenir une information utile sur la fonction. La conjecture prédit donc que, sans structure particulière imposée aux entrées, les avantages quantiques considérables ne devraient généralement pas persister pour la plupart d’entre elles.

Une borne explicite sur l’influence

Le théorème principal donne une estimation précise. Pour toute fonction $f$ définie sur $\{-1,1\}^n$, à valeurs dans $[-1,1]$, de degré au plus $d$ et de variance $\operatorname{Var}(f)$, il existe une variable dont l’influence quadratique est au moins :

$\frac{\sqrt{15}}{500\pi^4}\,\frac{\operatorname{Var}(f)^{5/2}}{d^6}$.

La formule montre directement le rôle de deux paramètres : une variance plus élevée renforce la borne, tandis qu’un degré plus élevé l’affaiblit. Dans la convention habituelle sur $\{0,1\}^n$, le résultat implique qu’un polynôme de degré $d$, à valeurs dans $[0,1]$ et de variance au moins $\varepsilon$, possède une variable d’influence au moins $(\varepsilon/d)^7$.

L’intérêt majeur est le caractère polynomial de cette dépendance en la variance et le degré. Selon les résultats généraux antérieurs rapportés dans l’article, les bornes disponibles dépendaient exponentiellement de $d$. La nouvelle estimation fournit donc une garantie plus utile lorsque le degré augmente.

Des outils combinatoires aux polynômes

La preuve relie des idées combinatoires à l’analyse des polynômes. Son outil central est celui des « lignes ». À chaque point du cube, une ligne associe un vecteur de poids non négatifs qui contrôle simultanément les variations de la fonction lorsque différents ensembles de coordonnées sont retournés. Pour une fonction booléenne, ces objets correspondent aux certificats fractionnaires, qui décrivent de manière pondérée les coordonnées nécessaires pour certifier une valeur.

Un théorème de bijection joue ensuite un rôle décisif. Les auteurs le démontrent en étudiant un déterminant dont les entrées sont des monômes. Cette analyse permet de contrôler deux aspects des bijections : les coordonnées qu’elles peuvent modifier et le nombre de fois où elles conservent chacune d’elles. Le résultat donne une inégalité portant sur les paires de points où la fonction prend des valeurs opposées, puis une version pondérée qui utilise les lignes.

Étendre l’argument aux fonctions réelles

Une difficulté est que les fonctions considérées ne sont pas nécessairement booléennes : elles peuvent prendre une gamme de valeurs réelles. Pour traiter ce cas, la preuve applique l’inégalité aux ensembles de niveau de la fonction, puis intègre sur les seuils. Ce passage des ensembles aux valeurs transforme les différences de la fonction en moments d’ordre trois et fait apparaître les incréments absolus moyens associés à chaque coordonnée.

Une inégalité sur ces moments, évaluée autour d’une médiane, montre que si le coût maximal des lignes est $K$, alors une coordonnée possède un incrément moyen d’au moins $\operatorname{Var}(f)^{3/2}/(6K^2)$. Enfin, une étape de moyennisation sur les coordonnées de faible influence préserve une fraction de la variance et permet de traduire cette estimation en une borne d’influence quadratique.

Ce que le résultat apporte

La preuve donne une réponse quantitative à une question fondamentale : une faible complexité polynomiale ne peut pas, à elle seule, empêcher une fonction d’être sensible à une variable particulière. En mettant au jour une telle variable, le résultat fournit aussi un lien concret entre l’analyse des polynômes booléens et la complexité des requêtes quantiques. Il précise ainsi les conditions dans lesquelles un avantage quantique général peut être limité, sans prétendre que les algorithmes quantiques sont toujours dépourvus d’avantage.

Créé le 09 Nov. 2026

Cette synthèse vous a-t-elle été utile ?

Note : 0

Posez des questions sur cet article à notre assistant IA

Comment discuter avec cet article ? Guide illustré

Comparer avec le PDF

Vous pouvez aussi discutez avec plusieurs papiers à la fois ici.

Instructions pour utiliser l'assistant IA ?

Outils pour cet article

Expliquer autrement 1 réécriture gratuite restante aujourd'hui

Enregistrer dans une collection Regroupez des articles en collections pour les comparer, les interroger et les exporter. Continuer avec Google Créer un compte gratuit Se connecter

Exporter BibTeX · RIS (Zotero, Mendeley, EndNote) · Obsidian (Markdown) · Notion (Markdown)

Outils avancés Premium

Pour suivre un domaine de près : alertes de citations, diapositives de journal club, comparaison des versions et envoi vers Zotero. Découvrir Premium

Zotero

Alertes de citation Guide des alertes de citations

Qui travaille dessus ? Les personnes et institutions qui publient sur son sujet

Lettre hebdomadaire Présenté dans « Informatique hors IA cette semaine » du 9 novembre 2026. Informatique hors IA cette semaine : des preuves aux épreuves du réel

Journal club Premium+ Des slides pour le présenter Proposer pour le journal club

Versions Ce qui a changé entre les versions

En parler en public Premium+ Kit presse : communiqué, questions, détecteur de hype Guide du kit presse

Les articles autour de celui-ci

Les voir sur une carte

Classés selon la proximité de leur titre et de leur résumé avec ceux de cet article. Sélectionnez-en pour les lire ensemble.

Les articles les plus proches

Proche Contexte plus large
An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphs
Matthew Kwan, Lisa Sauermann · 2019 · Combinatorics · cité 7 fois · Résumé IA disponible

« An algebraic inverse theorem for the quadratic Littlewood-Offord problem » caractérise la concentration de polynômes quadratiques, tandis que cet article établit une borne d’influence pour des polynômes bornés de faible degré.

Résumé scientifique
Consider a quadratic polynomial $f\left(\xi_{1},\dots,\xi_{n}\right)$ of independent Bernoulli random variables. What can be said about the concentration of $f$ on any single value? This generalises the classical Littlewood--Offord problem, which asks the same question for linear polynomials. As in the linear case, it is known that the point probabilities of $f$ can be as large as about $1/\sqrt{n}$, but still poorly understood is the "inverse" question of characterising the algebraic and arithmetic features $f$ must have if it has point probabilities comparable to this bound. In this paper we prove some results of an algebraic flavour, showing that if $f$ has point probabilities much larger…
Proche Contexte plus large
Anticoncentration in Ramsey graphs and a proof of the Erdős-McKay conjecture
Matthew Kwan, Ashwin Sah, Lisa Sauermann et al. · 2022 · Combinatorics · cité 12 fois · Résumé IA disponible

« Anticoncentration in Ramsey graphs » étudie les statistiques d’arêtes via les petites probabilités de polynômes de faible degré, plutôt que leurs influences.

Résumé scientifique
An $n$-vertex graph is called $C$-Ramsey if it has no clique or independent set of size $C\log_2 n$ (i.e., if it has near-optimal Ramsey behavior). In this paper, we study edge-statistics in Ramsey graphs, in particular obtaining very precise control of the distribution of the number of edges in a random vertex subset of a $C$-Ramsey graph. This brings together two ongoing lines of research: the study of "random-like" properties of Ramsey graphs and the study of small-ball probabilities for low-degree polynomials of independent random variables. The proof proceeds via an "additive structure" dichotomy on the degree sequence, and involves a wide range of different tools from Fourier analysis,…
Apparenté Contexte plus large
Optimizing QAOA: Success Probability and Runtime Dependence on Circuit Depth
Murphy Yuezhen Niu, Sirui Lu, Isaac L. Chuang · 2019 · Quantum Physics · preprint, non relu par les pairs · cité 48 fois · Pas encore résumé

« Optimizing QAOA » analyse la probabilité de transfert d’état selon la profondeur d’un circuit, sans étudier les influences des polynômes sur le cube.

Résumé scientifique
The quantum approximate optimization algorithm~(QAOA) first proposed by Farhi et al. promises near-term applications based on its simplicity, universality, and provable optimality. A depth-p QAOA consists of p interleaved unitary transformations induced by two mutually non-commuting Hamiltonians. A long-standing question concerning the performance of QAOA is the dependence of its success probability as a function of circuit depth p. We make initial progress by analyzing the success probability of QAOA for realizing state transfer in a one-dimensional qubit chain using two-qubit XY Hamiltonians and single-qubit Hamiltonians. We provide analytic state transfer success probability dependencies …
Apparenté Contexte plus large
Quantum query complexity of edge connectivity
Simon Apers, Troy Lee · 2020 · Quantum Physics · cité 11 fois · Résumé IA disponible

« Quantum query complexity of edge connectivity » établit des bornes de requêtes quantiques pour un problème de graphes, tandis que cet article relie les influences à la simulation classique.

Résumé scientifique
The edge connectivity of a simple graph is the least number of edges whose removal disconnects the graph. We study the quantum query complexity of computing the edge connectivity of a simple graph with $n$ vertices and $m$ edges in both the adjacency matrix and adjacency array models. For classical randomized algorithms, $\Omega(n^2)$ and $\Omega(m)$ lower bounds are known for these models, respectively, showing that the trivial algorithm is optimal in terms of query complexity for both cases. In contrast, we show upper bounds of $\tilde O(n^{3/2})$ and $\tilde O(\sqrt{mn})$ on the quantum query complexity of computing edge connectivity in the adjacency matrix and adjacency array models, res…
Apparenté Contexte plus large
Are Quantum States Exponentially Long Vectors?
Scott Aaronson · 2005 · Quantum Physics · preprint, non relu par les pairs · cité 11 fois · Résumé IA disponible

« Are Quantum States Exponentially Long Vectors? » discute de l’informatique quantique, mais ne traite ni des requêtes quantiques ni des influences polynomiales.

Résumé scientifique
I'm grateful to Oded Goldreich for inviting me to the 2005 Oberwolfach Meeting on Complexity Theory. In this extended abstract, which is based on a talk that I gave there, I demonstrate that gratitude by explaining why Goldreich's views about quantum computing are wrong.
Apparenté Contexte plus large
A doubly composite Chernoff-Stein lemma and its applications
Ludovico Lami · 2025 · Information Theory · preprint, non relu par les pairs · cité 6 fois · Pas encore résumé

« A doubly composite Chernoff-Stein lemma » étudie la discrimination statistique de distributions corrélées, sans lien direct avec les influences de polynômes.

Résumé scientifique
Given a sequence of random variables $X^n=X_1,\ldots, X_n$, discriminating between two hypotheses on the underlying probability distribution is a key task in statistics and information theory. Of interest here is the Stein exponent, i.e. the largest rate of decay (in $n$) of the type II error probability for a vanishingly small type I error probability. When the hypotheses are simple and i.i.d., the Chernoff-Stein lemma states that this is given by the relative entropy between the single-copy probability distributions. Generalisations of this result exist in the case of composite hypotheses, but mostly to settings where the probability distribution of $X^n$ is not genuinely correlated, but r…
Apparenté Contexte plus large
On Zeros and Algorithms for Disordered Systems II: The Antiferromagnetic Ising Model up to Kesten-Stigum
Ferenc Bencs, Brice Huang, Daniel Z. Lee et al. · 2026 · Data Structures and Algorithms · Résumé IA disponible

« On Zeros and Algorithms for Disordered Systems II » conçoit un algorithme pour la fonction de partition d’un modèle d’Ising, plutôt que pour simuler des requêtes quantiques.

En bref
L’article établit un comptage approché polynomial pour l’Ising antiferromagnétique sur graphes réguliers aléatoires, à toute température inverse strictement inférieure au seuil de Kesten–Stigum.
Apparenté Contexte plus large
Adversarial Wronskians: A proof of the Kung--Traub conjecture
Matthew J. Colbrook · 2026 · Numerical Analysis · Résumé IA disponible

« Adversarial Wronskians » prouve une conjecture sur l’ordre des méthodes de recherche de racines, en utilisant des polynômes de Wronskiens plutôt que des influences.

En bref
L’article prouve que l’ordre local universel d’une méthode déterministe sans mémoire utilisant au plus n évaluations scalaires est borné par 2^(n−1), borne atteinte pour n ≥ 2.

Aller plus loin

Comment ces articles sont-ils trouvés ?

Nous comparons le titre et le résumé de cet article avec ceux de tous les articles résumés sur ce site, et avec les articles que Semantic Scholar recommande, ceux qu’il cite et ceux qui le citent (pour un article très cité, ses citations les plus récentes et, depuis OpenAlex, les plus citées). Parmi les travaux antérieurs et les suites, les articles qui s’utilisent en profondeur, une méthode qu’il utilise et les suites très citées remontent un peu. Les niveaux (très proche, proche, apparenté) viennent de la similarité des textes, pas d’un jugement de qualité ; * signale un article sans résumé, comparé par son titre. La phrase sous un article est écrite par une IA à partir des deux résumés : vérifiez-la dans les articles. Un article jugé hors sujet par trois lecteurs quitte la liste.

Mis à jour le 9 novembre 2026.

Avertissement : Notre outil de synthèse basé sur l'IA et l'assistant virtuel fournis sur ce site Web peuvent ne pas toujours fournir des résumés complets ou des réponses exactes. Nous vous encourageons à examiner attentivement et à évaluer le contenu généré pour vous assurer de sa qualité et de sa pertinence par rapport à vos besoins.

A proof of the Aaronson-Ambainis conjecture

L’essentiel

Question

Méthode

Résultats

Limites

Portée

Pour aller plus loin

Definitions

Une preuve quantitative de la conjecture d’Aaronson–Ambainis

La conjecture et son importance

Une borne explicite sur l’influence

Des outils combinatoires aux polynômes

Étendre l’argument aux fonctions réelles

Ce que le résultat apporte

Posez des questions sur cet article à notre assistant IA

Outils pour cet article

Outils avancés Premium

Les articles autour de celui-ci

Les articles les plus proches

Aller plus loin

Citer cet article (BibTeX)