Quantum query complexity for qutrits
Boaz Tamir · Physical Review A · 2008
We compute lower bounds for the exact quantum query complexity of a ternary function $f$. The lower bound is of order $O\mathbf{(}{\text{log}}_{3}(n)\mathbf{)}$. In case $f$ is symmetric on a sphere then the lower bound is of order $O(\sqrt{n})$. This work is a natural continuation of the work of Beals, Buhrman, Cleve, Mosca, and de Wolf on lower limits for binary functions.