Succinct arguments for QMA from standard assumptions via compiled nonlocal games

• URL: http://arxiv.org/abs/2404.19754v1
• Date: Tue, 30 Apr 2024 17:58:06 GMT
• Title: Succinct arguments for QMA from standard assumptions via compiled nonlocal games
• Authors: Tony Metger, Anand Natarajan, Tina Zhang,
• Abstract summary: We construct a succinct classical argument system for QMA from generic and standard cryptographic assumptions. Our main technical contribution is to analyze the soundness of this transformation when it is applied to a succinct self-test for Pauli measurements.
• Score: 1.6124402884077915
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• On fault tolerant single-shot logical state preparation and robust long-range entanglement [1.3408612567129143]
  We prove that single-shot logical state preparation can be achieved for arbitrary quantum LDPC codes. We also prove single-shot preparation of the encoded GHZ state in arbitrary quantum LDPC codes.
  arXiv  Detail & Related papers  (2024-11-07T03:51:05Z)
• Classical Commitments to Quantum States [5.6739502570965765]
  We define the notion of a classical commitment scheme to quantum states. It allows a quantum prover to compute a classical commitment to a quantum state, and later open each qubit of the state in either the standard or the Hadamard basis.
  arXiv  Detail & Related papers  (2024-04-19T22:31:18Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• Encryption with Quantum Public Keys [1.7725414095035827]
  We study the question of building quantum public-key encryption schemes from one-way functions and even weaker assumptions. We propose three schemes for quantum public-key encryption from one-way functions, pseudorandom function-like states with proof of deletion and pseudorandom function-like states, respectively.
  arXiv  Detail & Related papers  (2023-03-09T16:17:19Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical. We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more. Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
  arXiv  Detail & Related papers  (2023-03-02T14:18:17Z)
• A Simple Construction of Quantum Public-Key Encryption from Quantum-Secure One-Way Functions [13.677574076242188]
  We show that quantum PKE can be constructed from any quantum-secure one-way function. Our construction is simple, uses only classical ciphertexts, and satisfies the strong notion of CCA security.
  arXiv  Detail & Related papers  (2023-03-02T10:45:16Z)
• Succinct Classical Verification of Quantum Computation [30.91621630752802]
  We construct a classically succinct interactive argument for quantum computation (BQP) Our protocol is secure assuming the post-quantum security of indistinguishability obfuscation (iO) and Learning Errors (LWE)
  arXiv  Detail & Related papers  (2022-06-29T22:19:12Z)
• A Variational Quantum Attack for AES-like Symmetric Cryptography [69.80357450216633]
  We propose a variational quantum attack algorithm (VQAA) for classical AES-like symmetric cryptography. In the VQAA, the known ciphertext is encoded as the ground state of a Hamiltonian that is constructed through a regular graph.
  arXiv  Detail & Related papers  (2022-05-07T03:15:15Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)
• Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
  We consider the setting where the two parties (a classical Alice and a quantum Bob) can communicate only via a classical channel. We show that it is in general impossible to realize a two-party quantum functionality with black-box simulation in the case of malicious quantum adversaries. We provide a compiler that takes as input a classical proof of quantum knowledge (PoQK) protocol for a QMA relation R and outputs a zero-knowledge PoQK for R that can be verified by classical parties.
  arXiv  Detail & Related papers  (2020-10-15T17:55:31Z)
• Using Quantum Metrological Bounds in Quantum Error Correction: A Simple Proof of the Approximate Eastin-Knill Theorem [77.34726150561087]
  We present a proof of the approximate Eastin-Knill theorem, which connects the quality of a quantum error-correcting code with its ability to achieve a universal set of logical gates. Our derivation employs powerful bounds on the quantum Fisher information in generic quantum metrological protocols.
  arXiv  Detail & Related papers  (2020-04-24T17:58:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.