# Oblivious Quantum Computation and Delegated Multiparty Quantum Computation

Masahito Hayashi<EMAIL_ADDRESS><EMAIL_ADDRESS>School of Data
Science, The Chinese University of Hong Kong, Shenzhen, Longgang District,
Shenzhen, 518172, China  International Quantum Academy (SIQA), Futian
District, Shenzhen 518048, China  Graduate School of Mathematics, Nagoya
University, Chikusa-ku, Nagoya, 464-8602, Japan

###### Abstract

We propose a new concept, oblivious quantum computation, which requires
performing oblivious transfer with respect to the computation outcome of the
quantum computation, where the secrecy of the input qubits and the program to
identify the quantum gates are required. Exploiting quantum teleportation, we
propose a two-server protocol for this task, which realizes an exponential
improvement for the communication complexity over the simple application of
two-server (quantum) oblivious transfer to the sending of the computation
result. Also, we discuss delegated multiparty quantum computation, in which,
several users ask multiparty quantum computation to server(s) only using
classical communications. We propose a two-server protocol for the latter task
as well.

##  I Introduction

Recently, quantum computation attracts much attention from various research
areas. However, exponential improvement by quantum computer is very limited
[1]. This paper focuses on oblivious transfer for computation outcome and
derives an exponential improvement for this task because oblivious transfer is
a cryptographic primitive task. Consider that the servers have a secret
computer program $\bm{w}$, and the user wants its computation outcome
$f_{\bm{w}}(\bm{k})$ only with a specific input $\bm{k}\in\mathbb{Z}_{2}^{n}$,
where $f_{\bm{w}}$ is the function based on the computer program $\bm{w}$. In
this case, the user wants to hide the input $\bm{k}\in\mathbb{Z}_{2}^{n}$, and
the servers want to hide the program $\bm{w}$, i.e., want to keep its
information except for the computation outcome $f_{\bm{w}}(\bm{k})$.

If they employ oblivious transfer [2], this task can be realized while
oblivious transfer is often called symmetric information retrieval [3].
Although one-server oblivious transfer is impossible information-theoretically
[4, 5], it is information-theoretically possible with two servers if they
share random numbers or entangled states. However, even when we employ quantum
communication, information-theoretically secure oblivious transfer requires
linear communication size with respect to the number of possible inputs [6,
7]. Although the papers [8] proposed its efficient quantum protocol, it works
well when the number of possible choices by the user is fixed and only the
size of each message increases. That is, the protocol [8] does not work in
this case. When we apply this method, the required communication complexity is
linear in $2^{n}$ because the input is composed $n$ bits. In addition, in this
scenario, the server(s) need to derive the computation outcomes for all
$2^{n}$ inputs, which requires exponential computation time.

In this paper, to realize its exponential improvement, we propose a new
conceptual task, oblivious quantum computation (OQC), and a concrete protocol
to realize this task with two servers, which is called a two-server OQC (TOQC)
protocol. Exploiting quantum teleportation [9], our TOQC protocol realizes
polynomial complexity by using quantum computation and quantum communication
when the number of servers is two and the computation requires polynomial time
complexity and polynomial space complexity with respect to the input size $n$.
Our protocol can be considered as a quantum computation version of oblivious
transfer as follows.

Consider that the servers have a secret program $\bm{w}$ to realize unitary
operation $W(\bm{w})$ on $n$ qubits, and the user wants a specific subsystem
of the output state $W(\bm{w})|\psi\rangle$ only with a specific input state
$|\psi\rangle\in{\cal H}^{\otimes n}$, where ${\cal H}$ is one qubit system
$\mathbb{C}^{2}$. Then, the user wants to hide the input state
$|\psi\rangle\in{\cal H}^{\otimes n}$, and the servers want to hide the
program $\bm{w}$, i.e., want to keep its information except for the output
state $W(\bm{w})|\psi\rangle$. We call the above task oblivious quantum
computation. This task can be considered as a kind of secure quantum
computation. When our unitary $W(\bm{w})$ is given as a combination of the
controlled Z operation, a modification of the Hadamard gate, and the
$1/8$-phase gate $\mathsf{T}$ on the input qubits system ${\cal H}^{\otimes
n}$, which forms a universal gate set, we propose an efficient protocol for
this task with two servers. When the number of quantum gates is $m$, several
prior entangled states are prepared between the two servers, and both servers
are not allowed to communicate with each other, the communication complexity
of our protocol is upper bounded by $(2n^{2}+20n)m$ bits plus $2n$ qubits.
Hence, when the number of quantum circuits is polynomial for the input qubit
length $n$, the communication complexity of our protocol is polynomial. When
the classical computation $f_{\bm{w}}(\bm{k})$ can be realized by quantum
computation with polynomial computation space and polynomial number of quantum
gates, our protocol offers an exponential improvement over simple application
of oblivious transfer with multiple servers [6, 7, 8, 10, 11]. In fact, since
our protocol has no information leakage, it has stronger secrecy than cheat-
sensitive secrecy given by [12].

In addition, we discuss delegated multiparty quantum computation, in which,
several users ask multiparty quantum computation to server(s) only by using
classical communications. The conventional delegated quantum computation [13,
14, 15, 16, 17, 18, 19, 20, 21, 22] realizes single-user computation with the
blindness condition. The delegated multiparty quantum computation requires the
servers to realize secure multiparty computation [23, 24, 25] with the
blindness condition. In this problem setting, it is required that a user
cannot obtain any information for other users except for the computation
outcome. Although the paper [26] proposed a similar problem, it allows the
users to use single qubit operations and quantum communications. Further,
combining oblivious quantum computation and delegated multiparty quantum
computation, we propose another new concept, generalized delegated multiparty
quantum computation as a unified concept. This concept contains delegated
multiparty quantum computation and a variant without quantum communication of
oblivious quantum computation as special cases. Since one-server delegated
quantum computation is impossible [27, 28, 29], we propose a two-server
protocol for generalized delegated multiparty quantum computation by modifying
our two-server protocol for oblivious quantum computation.

The remainder of this paper is organized as follows. To explain the key idea
of our protocol, Section II introduces a toy protocol, which explains how
quantum teleportation works for our aim. This idea takes a key role in our
protocols. Section III prepares various notations used in this paper. Using
these notations, Section IV introduces several concepts including the
definitions of the tasks of oblivious quantum computation, delegated
multiparty quantum computation, and generalized delegated multiparty quantum
computation. Section V introduces our protocol for oblivious quantum
computation, and shows its correctness, its user-secrecy, and its server-
secrecy. Section VI describes our protocol for generalized delegated
multiparty quantum computation, and shows its correctness, its user-secrecy,
and its server-secrecy. Finally, Section VII gives the conclusion.

##  II Toy protocol

To explain the basic idea of this paper, we consider a toy protocol, where the
random Pauli operation works as masking the input quantum state, and quantum
teleportation works as state transfer. For this aim, we define the flip
operator $\mathsf{X}$, the phase gate $\mathsf{Z}$, and $1/8$-phase gate
$\mathsf{T}$ as

$\displaystyle\mathsf{X}:=\left(\begin{array}[]{cc}0&1\\\
1&0\end{array}\right),\quad\mathsf{Z}:=\left(\begin{array}[]{cc}1&0\\\
0&-1\end{array}\right),\quad\mathsf{T}:=\left(\begin{array}[]{cc}1&0\\\
0&e^{i\pi/4}\end{array}\right).$ (7)

Then, we consider the case when the secret unitary is given as
$\mathsf{T}^{y}$ on a single qubit with $y\in\mathbb{Z}_{8}$. The user wants
the output state $\mathsf{T}^{y}|\psi\rangle$ only with a specific input state
$|\psi\rangle\in{\cal H}$, but the user wants to hide the input state
$|\psi\rangle\in{\cal H}$. In contrast, the servers want to hide the
information $y\in\mathbb{Z}_{8}$, i.e., the user obtains no other information
for the output state $\mathsf{T}^{y}|\psi\rangle$. This task can be realized
as follows when both servers are not allowed to communicate with each other.

######  Protocol 1 (Toy protocol).

The following protocol realizes the above task.

0)

Preparation: Servers A and B share the entangled state
$|\Phi\rangle=\frac{1}{\sqrt{2}}(|0\rangle|0\rangle+|1\rangle|1\rangle)\in{\cal
H}_{A}\otimes{\cal H}_{B}$.

1)

Query 1: The user generates a quantum state $|\psi\rangle\in{\cal H}$ and
random bits $A_{0},B_{0}\in\mathbb{Z}_{2}$ and random variables
$Q_{u}\in\mathbb{Z}_{8}$ for $u\in\mathbb{Z}_{2}$ according to the uniform
distribution. The user applies $\mathsf{Z}^{B_{0}}\mathsf{X}^{A_{0}}$, and
obtains the state $\mathsf{Z}^{B_{0}}\mathsf{X}^{A_{0}}|\psi\rangle\in{\cal
H}$. Then, the user sends $Q_{u}$ and the system ${\cal H}$ to Server A.

2)

Answer 1: Server A applies the unitary
$\mathsf{T}^{Q_{0}y}(\mathsf{X}\mathsf{T}^{Q_{1}y}\mathsf{X})$ to ${\cal H}$.
Server A applies the Bell measurement
$\\{|\Phi_{a,b}\rangle\\}_{a,b\in\mathbb{Z}_{2}}$ on ${\cal H}\otimes{\cal
H}_{A}$, where $|\Phi_{a,b}\rangle:=(\mathsf{X}^{a}\mathsf{Z}^{b})\otimes
I|\Phi\rangle$. Then, Server A obtains the outcome $(A_{1},B_{1})$ and sends
it to the user.

3)

Query 2: The user generates random bits $Q_{u}^{\prime}\in\mathbb{Z}_{8}$ as

$\displaystyle Q_{A_{0}+A_{1}}^{\prime}:=-Q_{A_{0}}+1,\quad
Q_{A_{0}+A_{1}+1}^{\prime}:=-Q_{A_{0}+1},$ (8)

and sends them to Server B.

4)

Answer 2: Server B applies the unitary
$\mathsf{T}^{Q_{0}^{\prime}y}(\mathsf{X}\mathsf{T}^{Q_{1}^{\prime}y}\mathsf{X})$
to ${\cal H}_{B}$ and sends ${\cal H}_{B}$ to the user.

5)

Construction: The user applies
$\mathsf{Z}^{B_{0}+B_{1}}\mathsf{X}^{A_{0}+A_{1}}$ to the received state.

The correctness of the above protocol can be shown as follow. Assume that the
user and both servers are honest. Then, the final state is calculated as

$\displaystyle\mathsf{Z}^{B_{0}+B_{1}}\mathsf{X}^{A_{0}+A_{1}}\mathsf{T}^{Q_{0}^{\prime}y}(\mathsf{X}\mathsf{T}^{Q_{1}^{\prime}y}\mathsf{X})\mathsf{X}^{A_{1}}\mathsf{Z}^{B_{1}}$
$\displaystyle\cdot\mathsf{T}^{Q_{0}y}(\mathsf{X}\mathsf{T}^{Q_{1}y}\mathsf{X})\mathsf{Z}^{B_{0}}\mathsf{X}^{A_{0}}|\psi\rangle$
$\displaystyle\doteq$
$\displaystyle\mathsf{X}^{A_{0}+A_{1}}\mathsf{T}^{Q_{0}^{\prime}y}(\mathsf{X}\mathsf{T}^{Q_{1}^{\prime}y}\mathsf{X})\mathsf{X}^{A_{1}}\mathsf{T}^{Q_{0}y}(\mathsf{X}\mathsf{T}^{Q_{1}y}\mathsf{X})\mathsf{X}^{A_{0}}|\psi\rangle$
$\displaystyle=$
$\displaystyle(\mathsf{X}^{A_{0}+A_{1}}\mathsf{T}^{Q_{0}^{\prime}y}\mathsf{X}^{A_{1}+A_{0}})(\mathsf{X}^{1+A_{1}+A_{0}}\mathsf{T}^{Q_{1}^{\prime}y}\mathsf{X}^{1+A_{1}+A_{0}})$
$\displaystyle\cdot(\mathsf{X}^{A_{0}}\mathsf{T}^{Q_{0}y}\mathsf{X}^{A_{0}})(\mathsf{X}^{1+A_{0}}\mathsf{T}^{Q_{1}y}\mathsf{X}^{1+A_{0}})|\psi\rangle$
$\displaystyle=$
$\displaystyle\mathsf{T}^{Q_{A_{0}+A_{1}}^{\prime}y}(\mathsf{X}\mathsf{T}^{Q_{1+A_{1}+A_{0}}^{\prime}y}\mathsf{X})\cdot\mathsf{T}^{Q_{A_{0}}y}(\mathsf{X}\mathsf{T}^{Q_{1+A_{0}}y}\mathsf{X})|\psi\rangle$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}$
$\displaystyle\mathsf{T}^{y}|\psi\rangle,$ (9)

where $(a)$ follows from (8). Here, $\doteq$ means the equal with a certain
phase factor.

Assume that the user is honest, and Servers A and B do not communicate with
each other. Server A receives only the system ${\cal H}$ and the variables
$Q_{0},Q_{1}$. The variables $Q_{0},Q_{1}$ are subject to the uniform
distribution independently of $|\psi\rangle$ and $A_{0},B_{0}$. Hence,
$Q_{0},Q_{1}$ have no information for $|\psi\rangle$ and $A_{0},B_{0}$. The
average of the state
$\mathsf{Z}^{B_{0}}\mathsf{X}^{A_{0}}|\psi\rangle\langle\psi|(\mathsf{Z}^{B_{0}}\mathsf{X}^{A_{0}})^{\dagger}$
is the completely mixed state. Hence, Server A has no information for
$|\psi\rangle$. Server B receives only the variables
$Q_{0}^{\prime},Q_{1}^{\prime}$, which are subject to the uniform distribution
independently of $|\psi\rangle$. Server B has no information for
$|\psi\rangle$.

