Quantum NP and a Quantum Hierarchy
<|reference_start|>Quantum NP and a Quantum Hierarchy: The complexity class NP is quintessential and ubiquitous in theoretical computer science. Two different approaches have been made to define "Quantum NP," the quantum analogue of NP: NQP by Adleman, DeMarrais, and Huang, and QMA by Knill, Kitaev, and Watrous. From an operator point of view, NP can be viewed as the result of the exists-operator applied to P. Recently, Green, Homer, Moore, and Pollett proposed its quantum version, called the N-operator, which is an abstraction of NQP. This paper introduces the exists^{Q}-operator, which is an abstraction of QMA, and its complement, the forall^{Q}-operator. These operators not only define Quantum NP but also build a quantum hierarchy, similar to the Meyer-Stockmeyer polynomial hierarchy, based on two-sided bounded-error quantum computation.<|reference_end|>
@article{yamakami2003quantum,
    title={Quantum NP and a Quantum Hierarchy},
    author={Tomoyuki Yamakami},
    journal={arXiv preprint arXiv:quant-ph/0308125},
    year={2003},
    archivePrefix={arXiv},
    eprint={quant-ph/0308125},
    primaryClass={quant-ph cs.CC}
}