Quantum function computation using sublogarithmic space (abstract & poster)

Abstract

We prove that quantum Turing machines are strictly superior to probabilistic Turing machines in function computation for any space bound $o(\log (n))$.

2 pages, poster presented at the 13th Workshop on Quantum Information Processing (QIP2010)