On the other hand, when the servers are honest, the user obtains only one
qubit system. Hence, if the user obtains the desired state
$\mathsf{T}^{y}|\psi\rangle$, the user cannot obtain any other information for
$\mathsf{T}$.

##  III Notation

To explain our problem setting of oblivious quantum computation, we prepare
several notations. First, we define the modified Hadamard gate $\mathsf{H}$ on
a qubit system ${\cal H}$ and the operator $\mathsf{Y}$ as

$\displaystyle\mathsf{Y}:=\mathsf{Z}\mathsf{X},\quad\mathsf{H}:=\frac{1}{\sqrt{2}}\left(\begin{array}[]{cc}1&1\\\
-1&1\end{array}\right).$ (12)

Then, we have the commutation relation
$\mathsf{Y}\mathsf{H}=\mathsf{H}\mathsf{Y}$. The Hadamard gate is given as
$\mathsf{T}^{4}\mathsf{H}$.

Then, we define the controlled $Z$ gate $\mathsf{C_{Z}}$ on a two-qubit system
${\cal H}^{\otimes 2}$ as

$\displaystyle\mathsf{C_{Z}}:=\sum_{j,k\in\mathbb{F}_{2}^{2}}(-1)^{jk}|j,k\rangle\langle
j,k|.$ (13)

It is known that the combination of the controlled NOT gate, the phase gate
$\mathsf{Z}$, $1/8$-phase gate $\mathsf{T}$, and the Hadamard gate
$\mathsf{Z}\mathsf{H}$ forms a universal gate set [30, Section 4.5.3]. Since
the controlled NOT gate is given as a combination of
$\mathsf{C_{Z}},\mathsf{Z},\mathsf{H}$ and the phase gate $\mathsf{Z}$ is
given as $\mathsf{T}^{4}$, the set
$\\{\mathsf{H},\mathsf{T},\mathsf{C_{Z}}\\}$ forms another universal gate set.
To see this fact, we consider operators acting on ${\cal
K}:=\otimes_{s=1}^{n}{\cal H}_{s}$, where the $s$-th system is written as
${\cal H}_{s}$. When the operator $\mathsf{X}$ acts on ${\cal H}_{s}$, it is
written as $\mathsf{X}_{s}$. This rule is applied to other operators. In
addition, the operator $\mathsf{C_{Z}}$ acts on ${\cal H}_{s}\otimes{\cal
H}_{t}$, it is written as $\mathsf{C_{Z}}_{(s,t)}$. The controlled NOT gate
$\mathsf{C_{not}}_{(s,t)}$ on ${\cal H}_{s}\otimes{\cal H}_{t}$ is given as
$|0\rangle\langle 0|_{s}\otimes\mathsf{I}_{t}+|1\rangle\langle
1|_{s}\otimes\mathsf{X}_{t}$. Since
$\mathsf{X}=\mathsf{Z}\mathsf{H}\mathsf{H}=\mathsf{Z}\mathsf{H}\mathsf{Z}\mathsf{Z}\mathsf{H}$
and $\mathsf{I}=\mathsf{Z}\mathsf{H}\mathsf{Z}\mathsf{H}$,

$\displaystyle\mathsf{C_{not}}_{(s,t)}=$
$\displaystyle\mathsf{Z}_{t}\mathsf{H}_{t}(|0\rangle\langle
0|_{s}\otimes\mathsf{I}_{t}+|1\rangle\langle
1|_{s}\otimes\mathsf{Z}_{t})\mathsf{Z}_{t}\mathsf{H}_{t}$ $\displaystyle=$
$\displaystyle\mathsf{Z}_{t}\mathsf{H}_{t}\mathsf{C_{Z}}_{(s,t)}\mathsf{Z}_{t}\mathsf{H}_{t}=\mathsf{T}_{t}^{4}\mathsf{H}_{t}\mathsf{C_{Z}}_{(s,t)}\mathsf{T}_{t}^{4}\mathsf{H}_{t}.$
(14)

Also, since
$-\mathsf{X}=\mathsf{H}\mathsf{H}\mathsf{Z}=\mathsf{H}\mathsf{Z}\mathsf{Z}\mathsf{H}\mathsf{Z}$
and $-\mathsf{I}=\mathsf{H}\mathsf{Z}\mathsf{H}\mathsf{Z}$, we have

$\displaystyle-\mathsf{C_{not}}_{(s,t)}=$
$\displaystyle\mathsf{H}_{t}(|0\rangle\langle
0|_{s}\otimes\mathsf{I}_{t}+|1\rangle\langle
1|_{s}\otimes\mathsf{Z}_{t})\mathsf{Z}_{t}\mathsf{H}_{t}\mathsf{Z}_{t}$
$\displaystyle=$
$\displaystyle\mathsf{H}_{t}\mathsf{C_{Z}}_{(s,t)}\mathsf{T}_{t}^{4}\mathsf{H}_{t}\mathsf{T}_{t}^{4}.$
(15)

In this way, the set $\\{\mathsf{H},\mathsf{T},\mathsf{C_{Z}}\\}$ forms
another universal gate set.

To handle these operators, we define the sets $[n]=\\{1,\ldots,n\\}$ and
$[n]_{2}=\\{(s,t)\\}_{s<t\in[n]}$. For
$\bm{x}=(x_{s})_{s\in[n]}\in\mathbb{Z}_{8}^{n}$ and
$\bm{y}=(y_{s})_{s\in[n]}\in\mathbb{Z}_{8}^{n}$, we define

$\displaystyle\bm{H}(\bm{x}):=\prod_{s\in[n]}\mathsf{H}_{s}(x_{s}),\quad\bm{T}(\bm{y}):=\prod_{s\in[n]}\mathsf{T}_{s}(y_{s}).$
(16)

Here, $\mathsf{H}_{s}(x)$ expresses $\mathsf{H}_{s}^{x}$, and this rule is
applied to other operators. This rule is useful when $x$ has a complicated
form including various indexes.

We define the set
$\mathbb{Z}_{8}^{[n]_{2}}:=\\{(z_{(s,t)})_{(s,t)\in[n]_{2}}\\}$, where
$z_{(s,t)}\in\mathbb{Z}_{8}$. For $\bm{z}\in\mathbb{Z}_{8}^{[n]_{2}}$, we
define

$\displaystyle\bm{C_{Z}}(\bm{z}):=\prod_{(s,t)\in[n]_{2}}\mathsf{C_{Z}}_{(s,t)}(z_{(s,t)}).$
(17)

In particular, we define

$\displaystyle\bm{U}(\bm{x},\bm{y},\bm{z}):=\bm{H}(\bm{x})\bm{T}(\bm{y})\bm{C_{Z}}(\bm{z}).$
(18)

Since the gate set $\\{\mathsf{H},\mathsf{T},\mathsf{C_{Z}}\\}$ is a universal
gate set, universal quantum computation can be performed by unitary operation

$\displaystyle\bm{W}(\bm{w}):=\bm{U}(\bm{x}_{m},\bm{y}_{m},\bm{z}_{m})\cdot\ldots\cdot\bm{U}(\bm{x}_{1},\bm{y}_{1},\bm{z}_{1}),$
(19)

where
$\bm{w}:=((\bm{x}_{m},\bm{y}_{m},\bm{z}_{m}),\ldots,(\bm{x}_{1},\bm{y}_{1},\bm{z}_{1}))$.
Hence, the string $\bm{w}$ can be considered as a program for quantum
computation because it identifies the unitary operation.

Given two programs $\bm{w},\bm{w}^{\prime}$, we define the product
$\bm{w}\cdot\bm{w}^{\prime}$ as
$((\bm{x}_{m}\cdot\bm{x}_{m}^{\prime},\bm{y}_{m}\cdot\bm{y}_{m}^{\prime},\bm{z}_{m}\cdot\bm{z}_{m}^{\prime}),\ldots,(\bm{x}_{1}\cdot\bm{x}_{1}^{\prime},\bm{y}_{1}\cdot\bm{y}_{1}^{\prime},\bm{z}_{1}\cdot\bm{z}_{1}^{\prime}))$,
where $\bm{x}_{j}\cdot\bm{x}_{j}^{\prime}$,
$\bm{y}_{j}\cdot\bm{y}_{j}^{\prime}$, $\bm{z}_{j}\cdot\bm{z}_{j}^{\prime}$ are
defined as $(x_{s}x_{s}^{\prime})_{s\in[n]}$,
$(y_{s}y_{s}^{\prime})_{s\in[n]}$,
$(z_{(s,t)}z_{(s,t)}^{\prime})_{(s,t)\in[n]_{2}}$. When we define
$\bm{e}:=(\underbrace{(1,1,1),\ldots,(1,1,1)}_{m})$, we have
$\bm{e}\cdot\bm{w}^{\prime}=\bm{w}^{\prime}$.

When $m$ is written as $m_{1}+m_{2}$, $\bm{w}$ is divided into two parts. That
is, $\bm{w}$ is written as $(\bm{w}_{1},\bm{w}_{2})$, where
$\bm{w}_{1}:=((\bm{x}_{m_{1}},\bm{y}_{m_{1}},\bm{z}_{m_{1}}),\ldots,(\bm{x}_{1},\bm{y}_{1},\bm{z}_{1}))$
and
$\bm{w}_{2}:=((\bm{x}_{m},\bm{y}_{m},\bm{z}_{m}),\ldots,(\bm{x}_{m_{1}+1},\bm{y}_{m_{1}+1},\bm{z}_{m_{1}+1}))$.
Then, we define

$\displaystyle\bm{W}_{1}(\bm{w}_{1})$
$\displaystyle:=\bm{U}(\bm{x}_{m_{1}},\bm{y}_{m_{1}},\bm{z}_{m_{1}})\cdot\ldots\cdot\bm{U}(\bm{x}_{1},\bm{y}_{1},\bm{z}_{1})$
(20) $\displaystyle\bm{W}_{2}(\bm{w}_{2})$
$\displaystyle:=\bm{U}(\bm{x}_{m},\bm{y}_{m},\bm{z}_{m})\cdot\ldots\cdot\bm{U}(\bm{x}_{m_{1}+1},\bm{y}_{m_{1}+1},\bm{z}_{m_{1}+1}).$
(21)

##  IV Formulations

###  IV.1 Formulation of oblivious quantum computation

The problem setting of oblivious quantum computation is formulated as Fig. 1
with the following definitions of various concepts.

####  IV.1.1 Task

Server(s) have a program
$\bm{w}:=((\bm{x}_{m},\bm{y}_{m},\bm{z}_{m}),\ldots,(\bm{x}_{1},\bm{y}_{1},\bm{z}_{1}))\in(\mathbb{Z}_{4}^{n}\times\mathbb{Z}_{8}^{n}\times\mathbb{Z}_{2}^{[n]_{2}})^{m}$.
When several server(s) exist, they are not allowed to communicate with each
other. While the user does not know it, the server(s) are required to apply
$\bm{W}(\bm{w})$ to the state $|\psi\rangle\in{\cal K}$. The user wants the
first $n_{\circ}$ qubits of the output state
$\bm{W}(\bm{w})|\psi\rangle\in{\cal K}$. We denote the first $n_{\circ}$
qubits of ${\cal K}$ by ${\cal K}_{\circ}$ and the remaining $n-n_{\circ}$
qubits of ${\cal K}$ by ${\cal K}_{\triangle}$. Hence, the user wants the
state $\Phi_{ideal}(\bm{w},|\psi\rangle):=\operatorname{Tr}_{{\cal
K}_{\triangle}}\bm{W}(\bm{w})|\psi\rangle\langle\psi|\bm{W}(\bm{w})^{\dagger}$
on ${\cal K}_{\circ}$. In the following, we use the subscript $\circ$ to
identify the first $n_{\circ}$ systems.

Figure 1: Oblivious quantum computation with two servers. This figure shows a
protocol for oblivious quantum computation with two servers when the two
servers share an entangled state.

####  IV.1.2 Correctness and complexity

An OQC protocol $\Phi$ has two types of inputs. The first input is the program
$\bm{w}\in(\mathbb{Z}_{4}^{n}\times\mathbb{Z}_{8}^{n}\times\mathbb{Z}_{2}^{[n]_{2}})^{m}$.
The second input is the input quantum state $|\psi\rangle\in{\cal K}$. The
output of the protocol is a state $\rho_{out}$ on ${\cal K}$, which is desired
to be $\Phi_{ideal}(\bm{w},|\psi\rangle)$.

An OQC protocol $\Phi$ has bilateral communication. The upload communication
is the communication from the user to the servers, and the download
communication is the communication from the servers to the user.

The communication complexity is composed of the upload complexity and the
download complexity. The upload complexity is the sum of the communication
sizes of all upload communications, and the download complexity is the sum of
the communication sizes of all download communications. The sum of the upload
and download complexity is called the communication complexity. For a OQC
protocol $\Phi$, we denote the output state by
$\Phi_{out}(\bm{w},|\psi\rangle)=\rho_{out}$. The upload complexity, the
download complexity, and the communication complexity are denoted by
$UC(\Phi)$, $DC(\Phi)$, and $CC(\Phi)$, respectively. Hence, the communication
complexity $CC(\Phi)$ is calculated as $UC(\Phi)+DC(\Phi)$.

