Non-interactive classical verification of quantum computation

Abstract

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.

37 pages

References in corpus (7)

• Realizable Hamiltonians for Universal Adiabatic Quantum Computers
• Non-interactive classical verification of quantum computation
• Quantum Proofs
• Semi-Quantum Money
• Self testing quantum apparatus
• QMA-hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge
• Non-interactive zero-knowledge arguments for QMA, with preprocessing

Cited by in corpus (14)

• Non-interactive classical verification of quantum computation
• Self-testing of a single quantum device under computational assumptions
• QMA-hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge
• Unifying Quantum Verification and Error-Detection: Theory and Tools for Optimisations
• Divide-and-conquer verification method for noisy intermediate-scale quantum computation
• Multi-theorem (Malicious) Designated-Verifier NIZK for QMA
• Lightweight Detection of a Small Number of Large Errors in a Quantum Circuit
• Information-theoretically-sound non-interactive classical verification of quantum computing with trusted center
• Towards a quantum-inspired proof for IP = PSPACE
• A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds
• Zero-Knowledge Proofs of Quantumness
• Non-Destructive Zero-Knowledge Proofs on Quantum States, and Multi-Party Generation of Authorized Hidden GHZ States
• Certified Everlasting Zero-Knowledge Proof for QMA
• Classically Verifiable NIZK for QMA with Preprocessing