Post hoc verification with a single prover

Abstract

We propose a simple protocol for the verification of quantum computation after the computation has been performed. Our construction can be seen as an improvement on previous results in that it requires only a single prover, who is restricted to measuring qubits in the $X$ or $Z$ basis, while requiring only one way communication, from the prover to the verifier. We also show similar constant round protocols with purely classical verifiers are not possible, unless BQP is contained in the third level of the polynomial hierarchy.

4 pages, no figure

References in corpus (2)

• Realizable Hamiltonians for Universal Adiabatic Quantum Computers
• Classical Verification of Quantum Proofs

Cited by in corpus (41)

• Photonic quantum information processing: a review
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Verification of quantum computation: An overview of existing approaches
• Computational advantage of quantum random sampling
• Theoretical and Experimental Perspectives of Quantum Verification
• Certifying the building blocks of quantum computers from Bell's theorem
• Self-guaranteed measurement-based quantum computation
• Resource-efficient verification of quantum computing using Serfling's bound
• Noise-resistant device-independent certification of Bell state measurements
• Non-interactive classical verification of quantum computation
• Accrediting outputs of noisy intermediate-scale quantum computing devices
• QFactory: classically-instructed remote secret qubits preparation
• QMA-hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge
• Quantum Correlation Sharing: A Review On Recent Progress From Nonlocality To Other Non-Classical Correlations
• Experimental accreditation of outputs of noisy quantum computers
• Reducing resources for verification of quantum computations
• Preparation and verification of tensor network states
• Security Limitations of Classical-Client Delegated Quantum Computing
• Classical zero-knowledge arguments for quantum computations
• Unifying Quantum Verification and Error-Detection: Theory and Tools for Optimisations
• Classical verification of quantum circuits containing few basis changes
• Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy
• Cross-verification of independent quantum devices
• Divide-and-conquer verification method for noisy intermediate-scale quantum computation
• Quantum advantage from energy measurements of many-body quantum systems
• In situ characterization of linear-optical networks in randomized boson sampling
• Sumcheck-based delegation of quantum computing to rational server
• Methods for Classically Simulating Noisy Networked Quantum Architectures
• Efficient classical verification of quantum computations
• Information-theoretically-sound non-interactive classical verification of quantum computing with trusted center
• A Quantum inspired proof of $P^{\#P}\subseteq IP$
• Efficiently verifiable quantum advantage on near-term analog quantum simulators
• Classical Commitments to Quantum States
• Sampling and the complexity of nature
• Parallel remote state preparation for fully device-independent verifiable blind quantum computation
• Instantaneous Quantum Polynomial-Time Sampling and Verifiable Quantum Advantage: Stabilizer Scheme and Classical Security
• Blind quantum computing can always be made verifiable
• Accreditation Against Limited Adversarial Noise
• Any gate of a quantum computer can be certified device-independently
• Quantum computation capability verification protocol for NISQ devices with dihedral coset problem
• On Information-Theoretic Classical Verification of Quantum Computers