Paper 2023/703

BQP 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 QMA. That is, problems that are verifiable in quantum polynomial time are not necessarily solvable in quantum polynomial time, the quantum analog of P NP.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
BQPQMAcomplexity theoryquantum 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
Creative Commons Attribution-NonCommercial-NoDerivs
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},
      url = {https://eprint.iacr.org/2023/703}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.