We introduce a simple protocol for verifiable measurement-only blind quantum computing. Alice, a client, can perform only single-qubit measurements, whereas Bob, a server, can generate and store entangled many-qubit states. Bob generates copies of a graph state, which is a universal resource state for measurement-based quantum computing, and sends Alice each qubit of them one by one. Alice adaptively measures each qubit according to her program. If Bob is honest, he generates the correct graph state, and therefore Alice can obtain the correct computation result. Regarding the security, whatever Bob does, Bob cannot learn any information about Alice's computation because of the no-signaling principle. Furthermore, malicious Bob does not necessarily send the copies of the correct graph state, but Alice can check the correctness of Bob's state by directly verifying stabilizers of some copies. Blind quantum computing is a quantum cryptographic protocol that enables Alice (a client), who does not have any sophisticated quantum technology, to delegate her quantum computing to Bob (a server), who has a sufficiently powerful quantum computer, without leaking any her privacy. The first protocol of blind quantum computing that uses the measurement-based quantum computing [1] was proposed by Broadbent, Fitzsimons, and Kashefi [2], and a proof-of-principle experiment was demonstrated with photonic qubits [3] . In the protocol of Ref. [2] , Alice generates many randomly-rotated singlequbit states, and sends them to Bob. Bob generates a universal resource state of the measurement-based quantum computing by applying entangling gates on qubits sent from Alice. Then, they do two-way classical communications: Alice instructs Bob how to measure each qubit, and Bob returns measurement results so that Alice can perform the feed-forward calculations. It was shown in Ref. [2] that if Bob is honest, Alice can obtain the correct quantum computing result (which we call the correctness), and that whatever evil Bob does, he cannot learn anything about Alice's input, output, and program (which we call the blindness) [4] . (See also Ref. [5] for a precise proof of the security.) Inspired by the seminal result, plenty of improvements have been done [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] . For example, it was shown that instead of single-qubit states generation, single-qubit measurements [6] or coherent states generation [7] are sufficient for Alice. In the protocol of Ref. [6] , so called the measurement-only blind quantum computing, Bob generates a universal resource state of measurement-based quantum computing (Fig 1(a) ), and sends each qubit of the resource state one by one to Alice (Fig. 1(b) ). Alice adaptively measures each qubit according to her program ( Fig. 1(b) ). Since adaptive single-qubit measurements on certain states are universal [1, [21] [22] [23] , Alice with only single-qubit measurements ability can perform universal quantum computing if Bob prepares the correct resource state. Furthermore, since this protocol is a one-way quantum communication from Bob to Alice, the blindness is guaranteed by the nosignaling principle [6] . Here, the no-signaling principle is one of the most fundamental assumptions in physics, which says that if Alice and Bob share a system she cannot transmit any her message to Bob whatever they do on their systems. Quantum physics respects the no-signaling principle. In addition to the correctness and the blindness, the verifiability is another important requirement for blind quantum computing. The verifiability means that Alice can check the correctness of Bob's computation. Although the blindness guarantees that Alice's privacy is kept secret against malicious Bob, it does not guarantee the correctness of the computation result with malicious Bob: Bob cannot learn Alice's secret, but he can mess up the computation. In order to avoid being palmed off a wrong result, Alice needs some statistical test to verify the correctness of Bob's computing. There are several protocols that enable verifiable blind quantum computing [8-11, 24, 25]. Some of them [9, 24, 25] elegantly achieve the completely classical client, but a trade-off is the requirement of more than two servers who do not communicate with each other. Although pursuing the completely classical client is an important direction, in particular, for the goal of constructing an interactive proof of BQP, where the assumption of noncommunicating multi provers is natural, in this paper we restrict ourselves to the single-server setup assuming some minimum quantum technologies for the client, since in the context of blind quantum computing, as-2 suming some minimum quantum technologies for the client is more realistic than to assume that the client can verify that remote servers are not communicating with each other. These results also achieve the device independence. Although our protocol assumes the correctness of measurement devices, it enables to derive a more practical bound suitable for experiments. Protocols in Refs. [8, 10, 11] need only a single server by assuming some minimum quantum technologies, which are available in today's laboratories, for the client. (The protocol of Ref. [10] requires single-qubit states generations, and those of Refs. [8, 11] require single-qubit measurements for the client.) The idea of the verification in the protocols of Refs. [8] [9] [10] [11] is to use trap qubits: Alice secretly hides trap qubits in the resource state, and any disturbance of a trap signals Bob's dishonesty [8] [9] [10] [11] . An experimental demonstration of the idea was done with photonic qubits [26] . In this paper, we propose another protocol for verifiable measurement-only blind quantum computing. The blindness is again guaranteed by the no-signaling principle like Ref. [6] . The verifiability is, on the other hand, achieved in a more straightforward way: instead of hiding traps, Alice directly checks whether the state sent from Bob is correct or not by testing stabilizers [27]. Alice asks Bob to generate 2k + 1 copies |G ⊗2k+1 of the graph state |G , where |G is an n-qubit graph state and k = poly(n). The graph state |G is defined by |G ≡ e∈E CZ e |+ ⊗n , where |+ ≡ , E is the set of edges of G, and CZ e is the Controlled-Z gate, CZ ≡ |0 0|⊗ I + |1 1|⊗ Z, acting on the pair of vertices sharing the edge e. The graph state |G has the stabilizers X j i∈N (j) Z i , for j = 1, 2, ..., n, where N (j) is the set of the vertices connected to j. Alice uses randomly chosen 2k copies of |G ⊗2k+1 to check stabilizers, and the rest of it for her computation. If Bob is honest, he generates |G ⊗2k+1 , and in this case we will show that she passes the test with probability 1. If Bob is evil, on the other hand, he might generate another n(2k + 1)-qubit state. However, we will show that if she passes the test, the closeness of the single copy to the correct graph state |G is guaranteed with a sufficiently small significance level. Any graph state can be used for our protocol as long as the corresponding graph G is bipartite. Therefore, for example, Alice can perform the fault-tolerant topological measurement-based quantum computing [21] by taking |G as the Raussendorf-Harrington-Goyal lattice [21] (Fig. 2(a) ). Note that there are several proposals for testing quantum gate operations [30, 31] , but testing quantum circuit models assumes the identical and independent properties of each gate, and suffers from the scalability and complexity of the analysis. On the other hand, our result in the present paper (and Ref. [25]) demonstrate that testing quantum computing becomes much easier if we consider a measurement-based quantum computing model, which is a new interesting advantage of the measurement-based quantum computing model over the circuit model. For more details about the relations between our result and previous works, see Appendix. Protocol.-Our protocol runs as follows: 1. Honest Bob generates |G ⊗2k+1 , where |G is an n-qubit graph state on a bipartite graph G, whose vertices are divided into two disjoint sets W and B. (Fig. 2(a) and (b) .) Bob sends each qubit of it one by one to Alice. Evil Bob can generate any n(2k + 1)-qubit state ρ instead of |G ⊗2k+1 . 2. Alice divides 2k + 1 blocks of n qubits into three groups by random choice. (Fig. 2(c) .) The first group consists of k blocks of n qubits. The second group consists of k blocks of n qubits. The third group consists of a single block of n qubits. 3. Alice uses the third group for her computation. Other blocks are used for the test, which will be explained later. (Fig. 2(c) For each block of the first and second groups, Alice performs the following test: 1. For each block of the first group, Alice measures qubits of W in the Z basis and qubits of B in the X basis. (Fig. 3(a) .) 2. For each block of the second group, Alice measures qubits of B in the Z basis and qubits of W in the X basis. (Fig. 3(b) .) 3. If the measurement outcomes in the X basis coincide with the values predicted from the outcomes in the Z basis (in terms of the stabilizer relations), 3 then the test is passed. If any outcome in the X basis that violates the stabilizer relations is obtained, Alice rejects. Analysis.-Let us analyze the correctness, blindness, and verifiability of our protocol. First, our protocol is a one-way quantum communication from Bob to Alice, and therefore, the blindness is guaranteed by the no-signaling principle as in the protocol of Ref. [6] . Second, it is obvious that if ρ = |G G| ⊗2k+1 , then Alice passes the test with probability 1. Therefore, if Bob is honest, Alice passes the test with probability 1 and she obtains the correct computation result on the third group. Hence the correctness is satisfied. Finally, to study the verifiability, we consider the following theorem: . (1) (Note that the significance level is the maximum passing probability when malicious Bob sends incorrect states so that the resultant state σ does not satisfy (1) [28] .) The proof of the theorem is given below and in Appendix. From the theorem and the relation between the fidelity and trace norm [32, (6.106)], we can conclude the verifiability: If Alice passes the test, she can guarantee for any POVM C with the significance level α. If we take α = , for example, the left-hand side of the above inequality is 1 (2k+1) 1/4 → 0 if k → ∞, and therefore the verifiability is satisfied. Note that the lower bound, α > 1 2k+1 , of the significance level α is tight, since if Bob generates 2k copies of the correct state |G and a single copy of a wrong state, Bob can fool Alice with probability 1. By considering an appropriate subspace, we can reduce the problem to the test of a maximallyentangled state. 2. For the test of a maximally-entangled state, verifications of coincidences of X measurement results with Z measurement results are sufficient. Furthermore, since we are interested in the fidelity between the given state and a maximally-entangled state, we can consider, without loss of generality, the discretely twirled version of the given state, which drastically simplifies the problem [29] . 3. Finally, since we check the coincidence or discrepancy of the measurement results between two parties of the given bipartite cut, we have only to consider a distribution on (0, 0), (0, 1), (1, 0), and (1, 1) for each block, and therefore we can reduce the problem to a classical hypothesis testing.  In the following, we regard X Here, we distinguish x and −x so that we can easily extend our analysis to the qudit case. Furthermore, for 2 ) 2k+1 and 2 ) 2k+1 , using the operator . Also, we define W  Thus, the discrete-twirled state . Also, we have Therefore, we have only to consider the discretely twirled version of ρ. Note that the upper subscript of x and z expresses the choice of group, and the lower subscript of x and z expresses the site of the modified graph. Finally, let us explain the third point. Since (W † = ρ and ρ is permutationinvariant, the state ρ is written with a permutation- Then, we define the function f from (F where Here, x i and z i are elements of F although s i is an element of F 2 . We introduce the distributionŝ P ((s 1 , t 1 ) , . . . , (s 2k+1 , t 2k+1 )) on ({0, 1} 2 ) (2k+1) aŝ P := P • f −1 . Once, Bob's operation is given, the values s 1 , . . . , s 2k+1 , t 1 , . . . , t 2k+1 are given as random variables although half of s 1 , . . . , s 2k , t 1 , . . . , t 2k can be observed. To employ the notations of probability theory, we express them using the capital letters as S 1 , . . . , S 2k+1 , T 1 , . . . , T 2k+1 . Hence,P (S i = 0) expresses the probability that the i-th measurement outcome of X basis of B system coincides with the prediction by the i-th measurement outcome of Z basis of W system. So, to show Theorem 1, it is enough to show the following theorem. Similarly,P (T k+i = 0) expresses the probability that the k + i-th measurement outcome of X basis of W system coincides with the prediction by the k + i-th measurement outcome of Z basis of B system. So, to show Theorem 1, it is enough to show the following theorem. Theorem 2 Assume that α > 1 2k+1 . When the distributionP satisfieŝ P (S 2k+1 = T 2k+1 = 0|S j = T k+j = 0 for 1 ≤ j ≤ k) , the probabilityP (S j = T k+j = 0 for 1 ≤ j ≤ k) is upper bounded by α. In this way, we have reduced the problem to the classical hypothesis testing. The proof of Theorem 2 is given in Appendix.
In REF a verification protocol is given where the prover is able to send quantum states back to the verifier which has the capacity to measure them.
Verifiable measurement-only blind quantum computing with stabilizer testing
Phys. Rev. Lett. 115, 220502 (2015)
Physics Medicine