An OQC protocol $\Phi$ is called correct when the relation
$\Phi_{out}(\bm{w},|\psi\rangle)=\Phi_{ideal}(\bm{w},|\psi\rangle)$ holds for
any state $|\psi\rangle\in{\cal K}$ and
$\bm{w}\in(\mathbb{Z}_{4}^{n}\times\mathbb{Z}_{8}^{n}\times\mathbb{Z}_{2}^{[n]_{2}})^{m}$.

####  IV.1.3 Two types of secrecy

An OQC protocol $\Phi$ has two types of secrecy. One is the user-secrecy, and
the other is the server-secrecy. We say that an OQC protocol $\Phi$ satisfies
the user-secrecy when the following condition holds. To explain the user-
secrecy, for $J=A,B$, we denote the final state on Server $J$ dependently of
the input state $|\psi\rangle$ by $\rho_{Y_{J}||\psi\rangle}$. When the user
is honest, no server obtains the information of the user’s input state
$|\psi\rangle$, i.e., the relation

$\displaystyle\rho_{Y_{J}||\psi\rangle}=\rho_{Y_{J}||\psi^{\prime}\rangle}$
(22)

holds for $J=A,B$ and any states $|\psi\rangle,|\psi^{\prime}\rangle\in{\cal
K}$.

We say that an OQC protocol $\Phi$ satisfies the server-secrecy when the
following condition holds. When the servers are honest and the output state
$\rho_{out}$ equals $\Phi_{ideal}(\bm{w},|\psi\rangle)$, the user obtains no
information for the program
$\bm{w}\in(\mathbb{Z}_{4}^{n}\times\mathbb{Z}_{8}^{n}\mathbb{Z}_{2}^{[n]_{2}})^{m}$
except for the desired output state $\Phi_{ideal}(\bm{w},|\psi\rangle)$, i.e.,
the user can generate the final state on his/her own whole system by using
$\Phi_{ideal}(\bm{w},|\psi\rangle)$, the classical information describing the
initial state $|\psi\rangle$, and classical information generated by
himself/herself.

###  IV.2 Formulation of delegated multiparty quantum computation

The problem setting of delegated multiparty quantum computation (DMQC) is
formulated as Fig. 2 with the following definitions of various concepts.

####  IV.2.1 Task

There are $m+1$ users, Users $1$, $2$, …, $m$, $m+1$, and server(s). When
several server(s) exist, they are not allowed to communicate with each other.
Each user can communicate with both servers via classical channel. Only
server(s) are allowed to make quantum operations.

User $j$ has the $j$-th component
$(\bm{x}_{j},\bm{y}_{j},\bm{z}_{j})\in\mathbb{Z}_{4}^{n}\times\mathbb{Z}_{8}^{n}\times\mathbb{Z}_{2}^{[n]_{2}}$
of the program $\bm{w}$ for $j=1,2,\ldots,m$ while the server(s) do not know
it. The final user $m+1$ aims to get the initial $n_{\circ}$ bits of the
computation outcome when the measurement based on the computation basis is
performed to the state $\bm{W}(\bm{w})|0\rangle^{\otimes n}\in{\cal K}$.

When we apply this general method to a specific function $f$ with $l$ inputs
$X_{1},\ldots,X_{l}$, we consider that there exist $l$ players who have
respective inputs. Then, the $m$ users are divided into $l$ distinct groups.
When the $k$-th group is composed of users with labels in the subset $S_{k}$,
the components $(\bm{x}_{j},\bm{y}_{j},\bm{z}_{j})_{j\in S_{k}}$ are decided
by the choice of the value $X_{k}$. That is, all users in the $k$-th group are
controlled by $k$-th player. When $l$ input variables $X_{1},\ldots,X_{l}$ are
independent of each other, the information possessed by users in the $k$-th
group is independent of the information possessed by users in the
$k^{\prime}$-th group for $k\neq k^{\prime}$.

####  IV.2.2 Example

To see how the above general setting works in specific functions, as an
example, we consider the function $X_{1}+X_{2}+\cdots+X_{l}\in\mathbb{Z}_{2}$,
where each variable $X_{j}$ is an element of $\mathbb{Z}_{2}$. The outcome of
this function can be written as the final state of the following combination
of universal gate set. Consider a two-qubit system ${\cal H}_{1}\otimes{\cal
H}_{2}$.

$\displaystyle|X_{1}+X_{2}+\cdots+X_{l}\rangle_{1}|1\rangle_{2}$
$\displaystyle\doteq$
$\displaystyle(\mathsf{H}_{1}\mathsf{C_{Z}}_{(1,2)}\mathsf{T}_{1}^{4}\mathsf{H}_{1}\mathsf{T}_{1}^{4})^{X_{l}}\cdots(\mathsf{H}_{1}\mathsf{C_{Z}}_{(1,2)}\mathsf{T}_{1}^{4}\mathsf{H}_{1}\mathsf{T}_{1}^{4})^{X_{2}}$
$\displaystyle\cdot(\mathsf{H}_{1}\mathsf{C_{Z}}_{(1,2)}\mathsf{T}_{1}^{4}\mathsf{H}_{1}\mathsf{T}_{1}^{4})^{X_{1}}|0\rangle_{1}|1\rangle_{2}$
$\displaystyle\doteq$
$\displaystyle(\mathsf{H}_{1}\mathsf{C_{Z}}_{(1,2)}\mathsf{T}_{1}^{4}\mathsf{H}_{1}\mathsf{T}_{1}^{4})^{X_{l}}\cdots(\mathsf{H}_{1}\mathsf{C_{Z}}_{(1,2)}\mathsf{T}_{1}^{4}\mathsf{H}_{1}\mathsf{T}_{1}^{4})^{X_{2}}$
$\displaystyle\cdot(\mathsf{H}_{1}\mathsf{C_{Z}}_{(1,2)}\mathsf{T}_{1}^{4}\mathsf{H}_{1}\mathsf{T}_{1}^{4})^{X_{1}}\mathsf{H}^{2}_{2}\mathsf{Z}_{2}|0\rangle_{1}|0\rangle_{2}$
$\displaystyle=$
$\displaystyle\mathsf{H}_{1}^{X_{l}}\mathsf{C_{Z}}_{(1,2)}^{X_{l}}\mathsf{T}_{1}^{4X_{l}}\mathsf{H}_{1}^{X_{l}}\mathsf{T}_{1}^{4X_{l}}\cdots\mathsf{H}_{1}^{X_{2}}\mathsf{C_{Z}}_{(1,2)}^{X_{2}}\mathsf{T}_{1}^{4X_{2}}\mathsf{H}_{1}^{X_{2}}\mathsf{T}_{1}^{4X_{2}}$
$\displaystyle\cdot\mathsf{H}_{1}^{X_{1}}\mathsf{C_{Z}}_{(1,2)}^{X_{1}}\mathsf{T}_{1}^{4X_{1}}\mathsf{H}_{1}^{X_{1}}\mathsf{T}_{1}^{4X_{1}}\mathsf{H}^{2}_{2}\mathsf{T}_{2}^{4}|0\rangle_{1}|0\rangle_{2}.$
(23)

We set $m$ and $n_{\circ}$ to be $2l+1$ and $1$, respectively. The first group
$S_{1}$ is set to be $\\{1,2,3\\}$, and the $k$-th group $S_{k}$ is set to be
$\\{2k,2k+1\\}$ for $k=2,3,\ldots,l$. Since $[2]_{2}$ is composed of one
element $(1,2)$, $\bm{z}_{j}$ is composed of one element of $\mathbb{Z}_{2}$
for $j=1,\ldots,m=2l+1$. Then, the program is chosen as

$\displaystyle(\bm{x}_{1},\bm{y}_{1},\bm{z}_{1})=$
$\displaystyle((0,2),(0,4),0)$ (24)
$\displaystyle(\bm{x}_{2k},\bm{y}_{2k},\bm{z}_{2k})=$
$\displaystyle((X_{k},0),(4X_{k},0),0)$ (25)
$\displaystyle(\bm{x}_{2k+1},\bm{y}_{2k+1},\bm{z}_{2k+1})=$
$\displaystyle((X_{k},0),(4X_{k},0),X_{k})$ (26)

for $k=1,\ldots,l$. The measurement outcome with the computation basis on the
first qubit in the final state is $X_{1}+X_{2}+\cdots+X_{l}\in\mathbb{Z}_{2}$.
Hence, the above choice of the program works for the delegated multiparty
quantum computation of the function
$X_{1}+X_{2}+\cdots+X_{l}\in\mathbb{Z}_{2}$.

Figure 2: Delegated multiparty quantum computation with two servers. This
figure shows a protocol for delegated multiparty quantum computation with two
servers when the two servers share an entangled state.

####  IV.2.3 Correctness and complexity

Since a DMQC protocol $\Phi$ has bilateral communication. The upload
communication is the communication from the users to the server(s), and the
download communication is the communication from the server(s) to the users.
In the same way as OQC, the communication complexity is composed of the upload
complexity and the download complexity.

A DMQC protocol $\Phi$ is called correct when the following condition holds
for any program
$\bm{w}\in(\mathbb{Z}_{4}^{n}\times\mathbb{Z}_{8}^{n}\times\mathbb{Z}_{2}^{[n]_{2}})^{m}$;
The outcome observed by the final user, User $m+1$, is subject to the
distribution of the initial $n_{\circ}$ bits of the measurement outcome of the
computation-basis measurement over the state $\bm{W}(\bm{w})|0\rangle^{\otimes
n}\in{\cal K}$.

####  IV.2.4 Secrecy condition

We require the following secrecy conditions. We choose an arbitrary subset
$\Theta\subset[m]$ as a form $\cup_{k\in\bar{\Theta}}S_{k}$ with
$\bar{\Theta}\subset[l]$. (1) When a set of users $\Theta\subset[m]$ is
honest, server(s) obtain no information for
$\\{(\bm{x}_{j},\bm{y}_{j},\bm{z}_{j})\\}_{j\in\Theta}$. (2) When Server(s)
are honest additionally, User $j^{\prime}$ obtains no information for
$\\{(\bm{x}_{j},\bm{y}_{j},\bm{z}_{j})\\}_{j\in\Theta\setminus\\{j^{\prime}\\}}$
for $j^{\prime}=1,\ldots,m$, and the final user $m+1$ obtains no information
for $\\{(\bm{x}_{j},\bm{y}_{j},\bm{z}_{j})\\}_{j\in\Theta}$ except for the
above computation outcome, i.e., the final user $m+1$ can recover the final
state on his/her own system by using the above computation outcome and
classical information generated by himself/herself. (3) In addition, even when
users in $[m+1]\setminus\Theta$ collude, they obtain no information except for
the above computation outcome. When the above three conditions hold, a DMQC
protocol $\Phi$ is called secure.

######  Remark 1.

The paper [26] studied delegated multiparty quantum computation. But, it
allows the users to use single qubit operations and quantum communications.
Since our delegated multiparty quantum computation does not allow the users to
use single qubit operations nor quantum communications.

In addition, oblivious quantum computation cannot be considered as a special
case of delegated multiparty quantum computation in the sense of our
definition nor in the sense of the definition by the paper [26] because of the
following two reasons. First, the server(s) do not have input data in
delegated multiparty quantum computation, but they have program $\bm{w}$ in
oblivious quantum computation. Second, oblivious quantum computation allows
the user to input a quantum state and to obtain a quantum state as the output,
but delegated multiparty quantum computation does not allow them. Therefore,
oblivious quantum computation can be considered as a new concept.

###  IV.3 Formulation of generalized delegated multiparty quantum computation

Delegated multiparty quantum computation is generalized to generalized
delegated multiparty quantum computation (GDMQC) by combining oblivious
quantum computation as Fig. 3 in the following way.

####  IV.3.1 Task

There are $m+1$ users, Users $1$, $2$, …, $m$, $m+1$, and server(s). When
several server(s) exist, they are not allowed to communicate with each other.
Each user can communicate with both servers via classical channel. Only
server(s) are allowed to make quantum operations. User $j$ has the $j$-th
component $(\bm{x}_{j}^{\prime},\bm{y}_{j}^{\prime},\bm{z}_{j}^{\prime})$ of a
program $\bm{w}^{\prime}$ for $j=1,2,\ldots,m$ while the server(s) do not know
it. Server(s) have another program $\bm{w}$ while the users do not know it.
The final user, User $m+1$, aims to get the initial $n_{\circ}$ bits of the
computation outcome when the measurement based on the computation basis is
performed to the state $\bm{W}(\bm{w}\cdot\bm{w}^{\prime})|0\rangle^{\otimes
n}\in{\cal K}$.

When we apply this general method to a specific function $f$ with $l$ inputs
$X_{1},\ldots,X_{l},X_{l+1}$, we consider that there exist $l$ players who
have respective inputs. Then, the $m$ users are divided into $l$ distinct
groups. When the $k$-th group is composed of users with labels in the subset
$S_{k}$, the components
$(\bm{x}_{j}^{\prime},\bm{y}_{j}^{\prime},\bm{z}_{j}^{\prime})_{j\in S_{k}}$
are decided by the choice of the value $X_{k}$. That is, all users in the
$k$-th group is controlled by $k$-th player. Also, the final variable
$X_{l+1}$ decides Server’s program $\bm{w}$.

Figure 3: Generalized delegated multiparty quantum computation with two
servers. This figure shows a protocol for generalized delegated multiparty
quantum computation with two servers when the two servers share an entangled
state.

####  IV.3.2 Correctness and complexity

For a GDMQC protocol $\Phi$, its upload communication, its download
communication, and its communication complexity are defined in the same way as
a DMQC protocol.

