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. Quantum computers offer the potential to dramatically increase our ability to efficiently solve otherwise intractable computational problems, spanning a range of applications, from computational number theory [1] to the simulation of physical systems [2] . While for most of its history the experimental side of the field has been restricted to performing experiments on systems with very few degrees of freedom, which could be simulated using conventional computers with modest effort, recent advances have begun to push against this bound [3] . As the complexity of controlled quantum systems has grown, it has begun to exceed our ability to convincingly answer questions as to whether observed behaviour is consistent with quantum mechanics. This question has already arisen in relation to several recent experiments, leading to sometimes heated debate [4] [5] [6] [7] [8] [9] [10] [11] [12] . Fortunately, recent years have also seen the emergence of interactive methods for verifying quantum dynamics, in the form of protocols for verified quantum computation [13] [14] [15] [16] [17] [18] . Such protocols can be divided broadly into two classes. The first class are protocols which use a small, well characterized, quantum device to verify a computation carried out on a larger quantum system [13-15, 18, 19]. Protocols in this class generally exhibit low overhead, but this comes at the cost of an assumption that there is no malicious conspiracy involving both the verifier's device and the quantum system being probed. The second class of protocols make use of queries to multiple non-communicating quantum provers which share entanglement to verify the computation using self-testing techniques [16, 17, 20] . Such protocols offer security conditioned under the assumption that the provers do not communicate during the protocols. This type of security comes at the price of astronomical overhead, and enforcing a ban on communication between provers can become problematic in multi-round protocols where space-like separation becomes infeasible. Recently attempts have been made to unify the two approaches, making use of self-testing protocols to replace the quantum operations of the verifier in verifiable blind computation protocols [21, 22] , which has shown some success in lowering the overheads associated with multi-prover schemes. Despite their differences, several common features remain between all known protocols from both classes. Current protocols require continuous interaction during the computation in order to verify correctness [37] . This fundamentally links the task of verification to the specific implementation of the computation, making it impossible to verify the correctness of a computation after the fact. Furthermore, all known verification schemes, whether intentional in the design or not, exhibit some form of blind quantum computation [23, 24] , allowing them to hide the computation being performed from the processor performing the computation. Here we introduce a new approach to the problem of verifying quantum computation, based on recent progress on short interactive proofs of the local Hamiltonian problem [25, 26] . This gives rise to a pair of verification protocols that can be used to verify a quantum computation with only a single round of communication. This verification can occur arbitrarily long after the computation has been completed, provided that a suitable witness state has been prepared. Furthermore, these post hoc verification protocols do not inherently exhibit blindness, and hence their existence serves to introduce a separation between the notions of blindness and verifiability. The class of decision problems answerable by a quantum computer in polynomial time (BQP) is contained within a larger class known as QMA. This larger class corresponds to the class of problems for which the solution can be verified by a quantum computer in polynomial time given a suitable quantum state to act as a witness [27, 28] . QMA can be though of as the quantum analogue of the classical complexity class NP. Of the problems known to be complete for QMA, meaning that any problem within QMA can be reduced to an instance of that problem with modest computational overhead, perhaps the most studied is the problem of deciding whether the ground state energy of some local Hamiltonian is bounded below some threshold [29, 30] . Specifically, given constants a and b, with a < b, and a Hamiltonian H = ∑ m i=1 H i , where each H i acts non-trivially on at most k qubits, with the promise that for constants a < b either ψ|H|ψ ≤ am for some |ψ or ψ|H|ψ ≥ bm for all |ψ , the local Hamiltonian problem is to decide between these two cases. The fact that BQP is contained in QMA does not immediately imply a non-trivial method to verify a quantum computation, since several conditions must be met in order for a verification protocol to be useful: arXiv:1512.04375v1 [quant-ph]
Very recently, a single-round scheme was devised REF that relies on preparing the ground state of a FeynmanKitaev Hamiltonian.
Post hoc verification of quantum computation
ArXiv
ArXiv
Mathematics Physics Medicine Computer Science