Classically Verifiable NIZK for QMA with Preprocessing

• URL: http://arxiv.org/abs/2102.09149v4
• Date: Tue, 15 Nov 2022 04:15:28 GMT
• Title: Classically Verifiable NIZK for QMA with Preprocessing
• Authors: Tomoyuki Morimae and Takashi Yamakawa
• Abstract summary: We propose three constructions of classically verifiable non-interactive zero-knowledge proofs and arguments (CV-NIZK) for QMA in various preprocessing models. We construct a CV-NIZK for QMA in a model where a trusted party generates a CRS and the verifier sends an instance-independent quantum message to the prover as preprocessing. This answers an open problem left by Coladangelo et al, which is to achieve either of soundness or zero-knowledge information theoretically.
• Score: 9.767030279324038
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose three constructions of classically verifiable non-interactive zero-knowledge proofs and arguments (CV-NIZK) for QMA in various preprocessing models. - We construct a CV-NIZK for QMA in the quantum secret parameter model where a trusted setup sends a quantum proving key to the prover and a classical verification key to the verifier. It is information theoretically sound and zero-knowledge. - Assuming the quantum hardness of the learning with errors problem, we construct a CV-NIZK for QMA in a model where a trusted party generates a CRS and the verifier sends an instance-independent quantum message to the prover as preprocessing. This model is the same as one considered in the recent work by Coladangelo, Vidick, and Zhang (CRYPTO '20). Our construction has the so-called dual-mode property, which means that there are two computationally indistinguishable modes of generating CRS, and we have information theoretical soundness in one mode and information theoretical zero-knowledge property in the other. This answers an open problem left by Coladangelo et al, which is to achieve either of soundness or zero-knowledge information theoretically. To the best of our knowledge, ours is the first dual-mode NIZK for QMA in any kind of model. - We construct a CV-NIZK for QMA with quantum preprocessing in the quantum random oracle model. This quantum preprocessing is the one where the verifier sends a random Pauli-basis states to the prover. Our construction uses the Fiat-Shamir transformation. The quantum preprocessing can be replaced with the setup that distributes Bell pairs among the prover and the verifier, and therefore we solve the open problem by Broadbent and Grilo (FOCS '20) about the possibility of NIZK for QMA in the shared Bell pair model via the Fiat-Shamir transformation.

Related papers

• Learning hard distributions with quantum-enhanced Variational Autoencoders [2.545905720487589]
  We introduce a quantum-enhanced VAE (QeVAE) that uses quantum correlations to improve the fidelity over classical VAEs. We empirically show that the QeVAE outperforms classical models on several classes of quantum states. Our work paves the way for new applications of quantum generative learning algorithms.
  arXiv  Detail & Related papers  (2023-05-02T16:50:24Z)
• Quantum delegation with an off-the-shelf device [3.3766484312332303]
  We show how to delegate-time quantum computations in the OTS model. This provides the first relativistic (one-round), two-prover zero-knowledge proof system for QMA. As a proof approach, we provide a new self-test for n EPR pairs using only constant-sized Pauli measurements.
  arXiv  Detail & Related papers  (2023-04-07T02:43:06Z)
• A Framework for Demonstrating Practical Quantum Advantage: Racing Quantum against Classical Generative Models [62.997667081978825]
  We build over a proposed framework for evaluating the generalization performance of generative models. We establish the first comparative race towards practical quantum advantage (PQA) between classical and quantum generative models. Our results suggest that QCBMs are more efficient in the data-limited regime than the other state-of-the-art classical generative models.
  arXiv  Detail & Related papers  (2023-03-27T22:48:28Z)
• 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)
• Quantum Annealing Learning Search Implementations [0.0]
  This paper presents the details and testing of two implementations of the hybrid quantum-classical algorithm Quantum Annealing Learning Search (QALS) on a D-Wave quantum annealer.
  arXiv  Detail & Related papers  (2022-12-21T15:57:16Z)
• Theory of Quantum Generative Learning Models with Maximum Mean Discrepancy [67.02951777522547]
  We study learnability of quantum circuit Born machines (QCBMs) and quantum generative adversarial networks (QGANs) We first analyze the generalization ability of QCBMs and identify their superiorities when the quantum devices can directly access the target distribution. Next, we prove how the generalization error bound of QGANs depends on the employed Ansatz, the number of qudits, and input states.
  arXiv  Detail & Related papers  (2022-05-10T08:05:59Z)
• Device-Independent-Quantum-Randomness-Enhanced Zero-Knowledge Proof [25.758352536166502]
  Zero-knowledge proof (ZKP) is a fundamental cryptographic primitive that allows a prover to convince a verifier of the validity of a statement. As an efficient variant of ZKP, non-interactive zero-knowledge proof (NIZKP) adopting the Fiat-Shamir is essential to a wide spectrum of applications.
  arXiv  Detail & Related papers  (2021-11-12T13:36:43Z)
• 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)
• Indistinguishability Obfuscation of Null Quantum Circuits and Applications [17.72516323214125]
  We study the notion of indistinguishability obfuscation for null quantum circuits (quantum null-iO) We show how quantum null-iO enables a series of new cryptographic primitives that, prior to our work, were unknown to exist even making assumptions.
  arXiv  Detail & Related papers  (2021-06-11T00:08:14Z)
• Quantum Federated Learning with Quantum Data [87.49715898878858]
  Quantum machine learning (QML) has emerged as a promising field that leans on the developments in quantum computing to explore large complex machine learning problems. This paper proposes the first fully quantum federated learning framework that can operate over quantum data and, thus, share the learning of quantum circuit parameters in a decentralized manner.
  arXiv  Detail & Related papers  (2021-05-30T12:19:27Z)
• 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)

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.