A DMQC protocol $\Phi$ is called correct when the following condition holds
for any program
$\bm{w}\in(\mathbb{Z}_{4}^{n}\times\mathbb{Z}_{8}^{n}\times\mathbb{Z}_{2}^{[n]_{2}})^{m}$;
The outcome observed by the final user, User $m+1$, is subject to the
distribution of the initial $n_{\circ}$ bits of the measurement outcome of the
computation-basis measurement over the state $\bm{W}(\bm{w})|0\rangle^{\otimes
n}\in{\cal K}$.

####  IV.3.3 Two types of secrecy

A GDMQC protocol $\Phi$ has two types of secrecy. One is the user-secrecy and
the other is the server-secrecy. We say that a GDMQC protocol $\Phi$ satisfies
the user-secrecy when the following conditions hold. We choose an arbitrary
subset $\Theta\subset[m]$ as a form $\cup_{k\in\bar{\Theta}}S_{k}$ with
$\bar{\Theta}\subset[l]$. (1) When a set of users $\Theta\subset[m]$ are
honest, server(s) obtain no information for
$\\{(\bm{x}_{j}^{\prime},\bm{y}_{j}^{\prime},\bm{z}_{j}^{\prime})\\}_{j\in\Theta}$.
(2) When Server(s) are honest additionally, User $j^{\prime}$ obtains no
information for
$\\{(\bm{x}_{j}^{\prime},\bm{y}_{j}^{\prime},\bm{z}_{j}^{\prime})\\}_{j\in\Theta\setminus\\{j^{\prime}\\}}$
for $j^{\prime}=1,\ldots,m$. The final user $m+1$ obtains no information for
$\\{(\bm{x}_{j}^{\prime},\bm{y}_{j}^{\prime},\bm{z}_{j}^{\prime})\\}_{j\in\Theta}$
except for the above computation outcome, i.e, the final user $m+1$ can
recover the final state on his/her own system by using the required
computation outcome and classical information generated by himself/herself.
(3) In addition, even when users in $[m+1]\setminus\Theta$ collude, they
obtain no information except for the above computation outcome, i.e., they can
recover the final state on their own system by using the above computation
outcome and classical information generated by themselves.

We say that an OQC protocol $\Phi$ satisfies the server-secrecy when the
following conditions hold. (1) When the server(s) are honest, User $j$ with
$j=1,\ldots,m$ obtains no information for $\bm{w}$, and User $m+1$ obtains no
information for $\bm{w}$ expect to the required computation outcome, i.e.,
User $m+1$ can recover the final state on his/her own system by using the
required computation outcome and classical information generated by
themselves. (2) In addition, when the server(s) are honest, even when all
users collude, the users obtain no information except for the above
computation outcome, i.e., the users can recover the final state on their own
system by using the above computation outcome and classical information
generated by themselves.

####  IV.3.4 Relation to OQC

A special case of GDMQC gives a variant of OQC as follows. We divide $m$
rounds into two parts, the first $m_{1}$ rounds and the remaining $m_{2}$
rounds, where $m=m_{1}+m_{2}$. The first $m_{1}$ components of $\bm{w}$ are
set to be $\bm{e}_{1}:=(\underbrace{(1,1,1),\ldots,(1,1,1)}_{m_{1}})$, and the
remaining $m_{2}$ components of $\bm{w}$ are denoted by $\bm{w}_{2}$ Also, the
first $m_{1}$ components of $\bm{w}^{\prime}$ are denoted by
$\bm{w}_{2}^{\prime}$, and the remaining $m_{2}$ components of
$\bm{w}^{\prime}$ are set to be
$\bm{e}_{2}:=(\underbrace{(1,1,1),\ldots,(1,1,1)}_{m_{2}})$. Also, we assume
that there exists only one user.

In this case, the user decides the state
$\bm{W}_{1}(\bm{w}_{1}^{\prime})|0\rangle^{\otimes n}$, and the servers decide
the unitary $\bm{W}_{2}(\bm{w}_{2})$. Finally, the user obtains the
measurement outcome with the computation basis under the state
$\bm{W}_{2}(\bm{w}_{2})\bm{W}_{1}(\bm{w}_{1}^{\prime})|0\rangle^{\otimes n}$.
When the user’s input state is given as
$\bm{W}_{1}(\bm{w}_{1}^{\prime})|0\rangle^{\otimes n}$ and the user needs only
the measurement outcome with the computation basis in OQC, this requirement
can be done without quantum communication by using a special case of GDMQC.

##  V Main protocol for TOQC

Since oblivious transfer with one server is impossible even with the quantum
setting [4, 5], this section introduces a two-server OQC (TOQC) protocol that
satisfies all the requirements. Then, we introduce the following protocol.

######  Protocol 2 (Main protocol for TOQC).

Severs A and B are not allowed to communicate with each other. The user can
communicate with both servers.

0)

Entanglement Sharing: Servers A and B prepare $2mn$ copies of the Bell state
$|\Phi\rangle$ on ${\cal H}_{A,j,s}\otimes{\cal H}_{B,j,s}$ for $s=1,\ldots,n$
and $j=1,\ldots,2m$.

1)

Query 1: The user generates a quantum state $|\psi\rangle\in{\cal H}^{\otimes
n}=\otimes_{s=1}^{n}{\cal H}_{s}$, and random bits
$A_{0,s},B_{0,s}\in\mathbb{Z}_{2}$ according to the uniform distribution for
$s=1,\ldots,n$, where ${\cal H}_{s}$ is the $s$-th system. The user applies
$\mathsf{Z}_{s}^{B_{0,s}}\mathsf{X}_{s}^{A_{0,s}}$ on ${\cal H}_{s}$, and
obtains the state
$\otimes_{s=1}^{n}\mathsf{Z}_{s}^{B_{0,s}}\mathsf{X}_{s}^{A_{0,s}}|\psi\rangle\in{\cal
H}^{\otimes n}$. Then, the user sends the system ${\cal H}^{\otimes n}$ to
Server A. Also, the user generates
$\bm{Q}_{2,1,u}=(Q_{2,1,u,s})_{s\in[n]}\in\mathbb{Z}_{8}^{n}$ and
$\bm{Q}_{3,1,(u,v)}=(Q_{3,1,(u,v),(s,t)})_{(s,t)\in[n]_{2}}\in\mathbb{Z}_{2}^{[n]_{2}}$
uniformly at random for $(u,v)\in\mathbb{Z}_{2}^{2}$, and sends them to Server
A.

2)

Unitary operation 1: Server A applies unitaries
$\mathsf{X}_{s}^{u}\mathsf{T}_{s}(Q_{2,1,u,s}\bm{y}_{1,s})\mathsf{X}_{s}^{u}$
to ${\cal H}_{s}$ and
$\mathsf{X}_{s}^{u}\mathsf{X}_{t}^{v}\mathsf{C_{Z}}_{(s,t)}(Q_{3,1,(u,v),(s,t)}\bm{z}_{1,(s,t)})\mathsf{X}_{s}^{u}\mathsf{X}_{t}^{v}$
to ${\cal H}_{s}\otimes{\cal H}_{t}$. Server A applies the Bell measurement
$\\{|\Phi_{a,b}\rangle\\}_{a,b\in\mathbb{Z}_{2}}$ on ${\cal H}_{s}\otimes{\cal
H}_{A,1,s}$ for $s=1,\ldots,n$. Then, Server A obtains the outcome
$(A_{1,s},B_{1,s})$ and sends them to the user for $s=1,\ldots,n$. Server A
applies unitary $\mathsf{Z}_{s}^{B_{1,s}}\mathsf{X}_{s}^{A_{1,s}}$ to ${\cal
H}_{A,2,s}$.

3)

Query 2: The user generates
$\bm{Q}_{2,1,u}^{\prime}=(Q_{2,1,u,s}^{\prime})_{s\in[n]}\in\mathbb{Z}_{8}^{n}$
and
$\bm{Q}_{3,1,(u,v)}^{\prime}=(Q_{3,1,(u,v),(s,t)}^{\prime})_{(s,t)\in[n]_{2}}\in\mathbb{Z}_{2}^{[n]_{2}}$
as

$\displaystyle Q_{2,1,u,s}^{\prime}$
$\displaystyle:=-Q_{2,1,u-A_{1,s},s}+\delta_{u,A_{0,s}+A_{1,s}},$ (27)

and

$\displaystyle Q_{3,1,(u,v),(s,t)}^{\prime}$
$\displaystyle:=-Q_{3,1,(u-A_{1,s},v-A_{1,t}),(s,t)}+\delta_{u,A_{0,s}+A_{1,s}}\delta_{v,A_{0,t}+A_{1,t}}.$
(28)

The user generates
$\bm{Q}_{1,1,u}^{\prime}=(Q_{1,1,u,s}^{\prime})_{s\in[n]}\in\mathbb{Z}_{4}^{n}$
according to the uniform distribution. The user sends them to Server B.

4)

Unitary operation 2: (i) Server B applies unitaries
$\mathsf{X}_{s}^{u}\mathsf{T}_{s}(Q_{2,1,u,s}^{\prime}\bm{y}_{1,s})\mathsf{X}_{s}^{u}$
to ${\cal H}_{B,1,s}$ and
$\mathsf{X}_{s}^{u}\mathsf{X}_{t}^{v}\mathsf{C_{Z}}_{(s,t)}(Q_{3,1,(u,v),(s,t)}^{\prime}\bm{z}_{1,(s,t)})\mathsf{X}_{s}^{u}\mathsf{X}_{t}^{v}$
to ${\cal H}_{B,1,s}\otimes{\cal H}_{B,1,t}$ for $(u,v)\in\mathbb{Z}_{2}^{2}$.
(ii) Then, Server B applies unitaries
$\mathsf{X}_{s}^{u}\mathsf{H}_{s}(Q_{1,1,u,s}^{\prime}\bm{y}_{1,s})\mathsf{X}_{s}^{u}$
to ${\cal H}_{B,1,s}$ for $u\in\mathbb{Z}_{2}$. (iii) Server B applies the
Bell measurement $\\{|\Phi_{a,b}\rangle\\}_{a,b\in\mathbb{Z}_{2}}$ on ${\cal
H}_{B,1,s}\otimes{\cal H}_{B,2,s}$ for $s=1,\ldots,n$. Then, Server B obtains
the outcome $(A_{2,s},B_{2,s})$ and sends them to the user for $s=1,\ldots,n$.
(iv) Server B applies unitary
$\mathsf{Z}_{s}^{B_{2,s}}\mathsf{X}_{s}^{A_{2,s}}$ to ${\cal H}_{B,3,s}$.

We perform the following steps for $j=2,\ldots,m$.

4$j$-3)

Query 2$j$-1: The user generates
$\bm{Q}_{1,j-1,u}=(Q_{1,j-1,u,s})_{s\in[n]}\in\mathbb{Z}_{4}^{n}$ as

$\displaystyle Q_{1,j-1,u,s}$ $\displaystyle:=$ $\displaystyle-
Q_{1,j-1,u-(A_{2j-2,s}+B_{2j-2,s}+A_{2j-3,s}+B_{2j-3,s}),s}^{\prime}$
$\displaystyle+\delta_{u,A_{0,s}+B_{0,s}+A_{2j-2,s}+B_{2j-2,s}}.$ (29)

Also, the user generates
$\bm{Q}_{2,j,u}=(Q_{2,j,u,s})_{s\in[n]}\in\mathbb{Z}_{8}^{n}$ and
$\bm{Q}_{3,j,(u,v)}=(Q_{3,j,(u,v),(s,t)})_{(s,t)\in[n]_{2}}\in\mathbb{Z}_{2}^{[n]_{2}}$
uniformly at random for $(u,v)\in\mathbb{Z}_{2}^{2}$. Then, the user sends
them to Server A.

4$j$-2)

Unitary operation 2$j$-1: (i) Server A applies unitaries
$\mathsf{X}_{s}^{u}\mathsf{H}_{s}(Q_{1,j-1,u,s}\bm{y}_{j-1,s})\mathsf{X}_{s}^{u}$
to ${\cal H}_{A,2j-2,s}$ for $u\in\mathbb{Z}_{2}$. (ii) Then, Server A applies
unitaries
$\mathsf{X}_{s}^{u}\mathsf{T}_{s}(Q_{2,j,u,s}\bm{y}_{j,s})\mathsf{X}_{s}^{u}$
to ${\cal H}_{A,2j-2,s}$ and
$\mathsf{X}_{s}^{u}\mathsf{X}_{t}^{v}\mathsf{C_{Z}}_{(s,t)}(Q_{3,j,(u,v),(s,t)}\bm{z}_{j,(s,t)})\mathsf{X}_{s}^{u}\mathsf{X}_{t}^{v}$
to ${\cal H}_{A,2j-2,s}\otimes{\cal H}_{A,2j-2,t}$. (iii) Server A applies the
Bell measurement $\\{|\Phi_{a,b}\rangle\\}_{a,b\in\mathbb{Z}_{2}}$ on ${\cal
H}_{A,2j-2,s}\otimes{\cal H}_{A,2j-1,s}$ for $s=1,\ldots,n$. (iv) Then, Server
A obtains the outcome $(A_{2j-1,s},B_{2j-1,s})$ and sends them to the user for
$s=1,\ldots,n$. Server A applies unitary
$\mathsf{Z}_{s}^{B_{2j-1,s}}\mathsf{X}_{s}^{A_{2j-1,s}}$ to ${\cal
H}_{A,2j,s}$.

4$j$-1)

Query 2$j$: The user generates
$\bm{Q}_{2,j,u}^{\prime}=(Q_{2,j,u,s}^{\prime})_{s\in[n]}\in\mathbb{Z}_{8}^{n}$
and
$\bm{Q}_{3,j,(u,v)}^{\prime}=(Q_{3,j,(u,v),(s,t)}^{\prime})_{(s,t)\in[n]_{2}}\in\mathbb{Z}_{2}^{[n]_{2}}$
as

