3
$\begingroup$

Here's a "proof" for why $BPP\subset BQP$ assuming Learning With Errors (LWE) is postquantum.

Consider the Mahadev protocol that uses LWE-based cryptography to verify if an instance $x\in L$ for a language $L\in BQP$. My understanding is that if the prover was classical, then they cannot pass the tests described in the protocol without breaking the LWE-based cryptography. This is because a classical computer can be rewound and that allows one to extract the claw of a trapdoor claw-free function without knowing the trapdoor.

The conclusion is that one of the following possibilities is true:

  1. The classical computer can break LWE.
  2. The classical computer cannot provide a proof that $x\in L$ for $L\in BQP$.

Assuming LWE is postquantum, is it then proved that $BPP\subset BQP$? Or is there a more subtle issue here?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

No.

To say that LWE is a post-quantum cryptographic protocol implies that LWE splits NP from BQP, not that it splits BPP from BQP. We think LWE is in NP\BQP, and not that it is in BQP\BPP. It needs to be in NP in order to efficiently and classically verify the witness (which is easy if the trapdoor is known), while it is not thought to be in BQP (lest a quantum computer could cheat Mahadev's protocol).

Similarly, we believe by hypothesis that RSA is classically secure, which entails that RSA (and factoring) splits BPP from NP. We think RSA is in NP\BPP. A decision version of RSA is in NP (and is efficient if the private key is known), but by assumption is not in BPP (otherwise it can be efficiently cracked).

That is, LWE is to the relationship between BQP and NP as RSA is to the relationship between BPP and NP. This is why NIST is looking at LWE as a post-quantum replacement for RSA.

I think you're mixing two sides to the Venn-diagram between NP and BQP. A post-quantum scheme is a problem that's in NP but not in BQP, while a BQP-complete problem is in BQP but likely not in NP. Mahadev provides an interactive proof for the latter by using binding properties of the former.

It's kind of circular to say that Mahadev's protocol, which uses a post-quantum cryptographic scheme to convince a classically-bounded verifier that some language is in BQP, implies that a classical computer cannot prove that the language is in BQP.

If BQP$\subseteq$NP then Mahadev's protocol wouldn't be needed, as she could just give the classical NP-witness for any problem in BQP. If NP$\subseteq$BQP then no post-quantum protocol, would exist!

Improve this answer
$\endgroup$
4
  • $\begingroup$ Yes, but then why is conclusion 2 from the question not true? I claim that if 1 holds, no classical machine can pass the Mahadev test to show $x\in L$ for some $L$ that is in BQP $\endgroup$
    – user1936752
    Commented Feb 3 at 10:19
  • $\begingroup$ The conclusion (modulo some fine points) is true, it just doesn't follow from the post-quantumness of LWE. $\endgroup$
    – Mark Spinelli
    Commented Feb 3 at 14:03
  • $\begingroup$ Thanks for the edited answer - however, I'm a bit confused about why the conclusion being true doesn't imply that $BPP$ is a proper subset of $BQP$. Can I check: If every classical polynomial-time algorithm fails the Mahadev protocol to prove either $x\in L$ or $x\not\in L$, is this not sufficient to claim that $L\not\in BPP$? $\endgroup$
    – user1936752
    Commented Feb 3 at 15:52
  • $\begingroup$ I don't quite understand the way you phrased it. But we know that P$\subseteq$NP and we strongly suspect that P=BPP. Mahadev's protocol provides an interactive proof for languages in BQP\NP. Such a language necessarily would also be in BQP\P which we also think is the same as BQP\BPP - that is, in BQP, but not in P or BPP. $\endgroup$
    – Mark Spinelli
    Commented Feb 3 at 20:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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