PaperlayerView exact revision on arXiv

Source-linked AI summary

Non-interactive classical verification of quantum computation

Gorjan Alagic, Andrew M. Childs, Alex B. Grilo, Shih-Han Hung

arXiv:1911.08101v2quant-phcs.CCcs.CR

TL;DR

Classical verification of quantum computations is difficult when devices become too large for direct classical simulation. This paper transforms Mahadev’s protocol into non-interactive BQP verification and a zero-knowledge argument for QMA, under stated cryptographic assumptions.

  • Problem

    Verifying quantum devices becomes difficult when their scale rules out direct classical simulation, motivating protocols for classical verification of quantum computation.

    Source: §1 · p. 1

  • Method

    The authors move the first message to offline setup, prove optimal-rate parallel repetition, apply Fiat–Shamir, and combine classical NIZK with circuit-private FHE for zero knowledge.

    Source: §1 · pp. 3–5

  • Results

    Under LWE, k-fold repetition gives three-round BQP verification with completeness 1 − negl(n) and soundness error 2−k + negl(n), while Fiat–Shamir yields non-interactive verification in the QROM.

    Source: §1 · pp. 5–6

  • Takeaways & Limitations

    Under LWE and circuit-private FHE, the construction gives a classical non-interactive zero-knowledge argument for QMA with trusted offline setup.

    Source: §1 · p. 5

    Security relies on quantum-hard LWE and the QROM; the zero-knowledge construction additionally requires circuit-private FHE.

    Source: §1 · p. 3

Abstract

from arXiv · show

In a recent breakthrough, Mahadev constructed an interactive protocol that enables a purely classical party to delegate any quantum computation to an untrusted quantum prover. In this work, we show that this same task can in fact be performed non-interactively and in zero-knowledge. Our protocols result from a sequence of significant improvements to the original four-message protocol of Mahadev. We begin by making the first message instance-independent and moving it to an offline setup phase. We then establish a parallel repetition theorem for the resulting three-message protocol, with an asymptotically optimal rate. This, in turn, enables an application of the Fiat-Shamir heuristic, eliminating the second message and giving a non-interactive protocol. Finally, we employ classical non-interactive zero-knowledge (NIZK) arguments and classical fully homomorphic encryption (FHE) to give a zero-knowledge variant of this construction. This yields the first purely classical NIZK argument system for QMA, a quantum analogue of NP. We establish the security of our protocols under standard assumptions in quantum-secure cryptography. Specifically, our protocols are secure in the Quantum Random Oracle Model, under the assumption that Learning with Errors is quantumly hard. The NIZK construction also requires circuit-private FHE.

1 Introduction

The paper transforms Mahadev’s four-message verification protocol into non-interactive protocols with offline setup, including a zero-knowledge construction. Its main technical step is optimal-rate parallel repetition, and the results rely on quantum-secure cryptographic assumptions.

1 Introduction

  • The security proofs assume quantum-hard LWE and use the QROM; the zero-knowledge protocol additionally requires circuit-private FHE.The exposition assumes security parameters polynomial in the BQP instance size.Source: §1 · p. 3
  • Instance-independent setup is obtained by increasing the ground-state copies by a constant factor, so some random basis and term assignments are consistent.A random assignment is consistent with probability 1/4.Source: §1 · p. 4
  • Parallel repetition achieves the sequential soundness rate δ^k while keeping the protocol’s interaction-round count unchanged.The proof uses nearly computationally orthogonal accepting-path projectors for distinct challenge strings.Source: §1 · pp. 4–5
  • Under LWE, k-fold repetition gives BQP verification with completeness 1 − negl(n) and soundness error 2−k + negl(n).The repeated protocol has three rounds with offline setup.Source: §1 · p. 5
  • The zero-knowledge construction uses classical NIZK and circuit-private FHE, with trusted setup, to obtain a three-round argument for QMA.Its assumptions include LWE and circuit-private FHE.Source: §1 · p. 5
  • Fiat–Shamir yields non-interactive BQP verification with offline setup and negligible completeness and soundness errors in the QROM.The theorem takes k = ω(log n) and assumes LWE.Source: §1 · p. 6

2 Preliminaries

The preliminaries set up classical verification of quantum computation through local-Hamiltonian tests and the Mahadev protocol. They also introduce NIZK for NP, whose properties provide background for the paper’s QMA construction.

2.1 Notation and conventions

  • The section defines efficient algorithms, negligible error, and coherent implementations of classical functions as notation used throughout the paper.It assumes the input size and security parameter are polynomially related.Source: §2.1 · p. 7

2.2 Quantum-prover interactive arguments

  • A quantum-prover interactive argument pairs a polynomial-time classical verifier with a quantum prover, with completeness and soundness bounding acceptance on yes- and no-instances.Soundness can be amplified by sequential repetition and, in some cases, parallel repetition.Source: §2.2 · pp. 7–8

