6533b835fe1ef96bd129f6f4

RESEARCH PRODUCT

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

Abuzer YakaryilmazA. C. Cem Say

subject

FOS: Computer and information sciencesComputer Science - Computational ComplexityQuantum PhysicsTheoryofComputation_COMPUTATIONBYABSTRACTDEVICESFOS: Physical sciencesComputational Complexity (cs.CC)Computer Science::Computational ComplexityQuantum Physics (quant-ph)

description

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.

yearjournalcountryeditionlanguage
2011-01-27
http://arxiv.org/abs/1101.5227