Secure Multiparty Delegated Quantum Computation

This protocol develops the idea of delegation of quantum computation to a server in a multi-party setting with guarantee for secrecy of both the data and the computation. It performs computation on encrypted data in the Measurement Based Quantum Computing framework. This protocol is a direct extension of Universal Blind Quantum Computation (to be linked) in the multiparty setting.

Assumptions

• The clients have secure access to classical multiparty functionalities, which will be treated as oracles.
• A set of malicious clients cannot corrupt the Server, and the other way around.

Outline

The Protocol consists of 2 phases: Preparation phase and Computation phase.

Preparation phase

• Input qubits: For the input qubit states, each client one-time pads their qubit and uses secret sharing schemes to share the secret values with other clients. The honest behaviour for every client is enforced via the given protocol. The server then one-time pads them and measures the one-time padded qubits and announces the measurement values.
• Non-output and non-input qubits: The clients send the qubits in random phases allowed in MBQC. The server then one-time pads them and announces the measurement values.
• Output qubits: The server prepares them in the </math>|+\rangle</math> state.
• Graph state: The server entangles the qubits to a brickwork state.

Computation phase

• Non-output qubits: All clients choose a random bit based on which they compute the measurement angle of the qubits. They send this angle to the server who then returns the result based on the measurement.
• Output qubits: The server sends the encrypted qubits to the corresponding clients. The clients then jointly compute the Pauli corrections and apply them to get the actual output.

Notation

• $n$: Total clients.
• $C_{k}$: Client with index Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} .
• ${\mathcal {C}}_{k}$: Register of client $C_{k}$.
• $S$: Server performing the computation.
• $I$: Set of input qubits.
• $O$: Set of output qubits.
• $O^{c}$: Set of all qubits except the output qubits.
• ${\mathcal {S}}_{k}$: Register of server with register index $k$.
• $t_{j}^{i}$: Outcome of the measurement for the qubit corresponding to $i^{th}$ client for $j^{th}$ qubit.
• $a_{j}$: Random bit chosen by $j^{th}$ client in preparation phase.
• $r_{j}^{k}$: Random bit chosen by $k^{th}$ client for $j^{th}$ qubit in computation phase.
• $\theta _{j}^{j}$: Random phase given by $j^{th}$ client to $j^{th}$ qubit.
• $\delta _{j}$: Measurement angle for encrypted qubit $j$.
• $\phi _{j}$: Measurementangle for $j^{th}$ decrypted qubit.
• $s_{j}^{X}$: $X$ correction term for $j^{th}$ qubit.
• $s_{j}^{Z}$: $Z$ correction term for $j^{th}$ qubit.

Hardware Requirements

• The quantum operations required from the clients are limited to creating $|+\rangle$ states and applying X gates and rotations around the z-axis.

Properties

• There is no need of quantum memory for the clients as the quantum communication from the clients to the server can be done in single-qubit rounds.
• The protocol provides security against a dishonest Server and against a coalition of dishonest clients.
• Security in the more general scenario where a Server and some clients collaborate to cheat is not guaranteed.
• No guarantee is given on the correctness of the computation outcome.
• The protocol uses Verifiable Secret Sharing (VSS) schemes and a computation oracle to calculate the necessary values at each step of the protocol and to ensure that the clients behave honestly.

\section{Pseudo Code}

\begin{algorithm}[H]

   \floatname{algorithm}{Protocol}
   \caption{(Enforcing honest behavior for client </math>C_k</math>)}
   \label{Algo1}
   \begin{enumerate}
       \item Client </math>C_k</math> sends </math>m</math> qubits </math>\ket{+_{\theta_i^k}}=\frac{1}{\sqrt{2}}(\ket{0}+e^{i\theta_i^k}\ket{1})</math> to the Server and secret-shares the values </math>\{\theta_i^k\}_{i=1}^m</math> with all clients, using a VSS scheme.
       \item The Server requests the shared values from the clients for all but one qubit, and measures in the resconstructed bases. If the bases agree with the results of the measurements, then with high probability, the remaining state is correctly formed in relation to the shared angle.
   \end{enumerate}

\end{algorithm}

   %\vspace{0.1in}
   

