Self-guaranteed measurement-based quantum computation

In order to guarantee the output of a quantum computation, we usually assume that the component devices are trusted. However, when the total computation process is large, it is not easy to guarantee the whole system when we have scaling effects, unexpected noise, or unaccounted for correlations between several subsystems. If we do not trust the measurement basis or the prepared entangled state, we do need to be worried about such uncertainties. To this end, we propose a self-guaranteed protocol for verification of quantum computation under the scheme of measurement-based quantum computation where no prior-trusted devices (measurement basis or entangled state) are needed. The approach we present enables the implementation of verifiable quantum computation using the measurement-based model in the context of a particular instance of delegated quantum computation where the server prepares the initial computational resource and sends it to the client, who drives the computation by single-qubit measurements. Applying self-testing procedures, we are able to verify the initial resource as well as the operation of the quantum devices and hence the computation itself. The overhead of our protocol scales with the size of the initial resource state to the power of 4 times the natural logarithm of the initial state's size.

Figure 1

Representation of the self-testing procedure for the state $\left(\right|0,+\rangle +|1,-\rangle )/\sqrt{2}$. We prepared $8m$ copies of this state which were then randomly divided into eight groups. Each group was measured as described in (2.3) and (2.4). There are four measurement settings for system ${\mathcal{H}}_1^{\prime }$ and two measurement settings for system ${\mathcal{H}}_2^{\prime }$. Each group was measured by one device acting on system ${\mathcal{H}}_1^{\prime }$ and one device acting on system ${\mathcal{H}}_2^{\prime }$.

Figure 2

Two examples of three-colorable graphs with their black vertices partitioned into subsets ${\left\{S_{B,k}\right\}}_{k=1}^{l_B}$. (a) For the small graph we can see that $l_B\le 2$. (b) The triangular lattice is still three-colorable but has $l_B\le 3$. It can be readily checked that this partitioning satisfies the nonconflict condition since elements of the same partition $S_{B,j}$ do not share any common neighbors. White and red vertices may be partitioned in the same way, which means that $l_W,l_R\le 3$.