# What is the "formula" for "any cipher can be deciphered by a quantum computer"?

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"?

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.
• Why do you show me two formulas instead of one? Do you imply that neither $BQP\subseteq QMA$ nor $QMA\subseteq BQP$ is know? Mar 4, 2021 at 22:48
• 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? Mar 5, 2021 at 7:13