\begin{algorithm}[H]

   \floatname{algorithm}{Protocol}
   \caption{(State preparation for </math>j\in I</math>)}
   \label{Algo2}

   Server stores states received from clients </math>C_k</math> to distinct registers </math>\mathcal{S}_k\subset \mathcal{S}</math> (</math>k=1,\dots,n</math>);
   
   for </math>k=1,\dots,n-1</math>
   
   \hspace{0.5in}if </math>k=j</math> then
   
   \hspace{1in}break;
   
   \hspace{0.5in}if </math>k=n-1</math> and </math>j=n</math> then
   
   \hspace{1in}break;
   
   \hspace{0.5in}if </math>k=j-1</math>, then
   
   \hspace{1in}CNOT on </math>\mathcal{S}_k\otimes\mathcal{S}_{k+2}</math>;
   
   \hspace{0.5in}else
   
   \hspace{1in}CNOT on </math>\mathcal{S}_k\otimes\mathcal{S}_{k+1}</math>;
   
   \hspace{0.5in}end;
   
   \hspace{0.5in}measure state in </math>\mathcal{S}_k</math> and get outcome </math>t_j^k</math>;
   
   end;
   
   if </math>j=n</math> then 
   
   \hspace{0.5in} CNOT on </math>\mathcal{S}_{n-1}\otimes\mathcal{S}_n</math>;
   
   \hspace{0.5in}measure state in </math>\mathcal{S}_{n-1}</math> and get outcome </math>t_n^{n-1}</math>;
   
   else
   
   \hspace{0.5in}CNOT on </math>(\mathcal{S}_{n}\otimes\mathcal{S}_j)</math>;
   
   \hspace{0.5in}measure state in </math>\mathcal{S}_n</math> and get outcome </math>t_j^n</math>;
   
   end;
   

\end{algorithm}

\begin{figure}[H]

   \centerline{
   \Qcircuit @C=0.5em @R=1.5em {
   \lstick{C_1:20:28, 17 April 2019 (CEST)20:28, 17 April 2019 (CEST)\ket{+_{\theta_j^1}}}	&\qw	&\targ &\meter	&	\cw 	& t_j^1\\	
   \lstick{C_2:20:28, 17 April 2019 (CEST)20:28, 17 April 2019 (CEST)\ket{+_{\theta_j^2}}}  	&\qw		&\ctrl{-1}&\qw	&\targ		 &	\meter 	&	\cw		&	t_j^2\\
   \lstick{C_3:20:28, 17 April 2019 (CEST)20:28, 17 April 2019 (CEST)\ket{+_{\theta_j^3}}} 	&\qw		&\qw	  &\qw	  	&\ctrl{-1}		&\qw &\targ{+1} & \meter	&	\cw		& \cw	&Shraddha (talk) 20:28, 17 April 2019 (CEST)  t_j^3\\
   \lstick{\vdots \hspace{1in}\vdots}  				&				 &		   &		&		 &			&	\vdots	&		&	& & & & 	&  &  & & \ddots \\
   \lstick{C_n:20:28, 17 April 2019 (CEST)20:28, 17 April 2019 (CEST)\ket{+_{\theta_j^n}}}				&\qw   			 &\qw 	   &\qw		& \qw	 &\qw		&\qw		&\qw	&\qw	& \qw	&\qw	&\qw &\qw & \qw &\ctrl{-1}		&\qw &\targ & \meter	&	\cw		& \cw &20:28, 17 April 2019 (CEST)~	t_j^n\\
   \lstick{C_j:~X^{a_j}Z(\theta_j^j)\big[\mathcal{C}_j\big] } 	Shraddha (talk) 20:28, 17 April 2019 (CEST)			&\qw   			 &\qw 	   &\qw		& \qw	 &\qw		&\qw		&\qw	&\qw	& \qw	&\qw	&\qw & \qw & \qw	& \qw	&\qw	& \ctrl{-1}	&\qw & \qw & & &\hspace{0.7in}X^{a_j}Z(\theta_j)\big[\mathcal{C}_j\big] \\\\
                        }		
       }
       \caption{Remote State Preparation with quantum input (Protocol \ref{Algo2}). Client </math>C_j</math> performs a one-time pad on his register </math>\mathcal{C}_j</math> and the result of the circuit remains one-time padded, where </math>\theta_j=\theta_j^j+\sum_{k=1,k\neq j}^n (-1)^{\bigoplus_{i=k}^n t_j^i+a_j}\theta_j^k</math>.}\label{fig:algo1}

