A proof of the Aaronson-Ambainis conjecture
Auteurs : David Turturean
Résumé scientifique
Aaronson and Ambainis conjectured that every bounded polynomial of low degree on the discrete cube has an influential variable. They showed that the conjecture implies that the acceptance probability of every quantum algorithm making $T$ queries can be approximated on most inputs by a classical algorithm making $\mathrm{poly}(T)$ queries. We prove their conjecture: every function $f\colon\{-1,1\}^n\to[-1,1]$ of degree at most $d\ge1$ has a variable of influence at least $c\,\operatorname{Var}(f)^{5/2}/d^{6}$, where $c>0$ is an absolute constant. In the original formulation, for polynomials of degree at most $d$ with values in $[0,1]$ on $\{0,1\}^n$ and variance at least $\varepsilon$, this gives a variable of influence at least $(\varepsilon/d)^{7}$. The proof is elementary, with steps inspired by works of others. Thus, as Aaronson and Ambainis anticipated, superpolynomial quantum speedups in the query model require structure, such as a promise on the inputs.
Les articles autour de lui, par date et par proximité
Plus haut, c’est plus proche de cet article ; à gauche, c’est plus ancien. Les traits relient les articles proches entre eux : les groupes de traits sont des sous-thèmes. Sélectionnez un point pour voir pourquoi il est là. Retour au résumé de cet article
Les articles autour de celui-ci
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
-
An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphsMatthew 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…
-
Anticoncentration in Ramsey graphs and a proof of the Erdős-McKay conjectureMatthew 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,…
-
Optimizing QAOA: Success Probability and Runtime Dependence on Circuit DepthMurphy 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 …
-
Quantum query complexity of edge connectivitySimon 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…
-
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.
-
A doubly composite Chernoff-Stein lemma and its applicationsLudovico 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…
-
On Zeros and Algorithms for Disordered Systems II: The Antiferromagnetic Ising Model up to Kesten-StigumFerenc 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.
-
Adversarial Wronskians: A proof of the Kung--Traub conjectureMatthew 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.