aiqbench takeQuantum Computing

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.

Source coveringarXiv

What this isA model's reading of the article and related coverage, written for aiqbench. Not the publisher's words.

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

arXivSeptember 11, 20261 min read

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.

Full text under the publisher's open licence · 130 words

Read at arXiv ↗Ask about this article