BQP $\neq$ QMA

ePrint Report: BQP $\neq$ QMA

Ping Wang, Yiting Su

The relationship between complexity classes BQP and QMA is analogous to the relationship between P and NP. In this paper, we design a quantum bit commitment problem that is in QMA, but not in BQP. Therefore, it is proved that BQP $\neq$ QMA. That is, problems that are verifiable in quantum polynomial time are not necessarily solvable in quantum polynomial time, the quantum analog of P $\neq$ NP.

complexity design eprint report ping problem problems quantum relationship report