\end{figure}

   \vspace{0.3in}

\begin{algorithm}[H]

   \floatname{algorithm}{Protocol}
   \caption{(State preparation for </math>j\in O^c\setminus I</math>)}
   \label{Algo3}
   Server stores states received from clients </math>C_k</math> to distinct registers </math>\mathcal{S}_k\subset \mathcal{S}</math> (</math>k=1,\dots,n</math>);
   
   for </math>k=1,\dots,n-1</math>
   
   \hspace{0.5in}CNOT on </math>\mathcal{S}_k\otimes\mathcal{S}_{k+1}</math>;
   
   \hspace{0.5in}measure state in </math>\mathcal{S}_k</math> and get outcome </math>t_j^k</math>;
   
   end;

\end{algorithm}

\vspace{0.2in}

\begin{figure}[H]

   \centerline{
   \Qcircuit @C=0.5em @R=1.5em {
   \lstick{C_1:Shraddha (talk) 20:28, 17 April 2019 (CEST)\ket{+_{\theta_j^1}}}	&\qw  &\targ &\meter	&	\cw 	& t_j^1\\	
   \lstick{C_2:Shraddha (talk) 20:28, 17 April 2019 (CEST)\ket{+_{\theta_j^2}}}  	&\qw		&\ctrl{-1}&\qw	&\targ		 &	\meter 	&	\cw		&	t_j^2\\
   \lstick{C_3:Shraddha (talk) 20:28, 17 April 2019 (CEST)\ket{+_{\theta_j^3}}} 	&\qw		&\qw	  &\qw	  	&\ctrl{-1}		&\qw &\targ & \meter	&	\cw		& \cw	&Shraddha (talk) 20:28, 17 April 2019 (CEST)  t_j^3\\
   \lstick{\vdots \hspace{0.7in}\vdots}  \hspace{0.5in}				&				 &		   &		&		 &			&	\vdots	&		&	& & & & 	&  &  & & \ddots \\
   \lstick{C_{n-1}:\hspace{0.1in}\ket{+_{\theta_j^{n-1}}}}				&\qw   			 &\qw 	   &\qw		& \qw	 &\qw		&\qw		&\qw	&\qw	& \qw	&\qw	&\qw &\qw & \qw &\ctrl{-1}		&\qw &\targ & \meter	&	\cw		& \cw & 20:28, 17 April 2019 (CEST)	t_j^{n-1}\\
   \lstick{C_n:Shraddha (talk) 20:28, 17 April 2019 (CEST)\ket{+_{\theta_j^n}}}				&\qw   			 &\qw 	   &\qw		& \qw	 &\qw		&\qw		&\qw	&\qw	& \qw	&\qw	&\qw & \qw & \qw	& \qw	&\qw	& \ctrl{-1}	&\qw & \qw & & &\hspace{0.3in}\mathbf{\ket{+_{\theta_j}}}\\
                        }		
       }
   \caption{Remote State Preparation without quantum input (Protocol \ref{Algo3}), where </math>\theta_j=\theta_j^n+\sum_{k=1}^{n-1} (-1)^{\bigoplus_{i=k}^{n-1} t_j^i}\theta_j^k</math>.}\label{fig:algo2}

\end{figure}

