Running summarizing tools on a new article

Check the paper below, then start its synthesis.


Quantum query complexity for qutrits

Boaz Tamir (Bar-Ilan University)

Physical Review A
License: not stated (all rights reserved)

Abstract: 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.

Published on 28 Feb. 2008