1101.5227 (Abuzer Yakaryilmaz et al.)

NP has log-space verifiers with fixed-size public quantum registers    [PDF]

Abuzer Yakaryilmaz, A. C. Cem Say

In classical Arthur-Merlin games, the class of languages whose membership proofs can be verified by Arthur using logarithmic space (AM(log-space)) coincides with the class P \cite{Co89}. In this note, we show that if Arthur has a fixed-size quantum register (the size of the register does not depend on the length of the input) instead of another source of random bits, membership in any language in NP can be verified with any desired error bound.

View original: http://arxiv.org/abs/1101.5227