BQP $\neq$ QMA

Ping Wang; Yiting Su

Paper 2023/703 Original: eprint.iacr.org/2023/703 ↗

BQP $\neq$ QMA

Ping Wang

Yiting Su

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.
History: 2023-05-17: last updated; 2023-05-17: published
Short URL: https://ia.cr/2023/703
License: https://creativecommons.org/licenses/by-nc-nd/4.0/

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}
}