arXiv (Cornell University) · 2007 · 10 citations · 0 references
Open access
ComputingComputer ScienceMathematicsQuantum ComputingQuantum MechanicsTheory Of ComputationComputational ComplexityProof ComplexityQuantum CommunicationQuantum Complexity TheoryQuantum ComputationQuantum Information TheoryQuantum ComplexityQuantum Complexity ClassesQuantum Proof Verification
In this note we show that all languages in NP have very short (logarithmic size) quantum proofs which can be verified provided that two unentangled copies are given. We thus introduce a new complexity class QMAlog(2) and show that NP ⊆ QMAlog(2). This gives a new perspective when compared to the previously known result QMAlog = BQP. 1