$\displaystyle Q_{2,j,u,s}^{\prime}$
$\displaystyle:=-Q_{2,j,u-A_{2j-1,s}-A_{2j-2,s},s}+\delta_{u,A_{0,s}+A_{2j-1,s}}$
(30)

and

$\displaystyle Q_{3,j,(u,v),(s,t)}^{\prime}$ $\displaystyle:=$ $\displaystyle-
Q_{3,j,(u-A_{2j-1,s}-A_{2j-2,s},v-A_{2j-1,t}-A_{2j-2,t}),(s,t)}$
$\displaystyle+\delta_{u,A_{0,s}+A_{2j-1,s}}\delta_{v,A_{0,t}+A_{2j-1,t}}.$
(31)

The user generates
$\bm{Q}_{1,j,u}^{\prime}=(Q_{1,j,u,s}^{\prime})_{s\in[n]}\in\mathbb{Z}_{4}^{n}$
according to the uniform distribution. The user sends them to Server B.

4$j$)

Unitary operation 2$j$: (i) Server B applies unitaries
$\mathsf{X}_{s}^{u}\mathsf{T}_{s}(Q_{2,j,u,s}^{\prime}\bm{y}_{j1,s})\mathsf{X}_{s}^{u}$
to ${\cal H}_{B,2j-1,s}$ and
$\mathsf{X}_{s}^{u}\mathsf{X}_{t}^{v}\mathsf{C_{Z}}_{(s,t)}(Q_{3,j,(u,v),(s,t)}^{\prime}\bm{z}_{j,(s,t)})\mathsf{X}_{s}^{u}\mathsf{X}_{t}^{v}$
to ${\cal H}_{B,2j-1,s}\otimes{\cal H}_{B,2j-1,t}$ for
$(u,v)\in\mathbb{Z}_{2}^{2}$. (ii) Then, Server B applies unitaries
$\mathsf{X}_{s}^{u}\mathsf{H}_{s}(Q_{1,j,u,s}^{\prime}\bm{y}_{j,s})\mathsf{X}_{s}^{u}$
to ${\cal H}_{B,2j-1,s}$ for $u\in\mathbb{Z}_{2}$. (iii) Server B applies the
Bell measurement $\\{|\Phi_{a,b}\rangle\\}_{a,b\in\mathbb{Z}_{2}}$ on ${\cal
H}_{B,2j-1,s}\otimes{\cal H}_{B,2j,s}$ for $s=1,\ldots,n$. Then, Server B
obtains the outcome $(A_{2j,s},B_{2j,s})$ and sends them to the user for
$s=1,\ldots,n$. (iv) Server B applies unitary
$\mathsf{Z}_{s}^{B_{2j,s}}\mathsf{X}_{s}^{A_{2j,s}}$ to ${\cal H}_{B,2j+1,s}$.

After Steps with $j=m$, we perform the following remaining steps.

4$m$+1)

Query 2$m$+1: The user generates
$\bm{Q}_{1,m,u}^{\prime}=(Q_{1,m,u,s}^{\prime})_{s\in[n]}\in\mathbb{Z}_{4}^{n}$
as (29) with $j=m+1$. Then, the user sends them to Server A.

4$m$+2)

Unitary operation 2$m$+1: (i) Server A applies unitaries
$\mathsf{X}_{s}^{u}\mathsf{H}_{s}(Q_{1,m,u,s}\bm{y}_{m,s})\mathsf{X}_{s}^{u}$
to ${\cal H}_{A,2m,s}$ for $u\in\mathbb{Z}_{2}$. (ii) Then, Server A sends the
system ${\cal H}_{A,2m,s}$ for $s=1,\ldots,n_{\circ}$ to the user.

4$m$+3)

Construction: The user applies
$\mathsf{X}_{s}^{A_{0,s}+A_{2m,s}}\mathsf{Z}_{s}^{B_{0,s}+B_{2m,s}}$ to ${\cal
H}_{A,2m,s}$ for $s=1,\ldots,n_{\circ}$.

In the above protocol, the first basis conversion is done as Step 2) before
the first unitary operation, Step 4). Since the output state of Step 2)
belongs to two-dimensional subspace, the problem (b) is resolved. This is the
reason why the first unitary operation is not done before the first basis
conversion.

######  Theorem 1.

Protocol 2 is a correct TOQC protocol that satisfies the user-secrecy even
with dishonest servers and the server-secrecy even with a dishonest user. Its
upload complexity is $(4n^{2}+16n)m$ bits and $n$ qubits. Its download
complexity is $4nm$ bits and $n_{\circ}$ qubits

Although Step 1) of Protocol 2 contains quantum communications, when the state
$|\psi\rangle$ is limited to basis states for the basis
$\\{|\bm{x}\rangle\\}_{\bm{x}\in\mathbb{Z}_{2}^{n}}$, the quantum
communication in Step 1) can be replaced to classical communication because
the masked state is also a basis state. In addition, when the user applies the
measurement based on the computation basis in Step $4m+3$), Steps $4m+2$) and
$4m+3$) can be replaced by the following Steps;

4$m$+2’)

Unitary operation 2$m$+1: (i) Server A applies unitaries
$\mathsf{X}_{s}^{u}\mathsf{H}_{s}(Q_{1,m,u,s}\bm{y}_{m,s})\mathsf{X}_{s}^{u}$
to ${\cal H}_{A,2m,s}$ for $u\in\mathbb{Z}_{2}$. (ii) Then, Server A applies
the measurement $\\{|0\rangle,|1\rangle\\}$ to the system ${\cal H}_{A,2m,s}$
and obtains the outcome $X_{s}$ for $s=1,\ldots,n_{\circ}$. (iii) Server A
sends the outcome $X_{s}$ for $s=1,\ldots,n_{\circ}$ to User $m+1$.

4$m$+3’)

Construction: The user calculates $A_{2m,s}+X_{s}$ for $s=1,\ldots,n_{\circ}$.

In this way, when the above two conditions are satisfied, this protocol does
not need quantum communication.

Proof:  Complexity: First, we discuss its upload complexity. In Step 1), the
size of the transmitted quantum system is $n$ qubits. $Q_{2,1,u,s}$ and
$Q_{3,1,(u,v),(s,t)}$ have 3bits and 1 bit, respectively, for
$(s,t)\in[n]_{2}$ and $(u,v)\in\mathbb{Z}_{2}^{2}$. Hence, $\bm{Q}_{2,1,u}$
and $\bm{Q}_{3,1,(u,v)}$ have $3n$ bits and $n(n-1)/2$ bits, respectively, for
$(u,v)\in\mathbb{Z}_{2}^{2}$. Thus, in Step 1), the user sends $2\cdot
3n+4\cdot n(n-1)/2=6n+2n(n-1)=2n^{2}+4n$ bits in addition to $n$ qubits to
Server A. In Step 3), since $Q_{1,1,u,s}^{\prime}$ has 2bits for $s\in[n]$ and
$u\in\mathbb{Z}_{2}$, $\bm{Q}_{1,1,u}^{\prime}$ has $2n$ bits for
$u\in\mathbb{Z}_{2}$. Thus, in Step 3), since the sender sends
$\bm{Q}_{2,1,u}^{\prime}$, $\bm{Q}_{3,1,(u,v)}^{\prime}$, and
$\bm{Q}_{1,1,u}^{\prime}$ to Server B, Step 3) has upload complexity
$2n^{2}+8n$ In the same way, Steps 4$j$-3) and 4$j$-1) have upload complexity
$2n^{2}+8n$. Step 4$m$+1) has upload complexity $4n$ to send $\bm{Q}_{1,m,u}$
for $u\in\mathbb{Z}_{2}$. Hence, the total upload complexity $(4n^{2}+16n)m$
bits and $n$ qubits.

Next, we discuss its download complexity. Steps 2), 4), 4$j$-2), and 4$j$)
have download complexity with $2n$ bits. Step 4$m$+2) has download complexity
with $n_{\circ}$ qubits. Hence, the total download complexity $4nm$ bits and
$n_{\circ}$ qubits.

Correctness: The state at the end of (i) of Step 3) on $\otimes_{s=1}^{n}{\cal
H}_{B,1,s}$ is the following.

$\displaystyle|\psi_{1}\rangle$
$\displaystyle:=\Big{(}\bigotimes_{(s,t)\in[n]_{2}}\prod_{(u,v)\in\mathbb{Z}_{2}^{2}}\mathsf{X}_{s}^{u}\mathsf{X}_{t}^{v}\mathsf{C_{Z}}_{(s,t)}(Q_{3,1,(u,v),(s,t)}^{\prime}\bm{z}_{1,(s,t)})\mathsf{X}_{s}^{u}\mathsf{X}_{t}^{v}\Big{)}\Big{(}\bigotimes_{s=1}^{n}\prod_{u\in\mathbb{Z}_{2}}\mathsf{X}_{s}^{u}\mathsf{T}_{s}(Q_{2,1,u,s}^{\prime}\bm{y}_{1,s})\mathsf{X}_{s}^{u}\Big{)}\Big{(}\bigotimes_{s=1}^{n}\mathsf{Z}_{s}^{B_{1,s}}\mathsf{X}_{s}^{A_{1,s}}\Big{)}$
$\displaystyle\quad\cdot\Big{(}\bigotimes_{(s,t)\in[n]_{2}}\prod_{(u,v)\in\mathbb{Z}_{2}^{2}}\mathsf{X}_{s}^{u}\mathsf{X}_{t}^{v}\mathsf{C_{Z}}_{(s,t)}(Q_{3,1,(u,v),(s,t)}\bm{z}_{1,(s,t)})\mathsf{X}_{s}^{u}\mathsf{X}_{t}^{v}\Big{)}\Big{(}\bigotimes_{s=1}^{n}\prod_{u\in\mathbb{Z}_{2}}\mathsf{X}_{s}^{u}\mathsf{T}_{s}(Q_{2,1,u,s}\bm{y}_{1,s})\mathsf{X}_{s}^{u}\Big{)}\Big{(}\bigotimes_{s=1}^{n}\mathsf{Z}_{s}^{B_{0,s}}\mathsf{X}_{s}^{A_{0,s}}\Big{)}|\psi\rangle$
$\displaystyle\doteq\Big{(}\bigotimes_{s=1}^{n}\mathsf{Z}_{s}^{B_{1,s}}\mathsf{X}_{s}^{A_{1,s}}\Big{)}\Big{(}\bigotimes_{s=1}^{n}\mathsf{Z}_{s}^{B_{0,s}}\mathsf{X}_{s}^{A_{0,s}}\Big{)}\Big{(}\bigotimes_{s\in[n]}\mathsf{T}_{s}(\bm{y}_{1,s})\Big{)}\Big{(}\bigotimes_{(s,t)\in[n]_{2}}\mathsf{C_{Z}}_{(s,t)}(\bm{z}_{1,(s,t)})\Big{)}|\psi\rangle,$
(32)

where the above equation follows from (27) and (28).

The state at the end of (i) of Step 5) on $\otimes_{s=1}^{n}{\cal H}_{A,2,s}$
is the following.

$\displaystyle|\psi_{2}\rangle$
$\displaystyle:=\Big{(}\bigotimes_{s=1}^{n}\prod_{u\in\mathbb{Z}_{2}}\mathsf{X}_{s}^{u}\mathsf{H}_{s}(Q_{1,1,u,s}\bm{x}_{1,s})\mathsf{X}_{s}^{u}\Big{)}\Big{(}\bigotimes_{s=1}^{n}\mathsf{Z}_{s}^{B_{1,s}}\mathsf{X}_{s}^{A_{1,s}}\Big{)}\Big{(}\bigotimes_{s=1}^{n}\mathsf{Z}_{s}^{B_{2,s}}\mathsf{X}_{s}^{A_{2,s}}\Big{)}\Big{(}\bigotimes_{s=1}^{n}\prod_{u\in\mathbb{Z}_{2}}\mathsf{X}_{s}^{u}\mathsf{H}_{s}(Q_{1,1,u,s}^{\prime}\bm{x}_{1,s})\mathsf{X}_{s}^{u}\Big{)}|\psi_{1}\rangle$
$\displaystyle\doteq\Big{(}\bigotimes_{s=1}^{n}\prod_{u\in\mathbb{Z}_{2}}\mathsf{X}_{s}^{u}\mathsf{H}_{s}(Q_{1,1,u,s}\bm{x}_{1,s})\mathsf{X}_{s}^{u}\Big{)}\Big{(}\bigotimes_{s=1}^{n}\mathsf{Y}_{s}^{B_{1,s}}\mathsf{X}_{s}^{A_{1,s}+B_{1,s}}\Big{)}\Big{(}\bigotimes_{s=1}^{n}\mathsf{Y}_{s}^{B_{2,s}}\mathsf{X}_{s}^{A_{2,s}+B_{2,s}}\Big{)}\Big{(}\bigotimes_{s=1}^{n}\prod_{u\in\mathbb{Z}_{2}}\mathsf{X}_{s}^{u}\mathsf{H}_{s}(Q_{1,1,u,s}^{\prime}\bm{x}_{1,s})\mathsf{X}_{s}^{u}\Big{)}|\psi_{1}\rangle$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\doteq}}\Big{(}\bigotimes_{s=1}^{n}\mathsf{Y}_{s}^{B_{2,s}}\mathsf{X}_{s}^{A_{2,s}+B_{2,s}}\Big{)}\Big{(}\bigotimes_{s=1}^{n}\mathsf{Y}_{s}^{B_{0,s}}\mathsf{X}_{s}^{A_{0,s}+B_{0,s}}\Big{)}\Big{(}\bigotimes_{s\in[n]}\mathsf{H}_{s}(\bm{x}_{1,s})\Big{)}\Big{(}\bigotimes_{s=1}^{n}\mathsf{Y}_{s}^{B_{0,s}}\mathsf{X}_{s}^{A_{0,s}+B_{0,s}}\Big{)}\Big{(}\bigotimes_{s=1}^{n}\mathsf{Y}_{s}^{B_{1,s}}\mathsf{X}_{s}^{A_{1,s}+B_{1,s}}\Big{)}|\psi_{1}\rangle$
$\displaystyle\doteq\Big{(}\bigotimes_{s=1}^{n}\mathsf{Z}_{s}^{B_{2,s}}\mathsf{X}_{s}^{A_{2,s}}\Big{)}\Big{(}\bigotimes_{s=1}^{n}\mathsf{Z}_{s}^{B_{0,s}}\mathsf{X}_{s}^{A_{0,s}}\Big{)}\Big{(}\bigotimes_{s\in[n]}\mathsf{H}_{s}(\bm{x}_{1,s})\Big{)}\Big{(}\bigotimes_{s=1}^{n}\mathsf{Z}_{s}^{B_{0,s}}\mathsf{X}_{s}^{A_{0,s}}\Big{)}\Big{(}\bigotimes_{s=1}^{n}\mathsf{Z}_{s}^{B_{1,s}}\mathsf{X}_{s}^{A_{1,s}}\Big{)}|\psi_{1}\rangle$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\doteq}}\Big{(}\bigotimes_{s=1}^{n}\mathsf{Z}_{s}^{B_{2,s}}\mathsf{X}_{s}^{A_{2,s}}\Big{)}\Big{(}\bigotimes_{s=1}^{n}\mathsf{Z}_{s}^{B_{0,s}}\mathsf{X}_{s}^{A_{0,s}}\Big{)}\Big{(}\bigotimes_{s\in[n]}\mathsf{H}_{s}(\bm{x}_{1,s})\Big{)}\Big{(}\bigotimes_{s\in[n]}\mathsf{T}_{s}(\bm{y}_{1,s})\Big{)}\Big{(}\bigotimes_{(s,t)\in[n]_{2}}\mathsf{C_{Z}}_{(s,t)}(\bm{z}_{1,(s,t)})\Big{)}|\psi\rangle,$
(33)

