1
$\begingroup$

There are several quantum complexity classes in different ways analogous to NP: NQP, QMA, and, as I understand, others.

P=NP BPP=NP in simple words means "any cipher can be deciphered by a classical computer". (Do I understand it correctly?)

So, what is the "formula" for "any cipher can be deciphered by a quantum computer"?

$\endgroup$

1 Answer 1

1
$\begingroup$

In general, if NP turns out to be the subset of any tractable class then that will be a black swan event for those who depend on cryptography as it exists today. $NP \subseteq BQP$ is one such example. But it need not be a fatal blow to use of cryptography. Quantum computers with a large number of qubits have yet to be built, and it is unknown whether they can be. So increasing key lengths may well put tractable decryption out of reach of the machines that can be built. And of course the polynomial exponent might turn out to be large enough to make polynomial-time "efficient" decryption infeasible in practice. E.g. an $O(n^{13})$ algorithm for SAT, while a beautiful thing to behold, probably isn't going to break use of cryptography.

$\endgroup$
3
  • $\begingroup$ Why do you show me two formulas instead of one? Do you imply that neither $BQP\subseteq QMA$ nor $QMA\subseteq BQP$ is know? $\endgroup$
    – porton
    Mar 4, 2021 at 22:48
  • $\begingroup$ No, I'm just trying to answer the question you asked, as I understood it. How BQP and QMA are related is a different question. $\endgroup$
    – Kyle Jones
    Mar 5, 2021 at 0:12
  • $\begingroup$ If it is known that $BQP\subseteq QMA$ or $QMA\subseteq BQP$, then it makes no sense to choose between $NP\subseteq BQP$ and $NP\subseteq QMA$ because one of these two formulas would be a consequence of another. But you put two inequalities. Is one these two inequalities stronger? $\endgroup$
    – porton
    Mar 5, 2021 at 7:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.