BQP $\neq$ QMA

Ping Wang; Yiting Su

Paper 2023/703

BQP $\neq$ QMA

Ping Wang

, Shenzhen University

Yiting Su, Shenzhen University

Abstract

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.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
Keywords: BQP QMA complexity theory quantum complexity theory
Contact author(s): wangping @ szu edu cn
suyiting2020 @ email szu edu cn
History: 2023-05-22: approved; 2023-05-17: received; See all versions
Short URL: https://ia.cr/2023/703
License: CC BY-NC-ND

BibTeX

@misc{cryptoeprint:2023/703,
      author = {Ping Wang and Yiting Su},
      title = {BQP $\neq$ QMA},
      howpublished = {Cryptology ePrint Archive, Paper 2023/703},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/703}},
      url = {https://eprint.iacr.org/2023/703}
}