Physics – Quantum Physics
Scientific paper
2003-08-23
Physics
Quantum Physics
The original abstract appeared in the Proceedings of the 2nd IFIP International Conference on Theoretical Computer Science (Fo
Scientific paper
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.
No associations
LandOfFree
Quantum NP and a Quantum Hierarchy does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Quantum NP and a Quantum Hierarchy, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum NP and a Quantum Hierarchy will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-17380