aiqbenchInformații despre AI & calcul cuantic

...

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

perspectiva aiqbenchCalcul cuantic

This paper establishes a near-quartic separation between quantum query complexity and certificate complexity by constructing a specific total Boolean function, resolving a long-standing theoretical question in the field. The result is tight up to logarithmic factors, providing crucial new bounds for understanding the fundamental limits of quantum algorithms on boolean functions. This advancement deepens our theoretical grasp of quantum advantage within the query model without relying on hardware-specific claims.

Sursă care acoperăarXiv

Ce este aceastaLectura unui model asupra articolului și a acoperirii conexe, scrisă pentru aiqbench. Nu sunt cuvintele publicației.

A Near-Quartic Separation Between Certificate Complexity and Quantum Query Complexity

arXiv11 septembrie 20261 min de cititArticolul și perspectiva sunt în engleză.

arXiv:2609.11664v1 Announce Type: new Abstract: We construct a total Boolean function $f$ for which $Q(f) = \widetilde{O}(\sqrt[4]{C(f)})$, where $Q(f)$ denotes the bounded-error quantum query complexity and $C(f)$ denotes the certificate complexity. This resolves a longstanding open question and is tight up to logarithmic factors.

Abstract:We construct a total Boolean function $f$ for which $Q(f) = \widetilde{O}(\sqrt[4]{C(f)})$, where $Q(f)$ denotes the bounded-error quantum query complexity and $C(f)$ denotes the certificate complexity. This resolves a longstanding open question and is tight up to logarithmic factors.

arXiv:2609.11664 [quant-ph]

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

https://doi.org/10.48550/arXiv.2609.11664 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 · 130 cuvinte

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