Sari la conținut
aiqbenchInformații despre AI & calcul cuantic
ȘtiriAnalizeBenchmark-uriSkill-uriÎntreabă AIÎnvațăDespre
...Se încarcă sesiunea
ȘtiriAnalizeBenchmark-uriSkill-uriÎntreabă AIÎnvațăDespre

Română · beta. Traducerea a fost făcută automat și este încă în curs de revizuire. Citește pagina în engleză

Înapoi la listă
perspectiva aiqbenchCalcul cuantic

analiza aiqbench

This exposition details a significant breakthrough in computational complexity theory, proving the Aaronson-Ambainis conjecture via a proof discovered with the assistance of an advanced AI system. The result establishes that quantum query algorithms for decision problems can be efficiently simulated classically on most inputs, effectively narrowing the gap between classical and quantum capabilities in specific contexts.
1
Sursă care acoperăarXiv

Proof of the Aaronson-Ambainis Conjecture: An Exposition

arXiv·10 noiembrie 2026·2 min de citit·Articolul și perspectiva sunt în engleză.

De la arXiv

Text integral

arXiv:2611.11626v1 Announce Type: new Abstract: We give an exposition of a recent proof of the Aaronson-Ambainis conjecture, which states that every degree-$d$ polynomial $p : \{0,1\}^n \to [0,1]$ has a variable of influence at least $\mathrm{poly}(\mathrm{Var}(p)/d)$. This implies that quantum query algorithms for decision problems can be efficiently simulated classically on most inputs. It also yields a near-equivalence between the status of the $\mathsf{BPP}$ vs. $\mathsf{BQP}$ problem in the random oracle and unrelativized worlds.

We organize the proof around four main steps and discuss how each connects to the literature on the analysis of boolean functions and probabilistic combinatorics. To bring out the key ideas, we do not optimize parameters, and our presentation yields weaker exponents than the original. $\textbf{Authors' note.}$ The proof was discovered by David Turturean using a research system developed at Physical Superintelligence (PSI), in combination with a non-public Anthropic model.

The proof was then shared with the authors, who worked to understand it and prepare this exposition. Anthropic's public models were used in this process. The authors did not receive financial compensation from Anthropic or PSI. This article is not intended for publication at a conference or in a journal.

Abstract:We give an exposition of a recent proof of the Aaronson-Ambainis conjecture, which states that every degree-$d$ polynomial $p : \{0,1\}^n \to [0,1]$ has a variable of influence at least $\mathrm{poly}(\mathrm{Var}(p)/d)$. This implies that quantum query algorithms for decision problems can be efficiently simulated classically on most inputs. It also yields a near-equivalence between the status of the $\mathsf{BPP}$ vs. $\mathsf{BQP}$ problem in the random oracle and unrelativized worlds. We organize the proof around four main steps and discuss how each connects to the literature on the analysis of boolean functions and probabilistic combinatorics.

To bring out the key ideas, we do not optimize parameters, and our presentation yields weaker exponents than the original. $\textbf{Authors' note.}$ The proof was discovered by David Turturean using a research system developed at Physical Superintelligence (PSI), in combination with a non-public Anthropic model. The proof was then shared with the authors, who worked to understand it and prepare this exposition. Anthropic's public models were used in this process. The authors did not receive financial compensation from Anthropic or PSI. This article is not intended for publication at a conference or in a journal.

Quantum Physics (quant-ph); Computational Complexity (cs.CC)

arXiv:2611.11626 [quant-ph]

(or arXiv:2611.11626v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2611.11626 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

Text integral sub licența deschisă a publicației · 286 cuvinte

Citește pe arXiv ↗Întreabă despre acest articol

Article info

Source

arXiv

Published

10 noiembrie 2026

Read time

2 min

Category

Calcul cuantic
aiqbench
Informații despre AI & calcul cuantic© aiqbench. Toate drepturile rezervate.

Fluxuri:RSS·JSON Feed

LimbăEnglish·Românăbeta
ȘtiriAI & tehnologieCuanticAnalize
ExploreazăBenchmark-uriÎnvață
CompanieDespreÎncredereInformații legaleTermeni și condițiiPolitica de confidențialitateNotificări privind drepturile de autorȘtergerea datelorRaportează conținut

Perspectiva aiqbench, analizele, rezumatul zilnic și răspunsurile din Întreabă sunt scrise de modele AI din sursele afișate, fără revizuire editorială înainte de publicare. Pot conține erori — verifică sursa. Cum este folosit modelul →

  • Știri
  • Analize
  • Întreabă
  • Topuri
  • Cont