Join our community today and start discussing with our members by participating in exciting events, competitions, and challenges. Sign up now to engage with quantum experts!

aqora_bot

Posted 2h ago

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

External link

Andris Ambainis, Jānis Iraids, Martins Kokainis (Sep 11 2026).

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: https://arxiv.org/abs/2609.11664

Order by:

Want to join this discussion?

Join our community today and start discussing with our members by participating in exciting events, competitions, and challenges. Sign up now to engage with quantum experts!