essentially a dupe of <a href="https://news.ycombinator.com/item?id=18167690" rel="nofollow">https://news.ycombinator.com/item?id=18167690</a>
Mahadev's result is excellent by any standard and remarkable for a graduate student. It's both impressively creative and technically novel. But quantum verification has not been solved, and the headline is wrong.<p>In essence, Mahadev developed a quantum verification protocol that relies on a post-quantum secure cryptosystem. She used an encryption scheme based on the the Learning With Errors (LWE) problem, which is one of the foremost intractability assumptions in post-quantum cryptography research. It's a great idea and a novel approach based on the marriage of two related fields of research.<p>But the jury is still out on whether or not the LWE is actually post-quantum secure (likewise with other intractability assumptions). It <i>probably</i> is, but there are reasonable and credible arguments against lattice-based problems generally and the LWE family of problems in particular (which is one reason proposals based on isogenies, error correcting codes, hash-based signatures and multivariate polynomials are also under active research).<p>Mahadev's real achievement is not solving quantum verification - but it's possible this will lead to that result. Rather as a direct result of her work we can now conclude one of the following must be true:<p>1. the LWE problem is <i>not</i> post-quantum secure, or<p>2. we can verify quantum computation.<p>That's a win-win for both the quantum computing and theoretical cryptography research communities.<p>I have suggested elsewhere that a logical next step in this research is to take Mahadev's framework and "port" it to another theorized post-quantum secure intractability assumption. My reading of Mahadev's paper is that her methodology is probably modular enough to support swapping out the LWE with any other family of post-quantum secure assumptions, not just lattice-based ones. She does highlight a few parameter choices taken from one of Gentry's lattice schemes for fully homomorphic encryption (FHE), but I don't think that should pose a significant obstacle to changing the intractability protocol.<p>This would be very interesting because it might result in nontrivial changes to the speed or efficiency of the quantum verification system. Post-quantum cryptographic systems have different trade-offs depending on their underlying intractability assumptions; I'm interested in whether and how that would surface in quantum verification as well. Another very interesting route for further research is seeing where else cryptographic protocols can be used for creatively solving open problems in verification more generally. But that's already an active area of investigation.
I sincerely believe we should treat quantum computing discoveries as (long term) major 0-days, as in they should sent in confidentiality to sensitive sectors's actors, those that depend heavily on classic encryption.
The lack of inspectability, it seems to me, would make quantum computing flat-out unacceptable in a variety of problem domains, including pretty much any decision support system. Not theoretically, so much as socially. In the way nuclear reactors are unacceptably risky to many who accept a far higher death toll associated with roofers falling to their deaths installing solar. Sure nuclear saves lives, but my aunt doesn't understand it and she finds it scary.