Post hoc Verification of Quantum Computation

We propose a set of protocols for verifying quantum computing at any time after the computation itself has been performed. We provide two constructions: one requires five entangled provers and a completely classical verifier; the other requires a single prover, a verifier, who is restricted to measuring qubits in the $X$ or $Z$ basis, and one-way quantum communication from the prover to the verifier. These results demonstrate that the verification can be achieved independently from the blindness. We also show that a constant round protocol with a single prover and a completely classical verifier is not possible, unless bounded error quantum polynomial time (BQP) is contained in the third level of the polynomial hierarchy.

Figure 1

A quantum circuit for verifying that $S$ is a possible output of computation $\mathcal{C}$. The measured qubit is in state $|1⟩$ with probability $p_S$. $S_i$ is $i$th bit of $S$.

Figure 2

A quantum circuit for verifying that $S$ is a possible output of computation $\mathcal{C}$ with amplified probability of success. $U_{\mathrm{SUM}}$ performs an $X$ gate on the final qubit conditioned on at least a fraction $1-\delta -\gamma /2$ of the other qubits being in state $|0⟩$. From Hoeffding’s inequality, it follows that when $p_S\ge 1-\delta$ that the probability ${\tilde{p}}_S$ that output qubit is measured to be in state $|1⟩$ with probability at least $1-\exp (-N{\gamma }^2/2)$, where $N$ is the number of times $\mathcal{C}$ is evaluated. However, when $p_S\le \epsilon$ then ${\tilde{p}}_S$ is at most $\exp (-N{\gamma }^2/2)$.