where $(a)$ follows from (29) and the relation
$[\mathsf{Y}_{s},\mathsf{H}_{s}]=0$, and $(b)$ follows from (32).

The state at the end of (i) of Step 7) on $\otimes_{s=1}^{n}{\cal H}_{B,3,s}$
is the following.

$\displaystyle|\psi_{3}\rangle$
$\displaystyle:=\Big{(}\bigotimes_{(s,t)\in[n]_{2}}\prod_{(u,v)\in\mathbb{Z}_{2}^{2}}\mathsf{X}_{s}^{u}\mathsf{X}_{t}^{v}\mathsf{C_{Z}}_{(s,t)}(Q_{3,2,(u,v),(s,t)}^{\prime}\bm{z}_{2,(s,t)})\mathsf{X}_{s}^{u}\mathsf{X}_{t}^{v}\Big{)}\Big{(}\bigotimes_{s=1}^{n}\prod_{u\in\mathbb{Z}_{2}}\mathsf{X}_{s}^{u}\mathsf{T}_{s}(Q_{2,2,u,s}^{\prime}\bm{y}_{2,s})\mathsf{X}_{s}^{u}\Big{)}\Big{(}\bigotimes_{s=1}^{n}\mathsf{Z}_{s}^{B_{2,s}}\mathsf{X}_{s}^{A_{2,s}}\Big{)}$
$\displaystyle\quad\cdot\Big{(}\bigotimes_{s=1}^{n}\mathsf{Z}_{s}^{B_{3,s}}\mathsf{X}_{s}^{A_{3,s}}\Big{)}\Big{(}\bigotimes_{(s,t)\in[n]_{2}}\prod_{(u,v)\in\mathbb{Z}_{2}^{2}}\mathsf{X}_{s}^{u}\mathsf{X}_{t}^{v}\mathsf{C_{Z}}_{(s,t)}(Q_{3,2,(u,v),(s,t)}\bm{z}_{2,(s,t)})\mathsf{X}_{s}^{u}\mathsf{X}_{t}^{v}\Big{)}\Big{(}\bigotimes_{s=1}^{n}\prod_{u\in\mathbb{Z}_{2}}\mathsf{X}_{s}^{u}\mathsf{T}_{s}(Q_{2,2,u,s}\bm{y}_{2,s})\mathsf{X}_{s}^{u}\Big{)}|\psi_{2}\rangle$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\doteq}}\Big{(}\bigotimes_{s=1}^{n}\mathsf{Z}_{s}^{B_{3,s}}\mathsf{X}_{s}^{A_{3,s}}\Big{)}\Big{(}\bigotimes_{s=1}^{n}\mathsf{Z}_{s}^{B_{0,s}}\mathsf{X}_{s}^{A_{0,s}}\Big{)}\Big{(}\bigotimes_{s\in[n]}\mathsf{T}_{s}(\bm{y}_{2,s})\Big{)}\Big{(}\bigotimes_{(s,t)\in[n]_{2}}\mathsf{C_{Z}}_{(s,t)}(\bm{z}_{2,(s,t)})\Big{)}\Big{(}\bigotimes_{s=1}^{n}\mathsf{Z}_{s}^{B_{2,s}}\mathsf{X}_{s}^{A_{2,s}}\Big{)}\Big{(}\bigotimes_{s=1}^{n}\mathsf{Z}_{s}^{B_{0,s}}\mathsf{X}_{s}^{A_{0,s}}\Big{)}|\psi_{2}\rangle$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\doteq}}\Big{(}\bigotimes_{s=1}^{n}\mathsf{Z}_{s}^{B_{3,s}}\mathsf{X}_{s}^{A_{3,s}}\Big{)}\Big{(}\bigotimes_{s=1}^{n}\mathsf{Z}_{s}^{B_{0,s}}\mathsf{X}_{s}^{A_{0,s}}\Big{)}\Big{(}\bigotimes_{s\in[n]}\mathsf{T}_{s}(\bm{y}_{2,s})\Big{)}\Big{(}\bigotimes_{(s,t)\in[n]_{2}}\mathsf{C_{Z}}_{(s,t)}(\bm{z}_{2,(s,t)})\Big{)}$
$\displaystyle\quad\cdot\Big{(}\bigotimes_{s\in[n]}\mathsf{H}_{s}(\bm{x}_{1,s})\Big{)}\Big{(}\bigotimes_{s\in[n]}\mathsf{T}_{s}(\bm{y}_{1,s})\Big{)}\Big{(}\bigotimes_{(s,t)\in[n]_{2}}\mathsf{C_{Z}}_{(s,t)}(\bm{z}_{1,(s,t)})\Big{)}|\psi\rangle,$
(34)

where $(a)$ follows from (30) and (31), and $(b)$ follows from (41).

Repeating the above discussion, we find that the state at the end of (i) of
Step 4$m$+2) on $\otimes_{s=1}^{n}{\cal H}_{A,2m,s}$ is the following.

$\displaystyle|\psi_{2m}\rangle:=\Big{(}\bigotimes_{s=1}^{n}\mathsf{Z}_{s}^{B_{2m,s}}\mathsf{X}_{s}^{A_{2m,s}}\Big{)}\Big{(}\bigotimes_{s=1}^{n}\mathsf{Z}_{s}^{B_{0,s}}\mathsf{X}_{s}^{A_{0,s}}\Big{)}\Bigg{(}\prod_{j=1}^{m}\Big{(}\bigotimes_{s\in[n]}\mathsf{H}_{s}(\bm{x}_{j,s})\Big{)}\Big{(}\bigotimes_{s\in[n]}\mathsf{T}_{s}(\bm{y}_{j,s})\Big{)}\Big{(}\bigotimes_{(s,t)\in[n]_{2}}\mathsf{C_{Z}}_{(s,t)}(\bm{z}_{j,(s,t)})\Big{)}\Bigg{)}|\psi\rangle.$
(35)

Then, Step 4$m$+3) constructs the desired state from $|\psi_{2m}\rangle$.

Server-secrecy: Next, we show the server-secrecy even with a dishonest user.
Assume that the servers are honest. The user obtains the variables
$(A_{k,s},B_{k,s})$ for $k=1,\ldots,2m$ and $s=1,\ldots,n$, and the quantum
system $\otimes_{s=1}^{n_{\circ}}{\cal H}_{A,2m,s}$. These variables are
independent of the program $\bm{w}$. Hence, only the state on the quantum
system $\otimes_{s=1}^{n_{\circ}}{\cal H}_{A,2m,s}$ is related to the program
$\bm{w}$. Since its dimension is the same as the desired output information,
the user does not obtain any information for the program $\bm{w}$ more than
the desired output information. In other words, the user can generate the
final state on his/her own whole system by using
$\Phi_{ideal}(\bm{w},|\psi\rangle)$, the classical information describing the
initial state $|\psi\rangle$, and classical information generated by
himself/herself.

User-secrecy: Next, we show the user-secrecy even with dishonest servers.
Assume that the user is honest. Server A receives the system
$\otimes_{s=1}^{n}{\cal H}_{s}$ and the variables $\bm{Q}_{1,j,u}$,
$\bm{Q}_{2,j,u}$, $\bm{Q}_{3,j,(u,v)}$ for $j=1,\ldots,m$ and
$(u,v)\in\mathbb{Z}_{2}^{2}$. Since the state on the system
$\otimes_{s=1}^{n}{\cal H}_{s}$ is the completely mixed state and these
variables are subject to the uniform distribution independently. Since they
are independent of $|\psi\rangle$, Server A obtains no information for
$|\psi\rangle$. Also, Server B receives the variables
$\bm{Q}_{1,j,u}^{\prime}$, $\bm{Q}_{2,j,u}^{\prime}$,
$\bm{Q}_{3,j,(u,v)}^{\prime}$ for $j=1,\ldots,m$ and
$(u,v)\in\mathbb{Z}_{2}^{2}$. These variables are subject to the uniform
distribution independently. Since they are independent of $|\psi\rangle$,
Server B obtains no formation for $|\psi\rangle$. Therefore, the user-secrecy
holds even with dishonest servers.

##  VI Protocol for TGDMQC

Since one-server delegated quantum computation is impossible [27, 28, 29],
using Protocol 2, we introduce our two-server GDMQC (TGDMQC) protocol by
considering the case when the input is fixed to $|0\rangle^{\otimes n}$ and
the read-out measurement is fixed to the measurement based on the computation
basis. In this case, the task can be done even when the user makes only
classical communication.

######  Protocol 3 (TGDMQC protocol).

There are $m+1$ users, Users $1$, $2$, …, $m$, $m+1$, and two servers, Servers
A and B. Severs A and B are not allowed to communicate with each other. Each
user can communicate with both servers with a classical channel. Only Servers
A and B are allowed to make quantum operations.

0)

Entanglement Sharing: Servers A and B prepare $2mn$ copies of the Bell state
$|\Phi\rangle$ on ${\cal H}_{A,j,s}\otimes{\cal H}_{B,j,s}$ for $s=1,\ldots,n$
and $j=1,\ldots,2m$.

1)

Query 1: User 1 generates
$\bm{Q}_{2,1,u}=(Q_{2,1,u,s})_{s\in[n]}\in\mathbb{Z}_{8}^{n}$ and
$\bm{Q}_{3,1,(u,v)}=(Q_{3,1,(u,v),(s,t)})_{(s,t)\in[n]_{2}}\in\mathbb{Z}_{2}^{[n]_{2}}$
uniformly at random for $(u,v)\in\mathbb{Z}_{2}^{2}$, and sends them to Server
A.

2)

Unitary operation 1: Server A sets the initial state $|0\rangle^{\otimes n}$
on ${\cal H}^{\otimes n}$. Server A applies unitaries
$\mathsf{X}_{s}^{u}\mathsf{T}_{s}(Q_{2,1,u,s}\bm{y}_{1,s})\mathsf{X}_{s}^{u}$
to ${\cal H}_{s}$ and
$\mathsf{X}_{s}^{u}\mathsf{X}_{t}^{v}\mathsf{C_{Z}}_{(s,t)}(Q_{3,1,(u,v),(s,t)}\bm{z}_{1,(s,t)})\mathsf{X}_{s}^{u}\mathsf{X}_{t}^{v}$
to ${\cal H}_{s}\otimes{\cal H}_{t}$. Server A applies the Bell measurement
$\\{|\Phi_{a,b}\rangle\\}_{a,b\in\mathbb{Z}_{2}}$ on ${\cal H}_{s}\otimes{\cal
H}_{A,1,s}$ for $s=1,\ldots,n$. Then, Server A obtains the outcome
$(A_{1,s},B_{1,s})$ and sends them to User 1 for $s=1,\ldots,n$. Server A
applies unitary $\mathsf{Z}_{s}^{B_{1,s}}\mathsf{X}_{s}^{A_{1,s}}$ to ${\cal
H}_{A,2,s}$.

3)

Query 2: User 1 generates
$\bm{Q}_{2,1,u}^{\prime}=(Q_{2,1,u,s}^{\prime})_{s\in[n]}\in\mathbb{Z}_{8}^{n}$
and
$\bm{Q}_{3,1,(u,v)}^{\prime}=(Q_{3,1,(u,v),(s,t)}^{\prime})_{(s,t)\in[n]_{2}}\in\mathbb{Z}_{2}^{[n]_{2}}$
as

$\displaystyle Q_{2,1,u,s}^{\prime}$
$\displaystyle:=-Q_{2,1,u-A_{1,s},s}+y_{1,s}^{\prime}\delta_{u,A_{1,s}},$ (36)

