Quantum query complexity for qutrits
We compute lower bounds for the exact quantum query complexity of a ternary function f. The lower bound is of order O(log{sub 3}(n)). In case f is symmetric on a sphere then the lower bound is of order O({radical}(n)). This work is a natural continuation of the work of Beals, Buhrman, Cleve, Mosca, and de Wolf on lower limits for binary functions.
71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