2.3 The local Hamiltonian problem and verification for BQP

  • The ZX-Hamiltonian problem encodes low versus high ground-state energy, and its terms can be tested using only single-qubit X and Z measurements.The MF protocol samples a Hamiltonian term and measures the corresponding observable; polynomially many repetitions can suppress its errors to negligible.Source: §2.3 · pp. 8–9

2.4 The Mahadev protocol for BQP verification

  • The Mahadev protocol [Mah18] lets a verifier request X- or Z-basis measurement outcomes without revealing the basis to the prover, with decoded responses close to measurements of an n-qubit state simultaneously across all basis choices.Under LWE, Protocol 2 is a four-message quantum-prover interactive argument for BQP with completeness error negl(n) and soundness error 3/4 + negl(n).Source: §2.4 · pp. 10–11

2.5 NIZK for NP

  • The NP NIZK framework includes setup, proving, verification, and simulation, with zero-knowledge requiring real proofs and simulated transcripts to be computationally indistinguishable.The paper uses a Peikert–Shiehian construction based on LWE; its QMA variant uses a quantum witness and prover, and works in the random oracle model with setup rather than the desired common reference string model.Source: §2.5 · pp. 11–12

3 Instance-independent key generation

The protocol modifies the MF test so that Hamiltonian-term sampling is independent of the measurements. This permits Mahadev keys to be generated before the input Hamiltonian arrives, in an offline setup phase.

3 Instance-independent key generation

  • The modified MF protocol makes term sampling independent of measurements, allowing Mahadev keys to be generated before the input Hamiltonian arrives.The resulting three-round Mahadev protocol uses secret keys to compute Hadamard-round outcomes, then samples Hamiltonian terms and checks consistent copies.Source: §3 · pp. 12–13
  • The verifier accepts only consistent basis-and-term copies; for sufficiently large r, there are around r/4 such copies, so a constant-factor increase in copies suffices to retain completeness and soundness.The verifier tests the accepted outcomes against the MF threshold.Source: §3 · pp. 12–13
  • The modified parallel-repeated MF protocol has negligible completeness and soundness errors when r = ω(log n).Source: §3 · p. 13

4 A parallel repetition theorem for the Mahadev protocol

The paper establishes near-orthogonality between challenge-dependent acceptance tests, including when a prover adapts its state after learning the challenge. Extending this property to repeated copies yields soundness at most 2^-k + negl(n) under LWE.

4 A parallel repetition theorem for the Mahadev protocol

  • The protocol repeats the verifier’s test independently and accepts only when every copy passes; the prover may apply challenge-dependent unitaries before honest measurements.Source: §4 · p. 13, §4.2 · p. 16

4.1 A lemma for the single-copy protocol

  • The single-copy lemma compares a prover’s decoded outcomes with measurements of an efficiently preparable quantum state, using results about perfect and trivial provers.The proof first relates a nearly perfect prover to a trivial prover, then shows its distribution is computationally indistinguishable from measurements of a consistent state.Source: §4.1 · pp. 14–15
  • For one copy, a prover that nearly always passes the test round must almost certainly fail the Hadamard round, even after adapting its state to the challenge.The accepting projectors are nearly orthogonal for states prepared by efficient provers.Source: §4.1 · pp. 14–15

4.2 The parallel repetition theorem

  • The parallel-repetition proof extends adaptive orthogonality to distinct challenge strings, then bounds their combined acceptance using pairwise near-orthogonality.This rules out improving overall success by succeeding appreciably on several challenges; the resulting soundness is negligibly close to 2^-k.Source: §4.2 · pp. 16, 17, 19
  • Under LWE, the k-fold three-round Mahadev protocol has soundness error at most 2^-k + negl(n).The theorem concerns parallel repetition of the three-round protocol.Source: §4.2 · p. 19

5 A classical zero-knowledge argument for QMA

Protocol 6 uses encrypted NIZK proofs to hide a verifier-dependent statement while retaining a classical verification procedure. It has negligible completeness and soundness errors, and is zero-knowledge under the stated commitment assumption.

5 A classical zero-knowledge argument for QMA

  • Homomorphic FHE evaluation lets the prover produce an encrypted NIZK proof using an encrypted instance, avoiding disclosure of the verifier’s secret key and secret randomness.The verifier decrypts the proof ciphertext and checks the resulting NIZK proof.Source: §5 · pp. 20–21

5.1 Completeness and soundness

  • Protocol 6 has negligible completeness and soundness errors, with soundness established for no-instances against bounded provers.Completeness follows from FHE correctness, NIZK completeness, and Protocol 4 completeness.Source: §5.1 · pp. 21–22

