Source-linked AI summary
Post hoc verification of quantum computation
Joseph F. Fitzsimons, Michal Hajdušek
TL;DR
The paper addresses how to verify arbitrary quantum computations despite existing protocols requiring interaction during computation. It proposes two local-Hamiltonian-based protocols enabling single-round, post hoc verification, assuming suitable witness states can be prepared.
Problem
Existing quantum-computation verification schemes require continuous interaction during computation, preventing verification after the fact.
Source: p. 1Method
The paper casts output verification as a probability decision problem and encodes it into local Hamiltonian instances verified using short interactive proofs.
Source: pp. 1–2Results
The protocols provide single-round verification that can occur arbitrarily long after computation, with one variant allowing a purely classical prover.
Source: pp. 1, 4Takeaways & Limitations
Post hoc verifiability can be separated from blindness because these protocols do not inherently hide the computation from the processor.
Source: p. 1Verification may be no more efficient than the original computation, and witness generation may require substantially greater computational power than deciding the statement.
Source: p. 2
Abstract
from arXiv · showhide
With recent progress on experimental quantum information processing, an important question has arisen as to whether it is possible to verify arbitrary computation performed on a quantum processor. A number of protocols have been proposed to achieve this goal, however all are interactive in nature, requiring that the computation be performed in an interactive manner with back and forth communication between the verifier and one or more provers. Here we propose two methods for verifying quantum computation in a non-interactive manner based on recent progress in the understanding of the local Hamiltonian problem. Provided that the provers compute certain witnesses for the computation, this allows the result of a quantum computation to be verified after the fact, a property not seen in current verification protocols.