Quantum proofs can be verified using only single qubit measurements

Abstract

QMA (Quantum Merlin Arthur) is the class of problems which, though potentially hard to solve, have a quantum solution which can be verified efficiently using a quantum computer. It thus forms a natural quantum version of the classical complexity class NP (and its probabilistic variant MA, Merlin-Arthur games), where the verifier has only classical computational resources. In this paper, we study what happens when we restrict the quantum resources of the verifier to the bare minimum: individual measurements on single qubits received as they come, one-by-one. We find that despite this grave restriction, it is still possible to soundly verify any problem in QMA for the verifier with the minimum quantum resources possible, without using any quantum memory or multiqubit operations. We provide two independent proofs of this fact, based on measurement based quantum computation and the local Hamiltonian problem, respectively. The former construction also applies to QMA${}_1$, i.e., QMA with one-sided error.

7 pages, 1 figure

References in corpus (2)

• Verifiable measurement-only blind quantum computing with stabilizer testing
• Classical Verification of Quantum Proofs

Cited by in corpus (22)

• Verification of quantum computation: An overview of existing approaches
• Theory of quantum system certification: a tutorial
• Post hoc verification with a single prover
• Post hoc verification of quantum computation
• Theoretical and Experimental Perspectives of Quantum Verification
• Verification of Many-Qubit States
• Verified measurement-based quantum computing with hypergraph states
• Measurement-only verifiable blind quantum computing with quantum input verification
• Zero-knowledge proof systems for QMA
• Classical zero-knowledge arguments for quantum computations
• Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy
• Quantum Merlin-Arthur with noisy channel
• Catalytic Transformation from Computationally Universal to Strictly Universal Measurement-Based Quantum Computation
• Quantum Arthur-Merlin with single-qubit measurements
• Finding resource states of measurement-based quantum computing is harder than quantum computing
• Information-theoretically-sound non-interactive classical verification of quantum computing with trusted center
• Passive verification protocol for thermal graph states
• Blind quantum computing can always be made verifiable
• Quantum state and circuit distinguishability with single-qubit measurements
• Classically Verifiable NIZK for QMA with Preprocessing
• Complexity of Fermionic 2-SAT
• Phase Transitions and Noise Robustness of Quantum Graph States