and

$\displaystyle Q_{3,1,(u,v),(s,t)}^{\prime}$
$\displaystyle:=-Q_{3,1,(u-A_{1,s},v-A_{1,t}),(s,t)}+z_{1,(s,t)}^{\prime}\delta_{u,A_{1,s}}\delta_{v,A_{0,t}+A_{1,t}}.$
(37)

User 1 generates
$\bm{Q}_{1,1,u}^{\prime}=(Q_{1,1,u,s}^{\prime})_{s\in[n]}\in\mathbb{Z}_{4}^{n}$
according to the uniform distribution. User 1 sends them to Server B.

4)

Unitary operation 2: (i) Server B applies unitaries
$\mathsf{X}_{s}^{u}\mathsf{T}_{s}(Q_{2,1,u,s}^{\prime}\bm{y}_{1,s})\mathsf{X}_{s}^{u}$
to ${\cal H}_{B,1,s}$ and
$\mathsf{X}_{s}^{u}\mathsf{X}_{t}^{v}\mathsf{C_{Z}}_{(s,t)}(Q_{3,1,(u,v),(s,t)}^{\prime}\bm{z}_{1,(s,t)})\mathsf{X}_{s}^{u}\mathsf{X}_{t}^{v}$
to ${\cal H}_{B,1,s}\otimes{\cal H}_{B,1,t}$ for $(u,v)\in\mathbb{Z}_{2}^{2}$.
(ii) Then, Server B applies unitaries
$\mathsf{X}_{s}^{u}\mathsf{H}_{s}(Q_{1,1,u,s}^{\prime}\bm{y}_{1,s})\mathsf{X}_{s}^{u}$
to ${\cal H}_{B,1,s}$ for $u\in\mathbb{Z}_{2}$. (iii) Server B applies the
Bell measurement $\\{|\Phi_{a,b}\rangle\\}_{a,b\in\mathbb{Z}_{2}}$ on ${\cal
H}_{B,1,s}\otimes{\cal H}_{B,2,s}$ for $s=1,\ldots,n$. Then, Server B obtains
the outcome $(A_{2,s},B_{2,s})$ and sends them to Users 1 and 2 for
$s=1,\ldots,n$. (iv) Server B applies unitary
$\mathsf{Z}_{s}^{B_{2,s}}\mathsf{X}_{s}^{A_{2,s}}$ to ${\cal H}_{B,3,s}$.

We perform the following steps for $j=2,\ldots,m$.

4$j$-3)

Query 2$j$-1: User $j-1$ generates
$\bm{Q}_{1,j-1,u}=(Q_{1,j-1,u,s})_{s\in[n]}\in\mathbb{Z}_{4}^{n}$ as

$\displaystyle Q_{1,j-1,u,s}$ $\displaystyle:=$ $\displaystyle-
Q_{1,j-1,u-(A_{2j-2,s}+B_{2j-2,s}+A_{2j-3,s}+B_{2j-3,s}),s}^{\prime}$
$\displaystyle+x_{j-1,s}^{\prime}\delta_{u,A_{0,s}+B_{0,s}+A_{2j-2,s}+B_{2j-2,s}}$
(38)

Then, User $j-1$ sends them to Server A. Also, User $j$ generates
$\bm{Q}_{2,j,u}=(Q_{2,j,u,s})_{s\in[n]}\in\mathbb{Z}_{8}^{n}$ and
$\bm{Q}_{3,j,(u,v)}=(Q_{3,j,(u,v),(s,t)})_{(s,t)\in[n]_{2}}\in\mathbb{Z}_{2}^{[n]_{2}}$
uniformly at random for $(u,v)\in\mathbb{Z}_{2}^{2}$. Then, User $j$ sends
them to Server A.

4$j$-2)

Unitary operation 2$j$-1: Server A applies unitaries
$\mathsf{X}_{s}^{u}\mathsf{H}_{s}(Q_{1,j-1,u,s}\bm{y}_{j-1,s})\mathsf{X}_{s}^{u}$
to ${\cal H}_{A,2j-2,s}$ for $u\in\mathbb{Z}_{2}$. Then, Server A applies
unitaries
$\mathsf{X}_{s}^{u}\mathsf{T}_{s}(Q_{2,j,u,s}\bm{y}_{j,s})\mathsf{X}_{s}^{u}$
to ${\cal H}_{A,2j-2,s}$ and
$\mathsf{X}_{s}^{u}\mathsf{X}_{t}^{v}\mathsf{C_{Z}}_{(s,t)}(Q_{3,j,(u,v),(s,t)}\bm{z}_{j,(s,t)})\mathsf{X}_{s}^{u}\mathsf{X}_{t}^{v}$
to ${\cal H}_{A,2j-2,s}\otimes{\cal H}_{A,2j-2,t}$. Server A applies the Bell
measurement $\\{|\Phi_{a,b}\rangle\\}_{a,b\in\mathbb{Z}_{2}}$ on ${\cal
H}_{A,2j-2,s}\otimes{\cal H}_{A,2j-1,s}$ for $s=1,\ldots,n$. Then, Server A
obtains the outcome $(A_{2j-1,s},B_{2j-1,s})$ and sends them to User $j$ for
$s=1,\ldots,n$. Server A applies unitary
$\mathsf{Z}_{s}^{B_{2j-1,s}}\mathsf{X}_{s}^{A_{2j-1,s}}$ to ${\cal
H}_{A,2j,s}$.

4$j$-1)

Query 2$j$: User $j$ generates
$\bm{Q}_{2,j,u}^{\prime}=(Q_{2,j,u,s}^{\prime})_{s\in[n]}\in\mathbb{Z}_{8}^{n}$
and
$\bm{Q}_{3,j,(u,v)}^{\prime}=(Q_{3,j,(u,v),(s,t)}^{\prime})_{(s,t)\in[n]_{2}}\in\mathbb{Z}_{2}^{[n]_{2}}$
as

$\displaystyle Q_{2,j,u,s}^{\prime}$
$\displaystyle:=-Q_{2,j,u-A_{2j-1,s}-A_{2j-2,s},s}+y_{j,s}^{\prime}\delta_{u,A_{0,s}+A_{2j-1,s}}$
(39)

and

$\displaystyle Q_{3,j,(u,v),(s,t)}^{\prime}$ $\displaystyle:=$ $\displaystyle-
Q_{3,j,(u-A_{2j-1,s}-A_{2j-2,s},v-A_{2j-1,t}-A_{2j-2,t}),(s,t)}$
$\displaystyle+z_{j,(s,t)}^{\prime}\delta_{u,A_{0,s}+A_{2j-1,s}}\delta_{v,A_{0,t}+A_{2j-1,t}}.$
(40)

User $j$ generates
$\bm{Q}_{1,j,u}^{\prime}=(Q_{1,j,u,s}^{\prime})_{s\in[n]}\in\mathbb{Z}_{4}^{n}$
according to the uniform distribution. User $j$ sends them to Server B.

4$j$)

Unitary operation 2j: Server B applies unitaries
$\mathsf{X}_{s}^{u}\mathsf{T}_{s}(Q_{2,j,u,s}^{\prime}\bm{y}_{j1,s})\mathsf{X}_{s}^{u}$
to ${\cal H}_{B,2j-1,s}$ and
$\mathsf{X}_{s}^{u}\mathsf{X}_{t}^{v}\mathsf{C_{Z}}_{(s,t)}(Q_{3,j,(u,v),(s,t)}^{\prime}\bm{z}_{j,(s,t)})\mathsf{X}_{s}^{u}\mathsf{X}_{t}^{v}$
to ${\cal H}_{B,2j-1,s}\otimes{\cal H}_{B,2j-1,t}$ for
$(u,v)\in\mathbb{Z}_{2}^{2}$. Then, Server B applies unitaries
$\mathsf{X}_{s}^{u}\mathsf{H}_{s}(Q_{1,j,u,s}^{\prime}\bm{y}_{j,s})\mathsf{X}_{s}^{u}$
to ${\cal H}_{B,2j-1,s}$ for $u\in\mathbb{Z}_{2}$.

Server B applies the Bell measurement
$\\{|\Phi_{a,b}\rangle\\}_{a,b\in\mathbb{Z}_{2}}$ on ${\cal
H}_{B,2j-1,s}\otimes{\cal H}_{B,2j,s}$ for $s=1,\ldots,n$. Then, Server B
obtains the outcome $(A_{2j,s},B_{2j,s})$ and sends them to Users $j$ and
$j+1$ for $s=1,\ldots,n$. Server B applies unitary
$\mathsf{Z}_{s}^{B_{2j,s}}\mathsf{X}_{s}^{A_{2j,s}}$ to ${\cal H}_{B,2j+1,s}$.

After Steps with $j=m$, we perform the following remaining steps.

4$m$+1)

Query 2$m$+1: User m generates
$\bm{Q}_{1,m,u}^{\prime}=(Q_{1,m,u,s}^{\prime})_{s\in[n]}\in\mathbb{Z}_{4}^{n}$
as (38) with $j=m+1$. Then, User m sends them to Server A.

4$m$+2)

Unitary operation 2m+1: (i) Server A applies unitaries
$\mathsf{X}_{s}^{u}\mathsf{H}_{s}(Q_{1,m,u,s}\bm{y}_{m,s})\mathsf{X}_{s}^{u}$
to ${\cal H}_{A,2m,s}$ for $u\in\mathbb{Z}_{2}$. (ii) Then, Server A applies
the measurement $\\{|0\rangle,|1\rangle\\}$ to the system ${\cal H}_{A,2m,s}$
and obtains the outcome $X_{s}$ for $s=1,\ldots,n_{\circ}$. (iii) Server A
sends the outcome $X_{s}$ for $s=1,\ldots,n_{\circ}$ to User $m+1$.

4$m$+3)

Construction: The user calculates $A_{2m,s}+X_{s}$ for $s=1,\ldots,n_{\circ}$.

######  Theorem 2.

Protocol 3 is a correct TGDMQC protocol that satisfies the user-secrecy even
with dishonest servers and the server-secrecy even with dishonest users. Its
upload complexity is $(4n^{2}+16n)m$ bits. Its download complexity is
$4nm+n_{\circ}$ bits.

Since Protocol 3 works as a TGDMQC protocol, we can realize a variant of TOQC
without quantum communication, as explained in Section IV.3.4.

Proof:  Complexity: The calculation of complexity of Protocol 3 is quite
similar to the calculation of complexity of Protocol 2. Their difference is
the following. While Step 1) of Protocol 2 has transmission of a quantum
system with $n$ qubits, Step 1) of Protocol 3 has no transmission of quantum
system. While Step 1) of Protocol 2 has transmission of a quantum system with
$n_{\circ}$ qubits, Step 1) of Protocol 3 has transmission of $n_{\circ}$
bits. Considering this difference, we can calculate the the complexity of
Protocol 3 from the complexity of Protocol 2.

Correctness:

Similar to (32) in the proof of Theorem 1, the state at the end of (i) of Step
3) on $\otimes_{s=1}^{n}{\cal H}_{B,1,s}$ is the following.

$\displaystyle|\psi_{1}\rangle$
$\displaystyle:=\Big{(}\bigotimes_{(s,t)\in[n]_{2}}\prod_{(u,v)\in\mathbb{Z}_{2}^{2}}\mathsf{X}_{s}^{u}\mathsf{X}_{t}^{v}\mathsf{C_{Z}}_{(s,t)}(Q_{3,1,(u,v),(s,t)}^{\prime}\bm{z}_{1,(s,t)})\mathsf{X}_{s}^{u}\mathsf{X}_{t}^{v}\Big{)}\Big{(}\bigotimes_{s=1}^{n}\prod_{u\in\mathbb{Z}_{2}}\mathsf{X}_{s}^{u}\mathsf{T}_{s}(Q_{2,1,u,s}^{\prime}\bm{y}_{1,s})\mathsf{X}_{s}^{u}\Big{)}\Big{(}\bigotimes_{s=1}^{n}\mathsf{Z}_{s}^{B_{1,s}}\mathsf{X}_{s}^{A_{1,s}}\Big{)}$
$\displaystyle\quad\cdot\Big{(}\bigotimes_{(s,t)\in[n]_{2}}\prod_{(u,v)\in\mathbb{Z}_{2}^{2}}\mathsf{X}_{s}^{u}\mathsf{X}_{t}^{v}\mathsf{C_{Z}}_{(s,t)}(Q_{3,1,(u,v),(s,t)}\bm{z}_{1,(s,t)})\mathsf{X}_{s}^{u}\mathsf{X}_{t}^{v}\Big{)}\Big{(}\bigotimes_{s=1}^{n}\prod_{u\in\mathbb{Z}_{2}}\mathsf{X}_{s}^{u}\mathsf{T}_{s}(Q_{2,1,u,s}\bm{y}_{1,s})\mathsf{X}_{s}^{u}\Big{)}\Big{(}\bigotimes_{s=1}^{n}\mathsf{Z}_{s}^{B_{0,s}}\mathsf{X}_{s}^{A_{0,s}}\Big{)}|\psi\rangle$
$\displaystyle\doteq\Big{(}\bigotimes_{s=1}^{n}\mathsf{Z}_{s}^{B_{1,s}}\mathsf{X}_{s}^{A_{1,s}}\Big{)}\Big{(}\bigotimes_{s=1}^{n}\mathsf{Z}_{s}^{B_{0,s}}\mathsf{X}_{s}^{A_{0,s}}\Big{)}\Big{(}\bigotimes_{s\in[n]}\mathsf{T}_{s}(\bm{y}_{1,s}\cdot\bm{y}_{1,s}^{\prime})\Big{)}\Big{(}\bigotimes_{(s,t)\in[n]_{2}}\mathsf{C_{Z}}_{(s,t)}(\bm{z}_{1,(s,t)}\cdot\bm{z}_{1,(s,t)}^{\prime})\Big{)}|0\rangle^{\otimes
n},$ (41)