5.2 The zero-knowledge property

  • Protocol 6 is zero-knowledge assuming a non-interactive bit commitment scheme with perfect binding and computational hiding.The proof compares simulator output distributions through computational indistinguishability steps, including the indistinguishability of SQ and S.Source: §5.2 · pp. 22–23

6 Round reduction by Fiat-Shamir transformation

The section applies Fiat–Shamir to reduce interaction, first describing its standard form and then extending soundness analysis to protocols with an initial verifier message. The transformation yields a non-interactive zero-knowledge protocol for QMA in the QROM.

6 Round reduction by Fiat-Shamir transformation

  • Fiat–Shamir converts the three-message Protocol 6 into a non-interactive protocol with setup while retaining negligible completeness and soundness errors.The prover computes the challenge by hashing the transcript, and the zero-knowledge variant is included.Source: §6 · p. 24, §6.3 · p. 26

6.1 Fiat-Shamir for Σ-protocols in the QROM

  • In the QROM, Fiat–Shamir security must account for quantum oracle access, and the section invokes a quantum-security theorem for the transformation.The random oracle is accessible to parties through quantum oracle queries.Source: §6.1 · pp. 24–25

6.2 Extension to generalized Σ-protocols

  • Generalized Σ-protocols allow an initial verifier message, and their Fiat–Shamir soundness error is O(sq^2 + q|Y|^-1) for provers making up to q random-oracle queries.When s and |Y|^-1 are negligible, the transformed protocol retains negligible soundness against efficient provers making polynomially many queries.Source: §6.2 · pp. 25–26

6.3 Non-interactive zero-knowledge for QMA

  • Applying Fiat–Shamir to Protocol 6 gives a non-interactive zero-knowledge argument for QMA in the Quantum Random Oracle Model.The prover derives the challenge coins from the random oracle and redefines the NIZK instance using those coins.Source: §6.3 · p. 26

A.1 Commitment schemes

The appendix defines a commitment scheme through key generation, commitment, and verification algorithms, then states properties of the LWE-based scheme.

A.1 Commitment schemes

  • A trapdoor commitment scheme comprises algorithms gen, commit, and verify, with key generation producing public and secret keys.Commit takes a bit and string to produce a commitment; verify checks the bit, string, and commitment.Source: §A.1 · p. 29
  • The LWE-based scheme is perfectly binding: equal commitments imply equal committed bits.Source: §A.1 · p. 29
  • The scheme’s listed second property is quantum computational concealing, but the supplied passage does not state its formal condition.Source: §A.1 · p. 29

A.2 Fully homomorphic encryption with circuit privacy

The appendix specifies FHE algorithms for key generation, encryption, decryption, and homomorphic evaluation, and lists quantum security and circuit privacy properties.

A.2 Fully homomorphic encryption with circuit privacy

  • FHE provides Gen, Enc, Dec, and Eval algorithms, with Eval producing a ciphertext from a circuit and ciphertext inputs.Gen outputs secret and public keys; Enc encrypts a message, and Dec recovers a message from a ciphertext.Source: §A.2 · pp. 29–30
  • The scheme requires semantic security against quantum adversaries and malicious circuit privacy.Source: §A.2 · p. 30
  • An FHE scheme with malicious circuit privacy is stated to exist assuming quantum computational intractability of LWE.Source: §A.2 · p. 30

B Proof of Lemma 3.1

Protocol 3 has negligible completeness and soundness error when the repetition count grows faster than g^-2 log n, where g is the promise gap. The proof uses an effective Hamiltonian for repeated verification and bounds soundness using Hoeffding’s inequality.

B Proof of Lemma 3.1

  • Each copy tests a term sampled from π with probability 1/4, yielding an effective repeated Hamiltonian whose ground state is also the ground state of H.The proof invokes the standard parallel repetition theorem for QMA to identify the optimal strategy.Source: B Proof of Lemma 3.1 · p. 30
  • For soundness, the proof bounds acceptance across consistent copies using Hoeffding’s inequality.The success-probability calculation uses the promise gap g.Source: B Proof of Lemma 3.1 · p. 31
  • Setting r = ω(g^-2 log n) suppresses soundness error to n^-ω(1) and makes completeness error negligible; since g^-1 = poly(n), polynomially many copies suffice for negligible soundness error.Source: B Proof of Lemma 3.1 · p. 31

C Proof of Lemma 4.2

The proof of Lemma 4.2 argues by contradiction: a violation would yield a single-copy prover that is perfect on the test round yet violates Lemma 4.1. A repeat-until-success construction supplies the test-round condition, while good keys make its termination likely.