\begin{algorithm}[!h]

   \caption{Multiparty Quantum Computing Protocol}
   \label{protocol}
   \begin{itemize}
       \item A quantum input </math>\rho_{in}</math> and measurement angles </math>\{\phi_j\}_{j=1}^q</math> for qubits </math>j\in O^c</math> .
   \end{itemize}
   
   \underline{\emph{Preparation phase}}
   \begin{description}
       \item[quantum input:] For </math>j\in I</math> 
       \begin{enumerate}
           \item Client </math>C_j</math> applies a one-time pad </math>X^{a_j}Z(\theta_j^j)</math> to his qubit, where </math>a_j\in_R\{0,1\}</math> and </math>\theta_j^j\in_R\{l\pi/4\}_{l=0}^7</math> and sends it to the Server. He secret-shares the values </math>a_j</math> and </math>\theta_j^j</math> with the other clients.
           \item Each client </math>C_k (k\neq j)</math>, runs Protocol \ref{Algo1} with the Server. If all clients pass the test, the Server at the end has </math>n-1</math> states </math>\ket{+_{\theta_j^k}}=\frac{1}{\sqrt{2}}\big(\ket{0}+e^{i\theta_j^k}\ket{1}  \big)</math> for </math>k\neq j</math>.
           \item The Server runs Protocol \ref{Algo2} and announces outcome vector </math>\mathbf{t}_j</math>. \\
       \end{enumerate}\vspace{-0.1in}
       At this point the Server has the state  </math>\rho'_{in}=\big(X^{a_1}Z(\theta_1)\otimes \dots \otimes X^{a_n} Z(\theta_n)\otimes \mathbf{1}_{\mathcal{R}}\big)\cdot \rho_{in}</math>, where 
       \begin{equation}\label{eq:entangle1}
           \theta_j=\theta_j^j+\sum_{k=1, k\neq j}^n (-1)^{\bigoplus_{i=k}^n t_j^i+a_j}\theta_j^k
       \end{equation}
       \item[non-output / non-input qubits:] For </math>j\in O^c\setminus I</math> 
       \begin{enumerate}
           \item[4.] All clients </math>C_k</math>, </math>k\in[n]</math>  run Protocol \ref{Algo1} with the Server. If all clients pass the test, the Server at the end has </math>n</math> states </math>\ket{+_{\theta_j^k}}=\frac{1}{\sqrt{2}}\big(\ket{0}+e^{i\theta_j^k}\ket{1}  \big)</math> for </math>k=1,\dots,n</math>.
           \item[5.] The Server runs Protocol \ref{Algo3} getting outcome vector </math>\mathbf{t}_j</math>. He ends up with the state </math>\ket{+_{\theta_j}}</math>, where:
           \begin{equation}\label{eq:entangle2}
               \theta_j=\theta_j^n+\sum_{k=1}^{n-1} (-1)^{\bigoplus_{i=k}^{n-1} t_j^i}\theta_j^k
           \end{equation}
       \end{enumerate}
       \item[output qubits:] For </math>j\in O</math>, the Server prepares </math>\ket{+}</math> states.
       \item[graph state:] The Server entangles the </math>n+q</math> qubits to a brickwork state by applying ctrl-</math>Z</math> gates.
   
   \end{description}
       
   \begin{flushleft}
       \underline{\emph{Computation phase}}
       \vspace{-7pt}
   \end{flushleft}
   
   \begin{description}
       \item[non-output qubits:] For </math>j\in O^c</math>
       \begin{enumerate}
           \item All clients </math>C_k</math>, </math>k=1,\dots,n</math> choose random </math>r_j^k\in\{0,1\}</math>, which they secret-share with the other clients. Then using a computation oracle, they compute the measurement angle of qubit </math>j</math>:
           \begin{equation}\label{angle}
               \delta_j:=\phi'_j+\pi r_j+\theta_j
           \end{equation}
           where undefined values are equal to zero, or otherwise:
           \begin{itemize}
               \item </math>\phi'_j=(-1)^{a_j+s_j^X}\phi_j+s^Z_j\pi+a_{f^{-1}(j)}\pi</math>.
               \item </math>r_j=\bigoplus\limits_{k=1}^n r_j^k</math>.
               \item </math>s_i=b_i\oplus r_i</math>, for </math>i\leq j</math>.
           \end{itemize}
           \item The Server receives </math>\delta_j</math> and measures qubit </math>j</math> in basis </math>\{\ket{+_{\delta_j}},\ket{-_{\delta_j}}\}</math>, getting result </math>b_j</math>. He announces </math>b_j</math> to the clients.
       \end{enumerate}
       \item[output qubits:] For </math>j\in O</math>, the Server sends the ``encrypted quantum state to client </math>C_{j-q}</math>. All participants jointly compute </math>s_j^X</math> and </math>s_j^Z</math> and send it to client </math>C_{j-q}</math>, who applies operation </math>Z^{s_j^Z}X^{s_j^X}</math> to retrieve the actual quantum output. 
   \end{description}

\end{algorithm}

Further Information

*contributed by Natansh Mathur