where the above equation follows from (36) and (37).

Repeating the same discussion as the proof of Theorem 1, we find that the
state at the end of (i) of Step 4m+2) on $\otimes_{s=1}^{n}{\cal H}_{A,2m,s}$
is the following.

$\displaystyle|\psi_{2m}\rangle:=\Big{(}\bigotimes_{s=1}^{n}\mathsf{Z}_{s}^{B_{2m,s}}\mathsf{X}_{s}^{A_{2m,s}}\Big{)}\Bigg{(}\prod_{j=1}^{m}\Big{(}\bigotimes_{s\in[n]}\mathsf{H}_{s}(\bm{x}_{j,s}\cdot\bm{x}_{j,s}^{\prime})\Big{)}\Big{(}\bigotimes_{s\in[n]}\mathsf{T}_{s}(\bm{y}_{j,s}\cdot\bm{y}_{j,s}^{\prime})\Big{)}\Big{(}\bigotimes_{(s,t)\in[n]_{2}}\mathsf{C_{Z}}_{(s,t)}(\bm{z}_{j,(s,t)}\cdot\bm{z}_{j,(s,t)}^{\prime})\Big{)}\Bigg{)}|0\rangle^{\otimes
n}.$ (42)

Then, Step 4m+3) constructs the desired outcome.

Server secrecy: Next, we show the server-secrecy even with dishonest users.
Assume that both servers are honest and all users collude and are dishonest.
The users obtain the variables $(A_{k,s},B_{k,s})$ for $k=1,\ldots,2m$ and
$s=1,\ldots,n$, and the variables $\bm{X}=(X_{1},\ldots,X_{n_{\circ}})$. These
variables $(A_{k,s},B_{k,s})$ are independent of the program $\bm{w}$. Hence,
only the variables $\bm{X}$ are related to the program $\bm{w}$. Since its
size is the same as the desired output information, the users do not obtain
any information for the program $\bm{w}$ more than the desired output
information. In other words, the users can generate the final state on their
own whole system by using the desired output information and classical
information generated by themselves.

User secrecy: Assume that a set of users $\Theta\subset[m]$ are honest. Since
$\bm{Q}_{2,j,u}$, $\bm{Q}_{3,j,(u,v)}$, and $\bm{Q}_{1,j,u}$ are independently
subject to the uniform distribution for $j\in\Theta$, Server A obtains no
information for
$\\{(\bm{x}_{j}^{\prime},\bm{y}_{j}^{\prime},\bm{z}_{j}^{\prime})\\}_{j\in\Theta}$.
In the same way, Server B obtains no information for
$\\{(\bm{x}_{j}^{\prime},\bm{y}_{j}^{\prime},\bm{z}_{j}^{\prime})\\}_{j\in\Theta}$.
We assume that the servers are honest additionally. User $j^{\prime}$ with
$j^{\prime}=1,\ldots,m$ receives the variables
$(A_{2j^{\prime}-1,s},B_{2j^{\prime}-1,s})$ and
$(A_{2j^{\prime},s},B_{2j^{\prime},s})$ for $s=1,\ldots,n$, which are
independently subject to the uniform distribution. User $j^{\prime}$ obtains
no information for
$\\{(\bm{x}_{j}^{\prime},\bm{y}_{j}^{\prime},\bm{z}_{j}^{\prime})\\}_{j\in\Theta\setminus\\{j^{\prime}\\}}$
for $j^{\prime}=1,\ldots,m$. Also, User $m+1$ obtains no information expect
for $\bm{X}$, i.e., User $m+1$ can recover the final state on his/her whole
system from $\bm{X}$ and classical information generated by himself/herself.
In addition, even when users in $[m+1]\setminus\Theta$ collude, they obtain no
information except for $\bm{X}$, i.e., they can recover the final state on
their whole system from $\bm{X}$ and classical information generated by
themselves. Hence, the user-secrecy holds.

##  VII Conclusion

We have proposed a new concept, oblivious quantum computation (OQC), and have
introduced its efficient protocol with two servers. In this protocol, two
servers cannot be communicated with each other, but share many prior entangled
states. The input state is masked by the random application of Pauli
operators. The quantum state is transferred between two servers alternately
via quantum teleportation. The user asks each server to apply various
unitaries such that unnecessarily unitary operations are canceled and the
request to each server behaves as a completely random request.

Our protocol is based on the universal gate set composed of the controlled Z
operation, the modification Hadamard gate $\mathsf{H}$, and the $1/8$-phase
gate $\mathsf{T}$. When the number of gates is $m$ and the inputs are composed
of $n$ qubits, the communication complexity of our protocol is upper bounded
by $2n^{2}m+20nm$ bits plus $2n$ qubits. In contrast, even when the input is
restricted into basis states in the $n$ qubits, the application of the
conventional protocol for two-server oblivious transfer requires communication
complexity with exponential size for $n$. Hence, when the number $m$ of gates
is a polynomial, our protocol offers an exponential improvement over existing
methods.

In addition, we have introduced an additional concept, generalized delegated
multiparty quantum computation (GDMQC), by generalizing delegated multiparty
quantum computation (DMQC). In Section VI, modifying our two-server protocol
for OQC, we have proposed a two-server protocol for GDMQC, whose basic idea is
the same as our protocol for OQC.

There are still several other remaining problems. Since the concept, GDMQC, is
very broad, we can expect that it covers various problem settings. Therefore,
it is an interesting future problem to find its fruitful applications. In
addition, the papers [31, 32, 33, 34, 35, 36] discussed the case when servers
potentially collude, but there are more than two servers. It is an interesting
remaining problem to extend our results to the above case with colluding
servers.

Further, our two-server protocol for GDMQC contains a two-server protocol for
conventional delegated quantum computation [13, 14, 15, 16, 17, 18, 19, 20,
21, 22] as a special case by assuming that there is only one user and the
servers’ program $\bm{w}$ is $\bm{e}$. Indeed, it could be possible to verify
this delegated quantum computation protocol by inserting check bits. However,
it is not easy to evaluate how many check bits are needed to achieve a given
precision level because it is difficult to evaluate the probability of
detecting an error with a given dishonest server’s operation. In fact, once
the above detecting probability is evaluated, it is possible to evaluate the
quality of verification by using existing results of the verification with the
non-iid setting [37]. This evaluation is another interesting remaining
problem.

## Acknowledgement

MH was supported in part by the National Natural Science Foundation of China
(Grants No. 62171212).

## References

  * [1] P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring”. Proceedings 35th Annual Symposium on Foundations of Computer Science. IEEE Comput. Soc. Press: 124–134, 1994.
  * [2] M. O. Rabin, “How to exchange secrets by oblivious transfer”, Technical Report TR-81, Harvard University, 1981.
  * [3] Y. Gertner, Y. Ishai, E. Kushilevitz, and T. Malkin, “Protecting data privacy in private information retrieval schemes,” Journal of Computer and Systems Sciences, 60(3):592–629, 2000. Earlier version in STOC 98.
  * [4] D. Mayers, “Unconditionally Secure Quantum Bit Commitment is Impossible,” Phys. Rev. Lett. 78, 3414 (1997).
  * [5] H.-K. Lo, “Insecurity of quantum secure computations,” Phys. Rev. A 56, 1154 (1997).
  * [6] I. Kerenidis and R. de Wolf. “Exponential lower bound for 2-query locally decodable codes via a quantum argument,” Proceedings of 35th ACM STOC, pp. 106–115, 2003.
  * [7] I. Kerenidis and R. de Wolf, “Quantum symmetrically-private information retrieval,” Information Processing Letters, vol. 90, pp. 109–114, 2004.
  * [8] S. Song and M. Hayashi, “Capacity of Quantum Private Information Retrieval with Multiple Servers,” IEEE Transactions on Information Theory, vol. 67, no. 1, pp. 452–463, 2021.
  * [9] C.H. Bennett, G. Brassard, C. Crepeau, R. Jozsa, A. Peres, W.K. Wootters, “Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels,” Phys. Rev. Lett. 70, 1895 (1993)
  * [10] H. Sun and S. Jafar, “The capacity of private information retrieval,” IEEE Transactions on Information Theory, vol. 63, no. 7, pp. 4075–4088, 2017.
  * [11] H. Sun and S. Jafar, “The Capacity of Symmetric Private Information Retrieval,” 2016 IEEE Globecom Workshops (GC Wkshps), Washington, DC, 2016, pp. 1–5.
  * [12] V. Giovannetti, S. Lloyd, and L. Maccone, “Quantum private queries,” Phys. Rev. Lett. 100, 230502 (2008)
  * [13] A. M. Childs, “Secure assisted quantum computation,” Quantum Inf. Comput. 5 456 – 66 (2005).
  * [14] A. Broadbent, J. Fitzsimons and E. Kashefi, “Universal blind quantum computation,” Proc. 50th Annual Symp. on Found. of Comput. Sci. pp 517–26 (2009).
  * [15] S. Barz, E. Kashefi, A. Broadbent, J. F. Fitzsimons, A. Zeilinger, and P. Walther, “Demonstration of blind quantum computing,” Science 335 303, 8, (2012).
  * [16] T. Morimae and K. Fujii “Blind topological measurement-based quantum computation,” Nat. Commun. 3 1036 (2012).
  * [17] T. Morimae, “Verification for measurement-only blind quantum computing,” Phys. Rev. A 89 060302(R) (2014)
  * [18] A. Mantri, C. A. P. Delgado, and J. F. Fitzsimons, “Optimal blind quantum computation,” Phys. Rev. Lett. 111 230502 (2013).
  * [19] T. Morimae and K. Fujii, “Secure entanglement distillation for double-server blind quantum computation,” Phys. Rev. Lett. 111 020502 (2013).
  * [20] Q. Li, W. H. Chan, C. Wu, and Z. Wen, “Triple-server blind quantum computation using entanglement swapping,” Phys. Rev. A 89 040302(R) (2014).
  * [21] Y.-B. Sheng and L. Zhou, “Deterministic entanglement distillation for secure double-server blind quantum computation,” Sci. Rep. 5 7815 (2015).
  * [22] M. Hayashi and T. Morimae, “Verifiable measurement-only blind quantum computing with stabilizer testing, Phys. Rev. Lett. 115 220502 (2015).
  * [23] C. Crepeau, D. Gottesman, and A. Smith. “Secure multi-party quantum computation,” In STOC ’02, 2002. DOI: 10.1145/509907.510000.
  * [24] M. Ben-Or, C. Crepeau, D. Gottesman, A. Hassidim, and A. Smith. “Secure multiparty quantum computation with (only) a strict honest majority,” In FOCS’06, 2006. DOI: 10.1109/focs.2006.68.
  * [25] Y. Dulek, A. B. Grilo, S. Jeffery, C. Majenz, and C. Schaffner, “Secure Multi-party Quantum Computation with a Dishonest Majority,” Advances in Cryptology - EUROCRYPT 2020, Lecture Notes in Computer Science, vol 12107. Springer, Cham.
  * [26] T. Kapourniotis, E. Kashefi, L. Music, and H. Ollivier, “Delegating Multi-Party Quantum Computations vs. Dishonest Majority in Two Quantum Rounds,” arXiv:2102.12949 (2021).
  * [27] V. Dunjko and E. Kashefi, “Blind quantum computing with two almost identical states,” arXiv:1604.01586 (2016).
  * [28] T. Morimae and T. Koshiba, “Impossibility of perfectly-secure one-round delegated quantum computing for classical client,” Quantum Inf. Comput. 19 214–21 (2019).
  * [29] T. Morimae, H. Nishimura, Y. Takeuchi, and S. Tani, “Impossibility of blind quantum sampling for classical client,” Quantum Inf. Comput. 19 793–806 (2019).
  * [30] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press (2010).
  * [31] S. Song and M. Hayashi, “Capacity of Quantum Private Information Retrieval with Collusion of All But One of Servers,” IEEE Journal on Selected Areas in Information Theory, vol. 2, no. 1, pp. 380–390, 2021.
  * [32] S. Song and M. Hayashi, “Capacity of Quantum Private Information Retrieval with Colluding Servers,” IEEE Transactions on Information Theory, Volume: 67, Issue: 7, 5491 – 5508, 2021.
  * [33] M. Allaix, L. Holzbaur, T. Pllaha, and C. Hollanti, “Quantum Private Information Retrieval From Coded and Colluding Servers,” IEEE Journal on Selected Areas in Information Theory, vol. 1, no. 2, 2020.
  * [34] M. Allaix, S. Song, L. Holzbaur, T. Pllaha, M. Hayashi, and C. Hollanti, “On the Capacity of Quantum Private Information Retrieval from MDS-Coded and Colluding Servers,” IEEE Journal on Selected Areas in Communications, vol. 40, no. 3, pp. 885 – 898, 2022.
  * [35] H. Sun and S. Jafar, “The capacity of robust private information retrieval with colluding databases,” IEEE Transactions on Information Theory, vol. 64, no. 4, pp. 2361–2370, 2018.
  * [36] R. Freij-Hollanti, O. W. Gnilke, C. Hollanti, and D. A. Karpuk, “Private information retrieval from coded databases with colluding servers,” SIAM J. Appl. Algebra Geometry, vol. 1, no. 1, pp. 647 – 664, 2017.
  * [37] Z. Li, H. Zhu, and M. Hayashi, “Significance improvement by randomized test in random sampling without replacement,” arXiv: 2211.02399 (2022).