Succinct arguments for QMA from standard assumptions via compiled nonlocal games

April 30, 2024 Β· Declared Dead Β· πŸ› IEEE Annual Symposium on Foundations of Computer Science

πŸ‘» CAUSE OF DEATH: Ghosted
No code link whatsoever

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Tony Metger, Anand Natarajan, Tina Zhang arXiv ID 2404.19754 Category quant-ph: Quantum Computing Cross-listed cs.CR Citations 7 Venue IEEE Annual Symposium on Foundations of Computer Science Last Checked 5 months ago
Abstract
We construct a succinct classical argument system for QMA, the quantum analogue of NP, from generic and standard cryptographic assumptions. Previously, building on the prior work of Mahadev (FOCS '18), Bartusek et al. (CRYPTO '22) also constructed a succinct classical argument system for QMA. However, their construction relied on post-quantumly secure indistinguishability obfuscation, a very strong primitive which is not known from standard cryptographic assumptions. In contrast, the primitives we use (namely, collapsing hash functions and a mild version of quantum homomorphic encryption) are much weaker and are implied by standard assumptions such as LWE. Our protocol is constructed using a general transformation which was designed by Kalai et al. (STOC '23) as a candidate method to compile any quantum nonlocal game into an argument system. Our main technical contribution is to analyze the soundness of this transformation when it is applied to a succinct self-test for Pauli measurements on maximally entangled states, the latter of which is a key component in the proof of MIP*=RE in quantum complexity.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

πŸ“œ Similar Papers

In the same crypt β€” Quantum Computing

Died the same way β€” πŸ‘» Ghosted