2022

[1,2]Wen-Jie Liu

These authors contributed equally to this work.

These authors contributed equally to this work.

These authors contributed equally to this work.

[1]School of Software, Nanjing University of Information Science and
Technology, No. 219 Ningliu Road, Nanjing, 210044, Jiangsu, China

2]Engineering Research Center of Digital Forensics, Ministry of Education, No.
219 Ningliu Road, Nanjing, 210044, Jiangsu, China

# Public Verifiable Measurement-Only Blind Quantum Computation Based On
Entanglement Witnesses

<EMAIL_ADDRESS>Zi-Xian Li<EMAIL_ADDRESS>Wen-Bo Li<EMAIL_ADDRESS>Qi
Yang<EMAIL_ADDRESS>*  [

###### Abstract

Recently Sato et al. proposed an public verifiable blind quantum computation
(BQC) protocol by inserting a third-party arbiter. However, it isn’t true
public verifiable in a sense, because the arbiter is determined in advance and
participates in the whole process. In this paper, a public verifiable protocol
for measurement-only BQC is proposed. The fidelity between arbitrary states
and the graph states of $2$-colorable graphs is estimated by measuring the
entanglement witnesses of the graph states, so as to verify the correctness of
the prepared graph states. Compared with the previous protocol, our protocol
is public verifiable in the true sense by allowing other random clients to
execute the public verification. It also has greater advantages in the
efficiency, where the number of local measurements is $O(n^{3}\log{n})$ and
graph states’ copies is $O(n^{2}\log{n})$.

###### keywords:

Blind quantum computation, Public verifiability, Graph state, Entanglement
witness

##  1 Introduction

Blind quantum computation (BQC) allows any client (known as Alice) with weak
quantum ability to delegate her computing tasks to a quantum server (known as
Bob) without leaking her privacy. BQC is divided into two categories: circuit-
based BQC (CBQC)RN1 ; RN2 ; RN3 ; RN4 ; RN5  and measurement-based BQC
(MBQC)RN6 ; RN7 ; RN8 ; RN9 ; RN10 ; RN11 ; RN12 ; RN13 ; RN14 ; RN15 ; RN17 ;
RN18 . CBQC realizes blindness through quantum circuits, where the client
needs to have the ability to operate some quantum gates. In MBQC, the client
only needs to prepare and measure quantum states. Recently, Morimae and
FujiRN7  proposed a new type of BQC, called measurement-only BQC (MOBQC),
where the server prepare the resource state, while the client just should
perform single-qubit measurements.

As more and more BQC protocols are proposed, the verifiability of BQC has
attracted much attention. In a verifiable BQC protocol, each party can verify
whether other party is honest. Although Broadbent et al.RN6  have explored the
possibility of verifiability in their protocol, it’s not complete. Based on
the former, Fitzsimons et al.RN8  proposed a relatively complete verifiable
version. In this protocol, the verifier encodes the computation task
(including the verification mechanism) into a series of single qubits, and
then executes BQC. According to the results, it can be verified whether the
computation has been correctly executed. In addition, several BQC protocolsRN2
; RN8 ; RN9  verifies the correctness of the input of BQC by checking the trap
qubits randomly hidden in the input state. For MOBQCRN7 , it’s proposed to
verify graph statesRN10 ; RN11 ; RN12 ; RN13 ; RN14 . Stabilizer testingRN14
is a verification technology of the graph state without setting traps. The
server generates graph states and send them to the client, and the latter then
directly measure stabilizers on the sent graph states to verifies the
correctness. However, these verifiable MOBQC protocols RN10 ; RN12 ; RN13 ;
RN14  using stabilizer test are of high resource consumption, which is an
obstacle to the development of scalable quantum computation. In 2021, Xu et
al.RN15  proposed a verifiable BQC protocol based on entanglement witnesses,
which effectively reduces the resource consumption of verification by
measuring entanglement witnessesRN16  that can detect the graph states.

The above verifiable protocols only allow Alice to verify Bob’s honesty, which
is called private verifiability. However, private verifiability has the
following problems: Alice can detect any dishonest behavior of Bob, but the
detection results can not make any third party trusted; even if Bob is honest,
he can be framed by Alice. In 2016, on the basis of unconditionally verifiable
BQC protocolRN8 , KentaroRN17  proposed the concept of public verifiability
and provided a corresponding protocol based on classical cryptography. In
2019, Sato et al.RN18  chose to insert a trusted third party as the arbiter to
build an arbitrable BQC protocol which realizes public verifiability in a
sense. However, the public verifiability depends on the arbiter, which is
determined in advance and participates in the whole process, thus the protocol
isn’t true public verifiable in a sense.

In this paper, inspired by the verifiable mechanism based on entanglement
witnesses, we propose a public verifiable MOBQC protocol. The third-party
verifier is randomly selected from other clients rather than a specific
arbiter, so as to achieve public verifiability in the true sense. In addition,
$2$-colorable graphs and entanglement witnesses are introduced to reduce
resource consumption. Compared with the number of local measurements
($O(n^{2n+5})$) and of copies of the resource states ($O(n^{2n+5}2^{n})$) of
Sato et al.RN18 , our protocol have obvious advantages ($O(n^{3}\log{n})$ and
$O(n^{2}\log{n})$ respectively). We also consider the communication error and
give some error mitigation schemes.

The rest of this paper is organized as follows: In Sect. 2, we briefly
introduce $2$-colorable graph states, entanglement witnesses, and MOBQC. The
protocol is presented in Sect. 3 and analyzed in Sect. 4. Error propagation
and mitigation is analyzed in Sect. 5. The paper concludes with Sect. 6.

##  2 Preliminaries

In this section, we briefly introduce $2$-colorable graph states and the
entanglement witnesses of them, and then review the basic steps of
measurement-only BQC.

###  2.1 2-colorable graph state

Given an undirected simple graph $G$ with $n$ vertices $i\in V$ and several
edges $(i,j)\in E=V\times V$, if all vertices of it can be divided into at
least $m$ disjoint subsets ${S_{1}},{S_{2}},\cdots,{S_{m}}$, where there is no
edge between any pair of vertices in any $S_{j},j=1,2,\cdots,m$, then we call
$G$ an $m$-colorable graph. We use $n$ qubits to represent vertices of $G$,
and the graph state $\left\lvert G\right\rangle$ corresponding to $G$ is
defined as $\left\lvert
G\right\rangle=\left({\prod\nolimits_{\left({i,j}\right)\in
E}{{U_{ij}}}}\right){\left\lvert+\right\rangle^{\otimes n}}$, where
$\left\lvert+\right\rangle={1\over{\sqrt{2}}}\left({\left\lvert
0\right\rangle+\left\lvert 1\right\rangle}\right)$ is the initial state of
each vertex and ${U_{ij}}$ is the controlled-$Z$ gate $\left\lvert
0\right\rangle\left\langle 0\right\lvert\otimes I+\left\lvert
1\right\rangle\left\langle 1\right\lvert\otimes Z$ performed on vertices $i$
and $j$, where $I$ is identity operator and $Z$ is Pauli operator
$\sigma_{z}$. On the other hand, there are $n$ stabilizer
${g_{i}}={X_{i}}\prod\nolimits_{k\in N\left(i\right)}{{Z_{k}}}$ of
$\left\lvert G\right\rangle$, i.e., $g_{i}\left\lvert
G\right\rangle=\left\lvert G\right\rangle$, where $i=1,2,\cdots,n$,
$N\left(i\right)$ is the adjacency points set of vertex $i$ and $X_{i},Z_{j}$
are the Pauli operators $\sigma_{x},\sigma_{z}$ performed on $i,j$
respectively.

In this paper, we only consider $2$-colorable graph states which are widely
used as resource states of BQC, such as brickwork stateRN6  and Raussendorf-
Harrington-Goyal (RHG) stateRN19 , of which the preparation and verification
are of research value. An example of a $2$-colorable graph is shown in Figure
1.

Figure 1: A $2$-colorable graph as an example, where red vertices belong to
$S_{1}$ and green vertices belong to $S_{2}$.

###  2.2 Entanglement witness

An entanglement witness $W$ is an observable measurement which satisfies: (1)
For all separable states ${\varrho_{s}}$, $tr\left({W{\varrho_{s}}}\right)\geq
0$; (2) At least one entangled state ${\varrho_{e}}$ satisfies
$tr\left({W{\varrho_{e}}}\right)<0$, where $tr\left(\cdot\right)$ represents
matrix trace; then we say that ${\varrho_{e}}$ is detected by $W$. For an
$n$-qubit graph state and some states close to it, based on the colorability
of the graph, some witnesses with constant measurement times are proposed. The
following $W^{\left(2\right)}$ is a witness of a $2$-colorable graph state
$\left\lvert G\right\rangle$RN16 :

${W^{\left(2\right)}}=3I-2\left[{\prod\limits_{i\in{S_{1}}}{{{{g_{i}}+I}\over
2}}+\prod\limits_{i\in S2}{{{{g_{i}}+I}\over 2}}}\right],$ (1)

where $S_{1},S_{2}$ are two divided sets of the graph. According to the
structure of the witness, for a given $2$-colorable graph state, only two
measuring settings are needed, and the $j$-th setting is observable
$\prod\limits_{i\in{S_{j}}}{{g_{i}}}$. The two settings corresponding to the
two-colorable graph in Figure 1 are shown in Figure 2. For the $j$-th
measuring setting $\prod\limits_{i\in{S_{j}}}{{g_{i}}}$, we only need to
measure the qubits corresponding to ${S_{j}}$, and then measure the qubits
corresponding to another subset $\overline{S_{j}}$ according to the adjacency
relationship with $S_{j}$. Therefore, a setting
$\prod\limits_{i\in{S_{j}}}{{g_{i}}}$ only needs $O(n)$ local measurement
times.

Figure 2: The two settings corresponding to the graph in Figure 1, where all
red vertices belong to $S_{1}$ and all green vertices belong to $S_{2}$.
(a)(b) are the observables
$\prod\limits_{i\in{S_{1}}}{{g_{i}}},\prod\limits_{i\in{S_{2}}}{{g_{i}}}$
corresponding to $S_{1},S_{2}$ respectively.

###  2.3 Measurement-only blind quantum computation

In MOBQC, the server Bob only needs to prepare the general resource state, and
the client Alice only needs to perform quantum measurement. The protocol steps
are as follows: Bob prepares the general resource state and then sends the
prepared state particles to Alice via quantum channel, then Alice measures the
sent particles on the basis determined by her algorithm. The verification of
this model is generally aimed at the correctness of the resource state. Bob is
often required to prepare multiple copies of the resource state, and some of
which are used for verification and one of the rest is used for calculation,
as shown in Figure 3.

Figure 3: The verification process of MOBQC.

##  3 Public Verifiable Measurement-only Blind Quantum Computation based on
entanglement witnesses

###  3.1 Verification algorithm

Inspired from Xu et al.’s verification mechanismRN15 , we present a
verification algorithm to verify the correctness of the prepared graph state.
Given a target graph state $\left\lvert G\right\rangle$ corresponding to a
$2$-colorable graph $G$, and an unknown state $\varrho$ to be verified. The
two divided subsets of $G$ are denoted as $S_{1},S_{2}$, and the verification
process is shown in Algorithm 1.

Algorithm 1 Verification Algorithm: verify the correctness of the prepared
graph state $\varrho$

1:$2K$ $n$-qubit registers, a required graph state $\left\lvert
G\right\rangle$, and a constant $0\leq C\leq 2K$.

2:The $2K$ registers store the same prepared $n$-qubit state $\varrho$.

3:Select $K$ registers independently, evenly and randomly from $2K$ registers
and mark it as the $1$-st group, then mark the rest $K$ registers as the
$2$-nd group.

4:Measure observable $\prod\limits_{i\in{S_{j}}}{{g_{j}}}$ on each register in
the $j$-th group.

5:Calculate $M_{j}^{\varrho}$ by
$M_{j}^{\varrho}=\prod\limits_{i\in{S_{j}}}{{{{x_{i}}\prod\nolimits_{k\in
N\left(i\right)}{{z_{k}}}+1}\over 2}}$, where $x_{i},z_{j}$ are the results of
measuring observables $X_{i},Z_{j}$, and count the number of registers satisfy
$M_{j}^{\varrho}=0$ as ${K_{j}}$.

6:if ${K_{1}}+{K_{2}}\leq C$ then

7: Accept.

8:else

9: Reject.

10:end if

In Algorithm 1, the condition constant $C$ is determined to make sure the
fidelity between the prepared state $\varrho$ and the required state
$\left\lvert G\right\rangle$ is high enough. Considering the fidelity
estimation process, $C$ isn’t fixed, but varies with the order of the
verifier, i.e., $C$ will be different for the third-party verifier from the
client in our protocol. Therefore, we set $C$ as a pending parameter so as to
ensures the scalability of the verification. Based on the above, Algorithm 1
can be applied to public verification.

###  3.2 Proposed protocol

In Sato et al.’s protocolRN18 , Charlie, the third-party arbiter, can
arbitrate in case of a dispute between the server Bob and the client Alice.
However, the verifier (Charlie) is determined in advance and participates in
the whole process, which isn’t a true third party independent with Bob and
Alice. To achieve a true public verification, i.e., any third party can
participate in verification, we removed Charlie’s role of third-party
verifier, but only retained its storage capacity of quantum state, therefore
it’s renamed the storage center. The third party that participates in the
public verification will be selected from other clients Alice2,
Alice3,$\cdots$, Alicel randomly, where $l$ is the total number of clients. As
shown in Figure 4, there are three parties in the protocol: the server Bob is
responsible for preparing the graph states; the set A = {Alice1,
Alice2,$\cdots$, Alicel} is a set of clients of quantum computation, which are
all legal usersRN22 ; RN23  registered with Charlie; the storage center
Charlie has the ability to store quantum states and is responsible for
distributing the graph states prepared by Bob to the client and selecting the
third-party verifier, and is ensured honesty. When the protocol is executed
between Alice1 and Bob, any other client Alicet in A where
$t\in\\{{\rm{2}},{\rm{}}\ldots{\rm{}},{\rm{}}l\\}$ can perform public
verification.

Figure 4: The tripartite relationship in the proposed protocol.

The graph states used in our protocol all correspond to $2$-colorable graphs.
Taking client Alice1, who has a computing request, as an example, the specific
steps are as follows (also shown in Figure 5):

  1. Step 1

Alice1 sends preparation request to Charlie, then Charlie forwards it to Bob,
where the graph state $\left\lvert G\right\rangle$ requested is an $n$-qubit
state corresponding to a $2$-colorable graph and $n\geq 6$.

  2. Step 2

Bob prepares a $5Kn$-qubit state ${\left\lvert G\right\rangle^{5K}}$,
where$K=\left\lceil{{n^{2}}\log n}\right\rceil,\left\lceil\cdot\right\rceil$
is ceiling function. Then he send it to Charlie one by one qubit.

  3. Step 3

Charlie divides the state sent from Bob into $5K$ $n$-qubit states
$\left\lvert G\right\rangle$ in turn and stores them in $n$-qubit registers
respectively. He selects $2K$ registers independently, evenly and randomly
from these $5K$ registers and keeps them, and then sends the rest $3K$ to
Alice1 in turn.

  4. Step 4

Alice1 divides the states sent from Charlie into $3K$ $n$-qubit registers and
selects $2K$ registers independently, evenly and randomly from them, then
executes Verification Algorithm (see Algorithm 1) where $C={\frac{K}{2n}}$.

  5. Step 5

If it accepts, Alice1 considers Bob honest and proceeds to the next step, and
otherwise considers Bob dishonest and refuses to pay for services.

  6. Step 6

Alice1 randomly selects one register from the remaining $K$ registers and
discards the others, then uses this register to perform MBQC, i.e., measures
particles on the basis determined by her algorithm.

  7. Step 7

If Alice1 claims that Bob is dishonest, Bob can ask Charlie for public
verification, and then Charlie randomly selects a third party Alicet from
Alice2, Alice3,$\cdots$, Alicel to send verification request.

  8. Step 8

If Alicet accepts the request, Charlie sends the $2K$ copies in his hand to
Alicet in turn. According to the graph state type, Alicet executes
Verification Algorithm, where $C=\frac{3K}{4n}$. If it accepts, Alicet claims
that Alice1 is dishonest, otherwise Bob is dishonest.

Figure 5: The process of public verifiable protocol. Solid lines represent
graph states transmission and dotted lines represent requests transmission.

##  4 Performance analysis

###  4.1 Completeness analysis

Completeness means that when Bob faithfully prepares the required graph state,
it must be accepted by Alice1 or Alicet with high probability. In Step 3 of
Algorithm 1, the random variable
$M_{j}^{\varrho}=\prod\limits_{i\in{S_{j}}}{{{{x_{i}}\prod\nolimits_{k\in
N\left(i\right)}{{z_{k}}}+1}\over 2}}\in\left\\{{0,1}\right\\}$ to be
calculated is the measurement result of
$\prod\limits_{i\in{S_{j}}}{{{{g_{i}}+I}\over 2}}$. According to quantum
measurement theory, we have

$\overline{M}_{j}^{\varrho}=Tr\left({\prod\limits_{i\in{S_{j}}}{{{{g_{i}}+I}\over
2}}\varrho}\right),$ (2)

where $\overline{M}_{j}^{\varrho}$ is the mathematical expectation of
$M_{j}^{\varrho}$. Assume Bob prepares the correct state $\varrho=\left\lvert
G\right\rangle\left\langle G\right\lvert$, then we have

$\overline{M}_{j}^{\varrho}=Tr\left({\prod\limits_{i\in
S_{j}}{\frac{g_{i}+I}{2}}\left\lvert G\right\rangle\left\langle
G\right\lvert}\right)=Tr\left(\left\lvert G\right\rangle\left\langle
G\right\lvert\right)=1.$ (3)

We have $M_{j}^{\varrho}\in\\{0,1\\}$, which means for each register
$k\in{\Pi^{\left(j\right)}}$, $M_{j}^{{\varrho_{k}}}=1$, i.e.,${K_{j}}=0$.
Therefore $\forall 0\leq C\leq 2K,{K_{1}}+{K_{2}}\leq C$, i.e., it must be
accepted, leading to the completeness.

###  4.2 Soundness analysis

Soundness means that if Alice1 or Alicet accepts the state $\varrho$ prepared
by Bob, it must close to the graph state required by Alice1 with high
probability. Fidelity $F=\left\langle G\right\lvert\varrho\left\lvert
G\right\rangle$ is generally used to measure the closeness. Fidelity
estimation is based on the following inequality RN15 :

$F\geq\frac{1}{2}-\frac{1}{2}Tr\left({W^{\left(2\right)}\varrho}\right).$ (4)

In our protocol, the expectation
$Tr\left({W^{\left(2\right)}\varrho}\right)$is obtained by measuring the
entanglement witness $W^{\left(2\right)}$ detecting $\left\lvert
G\right\rangle$ to determine whether the state $\varrho$ is close to
$\left\lvert G\right\rangle$, so as to verifies the behavior of Bob. We have
the following theorem about the soundness of our protocol:

######  Theorem 1.

In our protocol,

  1. (1)

When Alicet hasn’t involved in arbitration, if Alice1 measures
${K_{1}}+{K_{2}}\leq\frac{K}{2n}$, then we have

$F\geq 1-{{4\sqrt{\lambda_{1}}+1}\over n}$ (5)

with a probability

$P\geq 1-4n^{-\frac{\lambda_{1}}{2}},$ (6)

where $\lambda_{1}$ is arbitrary constant satisfying
$\log_{n}{16}\leq\lambda_{1}\leq\frac{{\left(n-1\right)}^{2}}{16}$.

  2. (2)

When Alicet involves in arbitration, if Alicet measures
${K_{1}}+{K_{2}}\leq\frac{3K}{4n}$, then we have

$F\geq 1-{{3\sqrt{\lambda_{2}}+1}\over n}$ (7)

with a probability

$P\geq 1-4n^{-\lambda_{2}},$ (8)

where $\lambda_{2}$ is arbitrary constant satisfying
$\log_{n}{4}\leq\lambda_{2}\leq\frac{{\left(n-1\right)}^{2}}{9}$.

Proof: In the theorem, (1) has been proved RN15  and we only need to prove
(2), using some existing probability inequalities. If we perform the $j$-th
measurement setting on the rest $3K$ registers, then for each group of $K$
registers selected by Charlie, we can obtain an upper bound of the number of
registers satisfying $M_{j}^{\varrho}=0$ in the rest $3K$ registers measured
and the relevant confidence probability, Hence, the lower bound of
$\sum\limits_{k=1}^{3K}{M_{1}^{\varrho_{k}}}$ is directly given. We then
obtain a lower bound of $\overline{M}_{1}^{\varrho}$ and the relevant
confidence probability. By Eq. 2 we can obtain a lower bound of
$Tr\left({\prod\limits_{i\in{S_{j}}}{{{{g_{i}}+I}\over 2}}\varrho}\right)$. By
Eq. 1 and Eq. 4, we finally prove that the fidelity $F$ satisfies a lower
bound with a certain confidence probability $P$. See Appendix A for details.

Therefore, if the verification is passed, then the state prepared by Bob is
close to the required graph state with high probability, leading to the
soundness.

In the protocol, $K=O\left({n^{2}}\log n\right)$ so that the probability in
the theorem is $1-O\left({n^{-\lambda}}\right)$ for a constant $\lambda$,
which is high enough; we set $n\geq 6$ so that the above $\lambda$ exists. See
Appendix A for details.

###  4.3 Efficiency analysis

Efficiency refers to the number of copies of the resource state prepared by
the protocol and the number of local measurements required. As mentioned
above, we set $K=O\left({n^{2}}\log n\right)$ so that the probability is high
enough. The detail parameters of our and Sato et al.’s protocolRN18  are shown
in Table 1.

Table 1: The detail parameters of public verifiable MBQC protocols Protocol | Copies numbers | Parameters ranges | Observables measured
---|---|---|---
Sato et al.’s | $\left\lvert G\right\rangle^{2k+m+1}$ |  $k\geq 4{n^{2}}-1$, $m\geq\left({2\ln 2}\right){K^{n}}{n^{5}}$ | $\prod\limits_{i=1}^{n}{g_{i}^{{k_{i}}}}$
Our | ${\left\lvert G\right\rangle^{5K}}$ | $K\geq\left\lceil{{n^{2}}\log n}\right\rceil$ | $\prod\limits_{i\in{S_{j}}}^{n}{{g_{i}}}$
|  |  |

We first consider the number of copies. For the same $n$-qubit graph state
$\left\lvert G\right\rangle$, in Sato et al.’s protocol, the number of copies
is

$\begin{aligned} 2k+m+1&\geq 8{n^{2}}-2+\left({2\ln 2}\right){k^{n}}n+1\\\
&=8{n^{2}}-2+\left({2\ln 2}\right){k^{n}}n+1\\\
&=\Theta\left({{n^{2n+5}}}\right)\end{aligned},$ (9)

i.e., $O\left({{n^{2n+5}}}\right)$ at least; in our protocol it is $5K\geq
5\left\lceil{{n^{2}}\log n}\right\rceil=\Theta\left({{n^{2}}\log n}\right)$,
i.e., $O\left({{n^{2}}\log n}\right)$ at least. Thus our protocol has
advantages.

Then, the number of required local measurement is taken into account. In Sato
et al.’s protocol, they measured stabilizers
$\prod\limits_{i=1}^{n}{g_{i}^{{k_{i}}}}$ on $k$ or $2k$ $n$-qubit graph
states, where $k=\left({{k_{1}}{k_{2}}\ldots{k_{n}}}\right)$ is a string
randomly selected. Considering that the local measurement decomposition of
$\prod\limits_{i=1}^{n}{g_{i}^{{k_{i}}}}$may be complex, and for a specific
graph structure it may be $O\left({{2^{n}}}\right)$RN24 , thus the number of
local measurements is $O\left({kn}\right)=O\left({{n^{2n+5}}{2^{n}}}\right)$;
in our protocol, we measure observables
$\prod\limits_{i\in{S_{j}}}^{n}{{g_{i}}}$ on $2K$ $n$-qubit graph states and
for each graph state the number of the local measurements is $O(n)$ as
mentioned above, thus the total number is
$O\left({Kn}\right)=O\left({{n^{3}}\log n}\right)$. Therefore, our protocol
still has advantages.

##  5 Error propagation and mitigation

It is worth noting that all the above analyses are based on the fact that the
quantum channel does not contain noise. However, the actual channel has a
certain amount of noise, so there must be certain errors in the graph state’s
propagation. Since Bob is not assumed to be honest in our protocol (i.e., the
sent graph state is not guaranteed to be correct), it is impossible to
determine whether the graph state is disturbed by noise by comparing it with
the target state. To mitigate the impact of noise, we have the following two
methods.

(1) Use channel noise detection For each $n$-qubit graph state $\left\lvert
G\right\rangle$, the sender (Bob or Charlie) insert some additional qubits
that are not entangled with the graph state into the $n$ qubits. These qubits’
initial states are agreed in advance by both the sender and the receiver
(Charlie or Alice), and they will be sent together with the graph state as a
whole. In this way, if some noise is encountered during one transmission, the
state of these extra qubits will be changed with a certain probability, and
thus the noise can be detected. If the noise is considered to be too high, the
receiver may reject the communication and request retransmission.

For example, assuming that $k$ additional qubits are in the initial state
$\left\lvert 0\right\rangle$, bit-flip noise occurs in the quantum channel
with probability $p$, and $r$ qubits are flipped to $\left\lvert
1\right\rangle$ after transmission. Since $r$ has a binomial distribution, its
expectation is $kp$. By Azuma-Hoeffding boundRN21  (see Appendix A for
details), $\forall t>0$, we have

$\Pr\left(\left(1-\frac{r}{k}\right)-\left(1-p\right)\leq
t\right)=\Pr\left(p\leq\frac{r}{k}+t\right)\geq 1-\exp\left(-2kt^{2}\right).$
(10)

If $p_{th}$ is the noise threshold, then

$\Pr\left(p\leq p_{th}\right)\geq
1-\exp\left(-2k\left(p_{th}-\frac{r}{k}\right)^{2}\right).$ (11)

Let $1-\exp\left(-2k\left(p_{th}-\frac{r}{k}\right)^{2}\right)\geq 99\%$, then
$r\leq kp_{th}-p\sqrt{k\ln{10}}=r_{th}$. For instance, let $k=5$, $p=1\%$,
then $r_{th}=3.44$. If $r\leq 3$, then we can say $\Pr\left(p\leq
p_{th}\right)\geq 99\%$. The larger the $k$, the smaller the
$\frac{r_{th}-\left\lfloor r_{th}\right\rfloor}{r_{th}}\leq\frac{1}{r_{th}}$,
and the tighter the upper bound. Other noise types can be detected similarly,
and only the corresponding initial states and measurement bases need to be
agreed.

(2) Use fault-tolerant quantum computing (FTQC) As mentioned by Morimae et
al.RN7 , using a computational model that can handle particle losses can
effectively mitigate noise. An $[\\![n,k,d]\\!]$ quantum error-correcting
codes (QECC) encodes $n$ physical qubits into $k$ logical qubits, and a QECC
with distance $d$ can correct up to $\frac{d-1}{2}$ errors on arbitrary
qubitsRN25 . The entanglement of the graph state will not be destroyed in a
qubit stabilizer QECC scheme, because it is not necessary to really know the
initial state of the target qubit, but only to measure and compare the
relative change between the physical qubits. On the other hand, only the
measurements and quantum gates of single-qubit Pauli operators $X,Y,Z$ are
required, which means that even receiver with weak quantum ability can
implement it. In existing fault-tolerant quantum computing, the noise
threshold can even reach $24.9\%$RN26 .

Note that the above two methods can be used in combination because they are
independent of each other. First, the channel noise detection can ensure that
the noise factor is lower than a certain threshold, and then the fault
tolerance mechanism can correct small errors. By using the two methods, the
error caused by channel noise can be mitigated to a certain extent. Of course,
when the noise reaches a certain level, even retransmission will fail.

##  6 Conclusion

In this paper, we proposes a public verifiable measurement-only blind quantum
computation protocol. By introducing a storage center, it allows the third-
party verifier to be any other client randomly selected. Compared with the
previous protocol, our protocol is public verifiable in the true sense. In the
protocol, the fidelity estimation between arbitrary states and graph states
are realized by measuring the entanglement witnesses detecting the graph
states. Without loss of completeness and soundness, the nature of
$2$-colorable graph states reduce the number of local measurements
($O\left(n^{3}\log n\right)$) and the number of copies of the graph states
resources ($O\left(n^{2}\log n\right)$). Compared with the arbitrable protocol
of Sato et al.RN18  (the number of local measurements is $O(n^{2n+5})$ and of
copies of the resource states is $O(n^{2n+5}2^{n})$), our protocol has obvious
advantages. We also consider the communication error and give some error
mitigation schemes.

On the other hand, since we have only considered $2$-colorable graphs, the
proposed protocol is not applicable to arbitrary graph states. For more
general graph states, more research is needed to further improve the
efficiency and performance of existing schemes.

Acknowledgments The authors would like to thank the anonymous reviewers and
editors for their comments that improved the quality of this paper. This work
is supported by the National Natural Science Foundation of China (62071240),
the Innovation Program for Quantum Science and Technology (2021ZD0302902), and
the Priority Academic Program Development of Jiangsu Higher Education
Institutions (PAPD).

##  Appendix A Proof of Theorem 1

In the theorem, (1) has been proved RN15  with a condition $n\geq 6$. Now we
prove (2). At first we introduce the following two probability bounds which
will be used in the analysis, where $\Pr\left(\cdot\right)$ represents the
event probability and $\rm{E}\left(\cdot\right)$ represents the mathematical
expectation:

  1. (1)

Serfling’s boundRN20  Given a set $Y=(Y_{1},Y_{2},...,Y_{T})$ of $T$ binary
random variables with $Y_{k}\in\\{0,1\\}$ and two arbitrary positive integers
$N$ and $K$ that satisfy $T=N+K$, select $K$ samples that are distinguished
from each other independently, evenly and randomly from $Y$, and let $\Pi$ be
the set of these samples, $\overline{\Pi}=Y-\Pi$, then $\forall 0<v<1$, we
have

$\displaystyle\Pr\left({\sum\limits_{k\in\overline{\Pi}}{{Y_{k}}}\leq{N\over
K}\sum\limits_{k\in\Pi}{{Y_{k}}}+Nv}\right)$ (12) $\displaystyle\geq
1-\exp\left({-{{2{v^{2}}N{K^{2}}}\over{\left({N+K}\right)\left({K+1}\right)}}}\right).$

  2. (2)

Azuma-Hoeffding boundRN21  Given independent random variables
${\xi_{1}},{\xi_{2}},\cdots,{\xi_{n}}$ where
${\xi_{i}}\in\left[{{a_{i}},{b_{i}}}\right],i=1,2,\cdots,n$, then $\forall
t>0$, we have

$\displaystyle\Pr\left({{{{\xi_{1}}+{\xi_{2}}+\cdots+{\xi_{n}}}\over
n}-{\rm{E}}\left({{{{\xi_{1}}+{\xi_{2}}+\cdots+{\xi_{n}}}\over n}}\right)\leq
t}\right)$ (13) $\displaystyle\geq
1-\exp\left({-{{2{n^{2}}{t^{2}}}\over{\sum\limits_{i=1}^{n}{\left({{b_{i}}-{a_{i}}}\right)}}}}\right).$

For the first $K$ registers selected, we denote them as $\Pi^{(1)}$ and the
rest $4K$ as $\overline{\Pi}^{(1)}$. Let
$T=5K,N=4K,Y_{k}=\left\\{\begin{matrix}0,M_{1}^{\varrho^{\prime}_{k}}=1\\\
1,M_{1}^{\varrho^{\prime}_{k}}=0\end{matrix}\right.$, where
$\varrho^{\prime}_{k}$ is the state in the $k$-th register in $\Pi^{(1)}$ or
$\overline{\Pi}^{(1)}$, then we have

$\Pr\left({\sum\limits_{k\in{{\overline{\Pi}}^{\left(1\right)}}}{{Y_{k}}}\leq{{4K}\over
K}\sum\limits_{k\in{\Pi^{\left(1\right)}}}{{Y_{k}}}+4Kv}\right)\geq
1-\exp\left({-{{2{v^{2}}4K{K^{2}}}\over{\left({4K+K}\right)\left({K+1}\right)}}}\right)$
(14)

by Eq 12, which means if we perform the $j$-th measurement on the rest $4K$
registers, then the upper bound of the number of the registers satisfying
$M_{1}^{\varrho}=0$ (i.e., ${Y_{k}}=1$) in ${\overline{\Pi}^{\left(1\right)}}$
is $4\sum\limits_{k\in{\Pi^{\left(1\right)}}}{{Y_{k}}}+4Kv$, with the
probability on the right-side of Eq 14. Similarly, for the second $K$
registers selected, we denote them as $\Pi^{(2)}$ and the rest $3K$ as
$\overline{\Pi}^{(2)}$. Let
$T=4K,N=3K,Y_{k}=\left\\{\begin{matrix}{0,M_{2}^{\varrho^{\prime}_{k}}=1}\\\
{1,M_{2}^{\varrho^{\prime}_{k}}=0}\end{matrix}\right.$, where
$\varrho^{\prime}_{k}$ is the state in the $k$-th register in $\Pi^{(2)}$ or
$\overline{\Pi}^{(2)}$, then we have

$\Pr\left({\sum\limits_{k\in{{\overline{\Pi}}^{2}}}{{Y_{k}}}\leq{{3K}\over
K}\sum\limits_{k\in{\Pi^{2}}}{{Y_{k}}}+3Kv}\right)\geq
1-\exp\left({-{{2{v^{2}}3K{K^{2}}}\over{\left({3K+K}\right)\left({K+1}\right)}}}\right),$
(15)

which means if we perform the $j$-th measurement on the rest $3K$ registers,
then the upper bound of the number of the registers satisfying
$M_{2}^{\varrho}=0$ in ${\overline{\Pi}^{\left(2\right)}}$ is
$4\sum\limits_{k\in{\Pi^{\left(2\right)}}}{{Y_{k}}}+4Kv$, with the probability
on the right-side of Eq 15. In the protocol, any two clients do not trust each
other, thus it can be considered that the rest $3K$ registers haven’t been
measured. If we perform the first measurement on the rest $3K$ registers,
there will be
$3K-\left({4\sum\limits_{k\in{\Pi^{\left(1\right)}}}{{Y_{k}}}+4Kv}\right)$
registers satisfying $M_{1}^{\varrho}=1$ at least, i.e.,

$\sum\limits_{k=1}^{3K}{M_{1}^{{\varrho_{k}}}}\geq
3K-\left({4\sum\limits_{k\in{\Pi^{\left(1\right)}}}{{Y_{k}}}+4Kv}\right).$
(16)

Similarly, we have

$\sum\limits_{k=1}^{3K}{M_{2}^{{\varrho_{k}}}}\geq
3K-\left({3\sum\limits_{k\in{\Pi^{\left(2\right)}}}{{Y_{k}}}+3Kv}\right).$
(17)

Let $n=3K,\xi_{k}=M_{1}^{\varrho}$ or $M_{2}^{\varrho}$, then by Eq 13 we have

$\Pr\left({{1\over{3K}}\sum\limits_{k=1}^{3K}{M_{1}^{{\varrho_{k}}}}-\overline{M}_{1}^{\varrho}\leq
t}\right)\geq 1-\exp\left({-2\cdot 3K{t^{2}}}\right).$ (18)

By $Tr\left({\prod\limits_{i\in{S_{1}}}{{{{g_{i}}+I}\over
2}}\varrho}\right)=\overline{M}_{1}^{\varrho}$ and Eq 16 we have

$\begin{aligned}
&\Pr\left({Tr\left({\prod\limits_{i\in{S_{1}}}{{{{g_{i}}+I}\over
2}}\varrho}\right)>1-{1\over{3K}}\left({4\sum\limits_{k\in{\Pi^{\left(1\right)}}}{{Y_{k}}}+4Kv}\right)-t}\right)\\\
&\geq 1-\exp\left({-6K{t^{2}}}\right)\end{aligned},$ (19)

and similarly we have

$\begin{aligned}
&\Pr\left({Tr\left({\prod\limits_{i\in{S_{2}}}{{{{g_{i}}+I}\over
2}}\varrho}\right)>1-{1\over{3K}}\left({3\sum\limits_{k\in{\Pi^{\left(2\right)}}}{{Y_{k}}}+3Kv}\right)-t}\right)\\\
&\geq 1-\exp\left({-6K{t^{2}}}\right)\end{aligned}.$ (20)

Therefore, we have

$\displaystyle F\geq{1\over 2}-{1\over
2}Tr\left({{W^{\left(2\right)}}\varrho}\right)$ (21) $\displaystyle={1\over
2}-{1\over 2}Tr\left({3I\varrho}\right)+{1\over
2}Tr\left({2\prod\limits_{i\in{S_{1}}}{{{{g_{i}}+I}\over
2}\varrho}}\right)+Tr\left({2\prod\limits_{i\in{S_{2}}}{{{{g_{i}}+I}\over
2}\varrho}}\right)$
$\displaystyle=-1+1-{1\over{AK}}\left({4\sum\limits_{k\in{\Pi^{\left(1\right)}}}{{Y_{k}}}+4Kv}\right)-t+1-{1\over{3K}}\left({3\sum\limits_{k\in{\Pi^{\left(2\right)}}}{{Y_{k}}}+3Kv}\right)-t$
$\displaystyle=1-\left({2+{1\over
3}}\right)v-2t-{1\over{3K}}\left({4\sum\limits_{k\in{\Pi^{\left(1\right)}}}{{Y_{k}}}+3\sum\limits_{k\in{\Pi^{\left(2\right)}}}{{Y_{k}}}}\right)$
$\displaystyle\geq 1-\left({2+{1\over
3}}\right)v-2t-{4\over{3K}}\left({\sum\limits_{k\in{\Pi^{\left(1\right)}}}{{Y_{k}}}+\sum\limits_{k\in{\Pi^{\left(2\right)}}}{{Y_{k}}}}\right)$
$\displaystyle=1-\left({2+{1\over
3}}\right)v-2t-{4\over{3K}}\left({{K_{1}}+{K_{2}}}\right).$

with a probability

$\begin{aligned}
&P\geq\left[{1-\exp\left({-{{8{v^{2}}K}\over{5\left({1+{1\over
K}}\right)}}}\right)}\right]\left[{1-\exp\left({-{{3{v^{2}}K}\over{2\left({1+{1\over
K}}\right)}}}\right)}\right]{\left[{1-\exp\left({-6K{t^{2}}}\right)}\right]^{2}}\\\
&\geq{\left[{1-\exp\left({-K{v^{2}}}\right)}\right]^{2}}{\left[{1-\exp\left({-6K{t^{2}}}\right)}\right]^{2}}\end{aligned},$
(22)

where the second inequality in Eq 22 holds as long as $K\geq 2$. Obviously
$\sum\limits_{k\in{\Pi^{\left(1\right)}}}{{Y_{k}}}={K_{1}}$ and
$\sum\limits_{k\in{\Pi^{\left(2\right)}}}{{Y_{k}}}={K_{2}}$ in Eq 21. To make
$F=\left\langle G\right\lvert\rho\left\lvert G\right\rangle$ is
$1-O\left({{1\over n}}\right)$, which is high enough, we need that
$v=O\left({{1\over n}}\right),t=O\left({{1\over
n}}\right),{4\over{3K}}\left({{K_{1}}+{K_{2}}}\right)\leq{1\over n}$ which
leads to $F=1-O\left({{1\over n}}\right)$. Therefore, we set
$v={{\sqrt{{\lambda_{2}}}}\over
n},t={{\sqrt{{\lambda_{2}}}}\over{\sqrt{6}n}}$, then consider the acceptance
condition ${K_{1}}+{K_{2}}\leq{{3K}\over{4n}}$ in Algorithm 1, we have

$F\geq 1-{7\over 3}{{\sqrt{{\lambda_{2}}}}\over
n}-2{{\sqrt{{\lambda_{2}}}}\over{\sqrt{6}n}}-{1\over n}=1-{{\left({{7\over
3}+{2\over{\sqrt{6}}}}\right)\sqrt{{\lambda_{2}}}+1}\over n}\geq
1-{{3.15\sqrt{{\lambda_{2}}}+1}\over n}$ (23)

with a probability

$P\geq{\left[{1-\exp\left({-{{{\lambda_{2}}}\over{{n^{2}}}}K}\right)}\right]^{4}}\geq
1-4\exp\left({-{{{\lambda_{2}}}\over{{n^{2}}}}K}\right)\geq
1-4\exp\left({-{{{\lambda_{2}}}\over{{n^{2}}}}{n^{2}}\log n}\right).$ (24)

To make the probability $P=1-O\left({n^{-\lambda}}\right)$ for a constant
$\lambda$, we set $K=\left\lceil{{n^{2}}\log n}\right\rceil$, then

$P\geq 1-4\exp\left({-{{{\lambda_{2}}}\over{{n^{2}}}}{n^{2}}\log
n}\right)=1-4{n^{-{\lambda_{2}}}},$ (25)

which is high enough. The condition for above $F,P$ both to be positive is
${\log_{n}}4\leq{\lambda_{2}}\leq{{{{\left({n-1}\right)}^{2}}}\over{10}}$,
where $n\geq 5$. When $n\geq 5$, we have
${n^{2}}>{{{{\left({n-1}\right)}^{2}}}\over{10}}$, thus
${\lambda_{2}}<{n^{2}}$, then $v={{\sqrt{{\lambda_{2}}}}\over n}<1$. Consider
the condition of (1), we have $n\geq 6$.

## References

  *   * (1) Childs, A.M.: Secure assisted quantum computation. Quantum Information Computation 5(6), 456–466 (2005)
  * (2) Aharonov, D., Ben-Or, M., Eban, E., Mahadev, U.: Interactive proofs for quantum computations, 1704–04487 (2017)
  * (3) Dupuis, F., Nielsen, J.B., Salvail, L.: Actively secure two-party evaluation of any quantum operation. In: Annual Cryptology Conference, pp. 794–811. Springer
  * (4) Broadbent, A., Gutoski, G., Stebila, D.: Quantum one-time programs. In: Annual Cryptology Conference, pp. 344–360. Springer
  * (5) Broadbent, A.: Delegating private quantum computations. Canadian Journal of Physics 93(9), 941–946 (2015)
  * (6) Broadbent, A., Fitzsimons, J.F., Kashefi, E.: Universal blind quantum computation. In: 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pp. 517–526. IEEE
  * (7) Morimae, T., Fujii, K.: Blind quantum computation protocol in which alice only makes measurements. Physical Review A 87(5), 050301 (2013)
  * (8) Fitzsimons, J.F., Kashefi, E.: Unconditionally verifiable blind quantum computation. Physical Review A 96(1), 012303 (2017)
  * (9) Morimae, T.: Measurement-only verifiable blind quantum computing with quantum input verification. Physical Review A 94(4), 042301 (2016)
  * (10) Fujii, K., Hayashi, M.: Verifiable fault tolerance in measurement-based quantum computation. Physical Review A 96(3), 030301 (2017)
  * (11) Hayashi, M., Hajdušek, M.: Self-guaranteed measurement-based quantum computation. Physical Review A 97(5), 052308 (2018)
  * (12) Takeuchi, Y., Morimae, T.: Verification of many-qubit states. Physical Review X 8(2), 021060 (2018)
  * (13) Takeuchi, Y., Mantri, A., Morimae, T., Mizutani, A., Fitzsimons, J.F.: Resource-efficient verification of quantum computing using serfling’s bound. npj Quantum Information 5(1), 1–8 (2019)
  * (14) Hayashi, M., Morimae, T.: Verifiable measurement-only blind quantum computing with stabilizer testing. Physical review letters 115(22), 220502 (2015)
  * (15) Xu, Q.S., Tan, X.Q., Huang, R., Li, M.Q.: Verification of blind quantum computation with entanglement witnesses. Physical Review A 104(4), 042412 (2021)
  * (16) Honda, K.: Publicly verifiable blind quantum computation (2016)
  * (17) Sato, G., Koshiba, T., Morimae, T.: Arbitrable blind quantum computation. Quantum Information Processing 18(12), 1–8 (2019)
  * (18) Gühne, O., Tóth, G.: Entanglement detection. Physics Reports 474(1-6), 1–75 (2009)
  * (19) Raussendorf, R., Harrington, J., Goyal, K.: Topological fault-tolerance in cluster state quantum computation. New Journal of Physics 9(6), 199 (2007)
  * (20) Shan, R.T., Chen, X.B., Yuan, K.G.: Multi-party blind quantum computation protocol with mutual authentication in network. Science China Information Sciences 64(6), 1–14 (2021)
  * (21) Li, Q., Li, Z.L., Chan, W.H., Zhang, S.Y., Liu, C.D.: Blind quantum computation with identity authentication. Physics Letters A 382(14), 938–941 (2018)
  * (22) Gühne, O., Hyllus, P.: Investigating three qubit entanglement with local measurements. International Journal of Theoretical Physics 42(5), 1001–1013 (2003)
  * (23) Hoeffding, W.: Probability inequalities for sums of bounded random variables, vol. 58, p. 13 (1963)
  * (24) Lidar, D.A., Brun, T.A.: Quantum Error Correction. Cambridge, UK, Boston (2013)
  * (25) Barrett, S.D., Stace, T.M.: Fault tolerant quantum computation with very high threshold for loss errors. Physical Review Letters 105(20), 200502 (2010)
  * (26) Serfling, R.J.: Probability inequalities for the sum in sampling without replacement. The Annals of Statistics, 39–48 (1974)