C Proof of Lemma 4.2

  • The proof reduces a failure of the claimed state bound to an efficient single-copy prover contradicting Lemma 4.1.It assumes a violating basis choice and randomness, then constructs the prover from the k-fold prover.Source: C Proof of Lemma 4.2 · pp. 31–32
  • The reduction simulates the other verifier copies and uses a repeat-until-success procedure to prepare a state that passes the selected test-round coordinate.The procedure performs the prover’s preparation and challenge-dependent unitary, tests acceptance, and repeats after rejection.Source: C Proof of Lemma 4.2 · pp. 32–33
  • The constructed prover is accepted perfectly when the verifier selects a test round, so it meets the test-round condition used in the contradiction.The acceptance test in that round is independent of the basis choice.Source: C Proof of Lemma 4.2 · p. 33
  • For good keys, the probability that the procedure fails to terminate within q = poly(n) steps is at most e^-√q, making its success probability 1 − negl(n).The proof uses this high-probability termination to complete the contradiction.Source: C Proof of Lemma 4.2 · p. 33

D Proof of Lemma 4.3

Lemma 4.3 relates the total expected acceptance of several projectors to bounds on their pairwise symmetrized overlaps. Its proof controls the sum by considering its second moment.

D Proof of Lemma 4.3

  • Lemma 4.3 bounds the total expected acceptance of projectors under pairwise upper bounds on their symmetrized overlaps.The stated hypotheses bound ⟨ψ|AiAj + AjAi|ψ⟩ for distinct projectors.Source: D Proof of Lemma 4.3 · p. 34
  • The proof compares the square of the expected sum with the expectation of the squared sum.Source: D Proof of Lemma 4.3 · p. 34
  • Idempotence of each projector lets the squared sum be expanded into individual and cross terms for the bound.The proof then uses an inequality relating x^2 ≤ x + β to an upper bound on x.Source: D Proof of Lemma 4.3 · p. 34

E Proof of soundness for Protocol 6

The soundness proof uses a sequence of hybrids, showing negligible acceptance for no-instances at each step. The transitions rely on commitments, FHE security, and NIZK soundness.

E Proof of soundness for Protocol 6

  • The proof aims to show negligible maximum acceptance for no-instances in every hybrid H0 through H4.H0 is handled by Theorem 4.6; the remaining hybrids are addressed in successive steps.Source: E Proof of soundness for Protocol 6 · pp. 34–35
  • In H1, revealing the committed key pair in Round P2 preserves negligible soundness because the commitment is perfectly binding and the verifier’s challenge is public coins.The proof first replaces the instance with a keyed instance having the same ground-state energy, preserving the soundness bound.Source: E Proof of soundness for Protocol 6 · p. 35
  • Adding the commitment to u in H2 can only reduce the prover’s success probability.Source: E Proof of soundness for Protocol 6 · p. 35
  • FHE security makes H3 indistinguishable from H2 when encryptions of (0, 0) replace encryptions of (s, sk), preserving negligible acceptance.Otherwise a prover succeeding in H3 would give an adversary succeeding in H2 with nearly the same probability.Source: E Proof of soundness for Protocol 6 · pp. 35–36
  • In H4, an accepting view must have a unique witness, while NIZK soundness prevents proving false statements for no-instances, even when the proof is encrypted.The transition to H4 adds the common reference string and encrypted proof to the protocol.Source: E Proof of soundness for Protocol 6 · pp. 35–36

F The reduction for Σ-protocols in the QROM

The section reduces a Fiat–Shamir prover in the QROM to a prover in the underlying Σ-protocol. The reduction simulates the random oracle with a quantum-secure pseudorandom function and reprograms it after the verifier’s challenge.

F The reduction for Σ-protocols in the QROM

  • The simulator begins by instantiating a quantum-secure pseudorandom function, choosing a random query index, and preparing the prover’s state.When an upper bound q is known, a 2q-wise independent function would suffice.Source: F The reduction for Σ-protocols in the… · p. 36
  • After measuring and sending commitment y, the simulator receives challenge Θ, reprograms its oracle for subsequent queries, and branches on a random bit to simulate the prover.It aborts if its later measurement of Y differs from y; otherwise it outputs (y, m).Source: F The reduction for Σ-protocols in the… · pp. 36–37
  • A successful Fiat–Shamir prover yields a Σ-protocol prover whose success probability is polynomially related to the original prover’s.The reduction is black-box, using queries to the Fiat–Shamir prover.Source: F The reduction for Σ-protocols in the… · pp. 36–37
  • For the generalized Σ-protocol lemma, success probability ε against the Fiat–Shamir verifier implies success probability at least ε for prover B in the interactive protocol.The lemma considers the hash challenge H(x, f(r, x), y).Source: F The reduction for Σ-protocols in the… · p. 37
Loading 1911.08101v2…