Quantum Protocol Zoo - User contributions [en]

Protocol Library

2019-10-28T15:04:55Z

Limacher: Quantum Secret Sharing added

{| class="wikitable"
!width="40%"|Functionality
!width="60%"|Protocols
|-
|rowspan="2"|[[Anonymous Transmission]]||[[GHZ-based Quantum Anonymous Transmission]]
|-
|[[Verifiable Quantum Anonymous Transmission]]
|-
|rowspan="2"|[[Authentication of Quantum Messages]]||[[Clifford based Quantum Authentication]]
|-
|[[Polynomial Code based Quantum Authentication]]
|-
||[[Byzantine Agreement]]||[[Fast Quantum Byzantine Agreement]]
|-
||[[Bit Commitment]]||[[Quantum Bit Commitment]]
|-
||[[Coin Flipping]]||[[Quantum Coin Flipping]]
|-
|rowspan="8"|[[Quantum Digital Signature|(Quantum) Digital Signature]] |||[[Gottesman and Chuang Quantum Digital Signature]]
|-
|[[Prepare and Measure Quantum Digital Signature]]
|-
|[[Measurement Device Independent Quantum Digital Signature (MDI-QDS)]]
|-
|[[Arbitrated Quantum Digital Signature]]
|-
|[[Blind Delegation of Quantum Digital Signature]]
|-
|[[Designated Verifiable Quantum Signature]]
|-
|[[Limited Delegation of Quantum Digital Signature]]
|-
|[[Quantum Proxy Signature]]
|-
||[[Entanglement Verification]]||[[Multipartite Entanglement Verification]]
|-
||[[Fingerprinting]]||[[Quantum Fingerprinting]]
|-
|[[Quantum Identity Authentication]]||[[-]]
|-
|rowspan="4"|[[Quantum Key Distribution|(Quantum) Key Distribution]]||[[BB84 Quantum Key Distribution]]
|-
|[[Measurement Device Independent Quantum Key Distribution (MDI-QKD)]]
|-
|[[Device-Independent Quantum Key Distribution]]
|-
|[[Continuous-Variable Quantum Key Distribution (CV-QKD)]]
|-
||[[Leader Election]]||[[Quantum Leader Election]]
|-
|rowspan="4"|[[Quantum Money|(Quantum) Money]]||[[Quantum Cheque]]
|-
|[[Quantum Coin]]
|-
|[[Quantum Token]]
|-
|[[Wiesner Quantum Money]]
|-
||[[Oblivious Transfer]]||[[Quantum Oblivious Transfer]]
|-
|rowspan="2"| [[Quantum Secret Sharing|Secret Sharing]] ||[[Quantum Secret Sharing using GHZ States]]
|-
|[[Verifiable Quantum Secret Sharing]]
|-
|rowspan="5"| [[Secure Client- Server Delegated Quantum Computation]] ||[[Classical Fully Homomorphic Encryption for Quantum Circuits]]
|-
|[[Measurement-Only Universal Blind Quantum Computation]]
|-
| [[Prepare-and-Send Quantum Fully Homomorphic Encryption]]
|-
|[[Prepare-and-Send Universal Blind Quantum Computation]]
|-
|[[Pseudo-Secret Random Qubit Generator (PSQRG)]]
|-
|rowspan="3"|[[Secure Verifiable Client-Server Delegated Quantum Computation]]||[[Prepare-and-Send Verifiable Universal Blind Quantum Computation]]
|-
|[[Measurement-Only Verifiable Universal Blind Quantum Computation]]
|-
|[[Prepare-and-Send Verifiable Quantum Fully Homomorphic Encryption]]
|-
|rowspan="2"|[[Secure Delegated Classical Computation]]||[[Secure Client-Server Classical Delegated Computation]]
|-
|[[Secure Multiparty Delegated Classical Computation]]
|-
|rowspan="2"|[[Secure Multi-Party Delegated Computation]]||[[Secure Multiparty Delegated Quantum Computation]]
|-
|[[Secure Multiparty Delegated Classical Computation]]
|-
|rowspan="2"|[[Teleportation|(Quantum) Teleportation]]||[[Quantum Teleportation|State Teleporation]]
|-
|[[Gate Teleporation]]
|-
|[[Verification of Universal Quantum Computation]]||[[Interactive Proofs for Quantum Computation|Quantum Prover Interactive Proofs]]
|-
|[[Verification of Sub-Universal Quantum Computation]]||[[-]]
|-
|[[Verification of NP-complete problems]]||[[-]]
|-
|[[Classical Verification of Universal Quantum Computation]]||[[-]]
|-
||-||[[Weak String Erasure]]
|-
{| class="wikitable"
!width="40%"|Nodal Subroutine
!width="60%"|Types
|-
||[[Quantum Cloning]]
|-
||[[Universal Superposition of Orthogonal States|Superposition]]
|-
|rowspan="3"|[[Quantum Random Number Generator]]||[[Certified finite randomness expansion]]
|-
|[[Certified infinite randomness expansion]]
|-
|[[Randomness amplification (8 devices)]]

Quantum Secret Sharing

2019-09-13T16:15:48Z

Limacher: Second batch

==Functionality Description==
Quantum Secret Sharing (QSS) allows to transfer a quantum state (or a classical message encoded as quantum state), referred to as the secret, from Alice to Bob but only with the consent of a third-party, Charlie. A QSS protocol is generalizable to an arbitrary number of parties consisting of one sender, one recipient, and all other parties being endorsers. In case of only two parties, sender and receiver, QSS is equivalent to [[Quantum Teleportation]]. Despite the no-cloning theorem not allowing the quantum secret to be in possession of more than one party at the same time, there exist QSS protocols that mimic classical secret sharing (see [[Quantum Secret Sharing#Further Details|Further Information]]).

'''Tags:''' [[:Category: Building Blocks|Building Blocks]], [[:Category: Multi Party Protocols|Multi Party]], [[:Category: Quantum Enhanced Classical Functionality|Quantum Enhanced Classical Functionality]]

[[Category: Two Party Protocols]] [[Category: Quantum Enhanced Classical Functionality]]

== Use Cases ==
* QSS can replace certain classical secret sharing scenarios with unconditional security.[[Quantum Secret Sharing#References|(1)]]
* Secret sharing is a very common building block in other protocols:[[Quantum Secret Sharing#References|(2)]]
** [[Secure Multiparty Delegated Quantum Computation]]
** Leader election and [[Fast Quantum Byzantine Agreement|Byzantine Agreement]]
** Error correction in quantum computers[[Quantum Secret Sharing#References|(3)]]
** Bank transfers with third party endorsement, see [[Quantum Cheque]]

==Protocols==
#[[Quantum Secret Sharing using GHZ States]][[Quantum Secret Sharing#References|(4)]]
#[[Verifiable Quantum Secret Sharing]] (VQSS)

==Properties==
* Confidentiality: QSS with one dishonest party not following the protocol must guarantee that no information about the quantum secret at all is revealed to any party.
* Security: Every protocol must ensure that no information about the secret is leaked to an external eavesdropper.

==Further Information==
QSS is inspired by classical secret sharing (CSS), but has one fundamental difference due to the no-cloning theorem. In CSS, Alice shares a secret among <math>n</math> parties and any team of <math>t</math> parties or more, with <math>t \leq n</math>, has full access to the secret, whereas <math>t-1</math> collaborating parties or less have no information about the secret at all. Such <math>(t, n)</math>-threshold schemes are not straightforward to implement for QSS, since the no-cloning theorem forbids that quantum states are copied, resulting in only one party, the receiver, obtaining the quantum secret from Alice, who looses hers during the process. However, <math>(t, n)</math> schemes can be built through sequentially running several QSS rounds.[[Quantum Secret Sharing#References|(5)]]

==References==
#[https://arxiv.org/abs/quant-ph/9802025 Mayers (2001)]
#[https://arxiv.org/abs/1807.03219 Joy et al (2018)]
#[https://arxiv.org/abs/quant-ph/9910067 Gottesman (1999)]
#[https://arxiv.org/abs/quant-ph/9806063 Hillery et al (1998)]
#[https://arxiv.org/abs/1710.11600 Lu et al (2018)]

<div style='text-align: right;'>''contributed by Peter Limacher''</div>

Quantum Secret Sharing

2019-09-13T14:34:57Z

Limacher: Initial filling with text

==Functionality Description==
Quantum Secret Sharing (QSS) allows to transfer a quantum state (or a classical message encoded as quantum state), referred to as the secret, from Alice to Bob but only with the consent of a third-party, Charlie. A QSS protocol is generalizable to an arbitrary number of parties always consisting of one sender, one recipient, and all other parties being endorsers. In case of only two parties, sender and receiver, QSS is equivalent to [[Quantum Teleportation]]. QSS with one dishonest party not following the protocol must guarantee that no information about the quantum secret at all is revealed to any party.

'''Tags:''' [[:Category: Building Blocks|Building Blocks]], [[:Category: Multi Party Protocols|Multi Party]], [[:Category: Quantum Enhanced Classical Functionality|Quantum Enhanced Classical Functionality]]

[[Category: Two Party Protocols]] [[Category: Quantum Enhanced Classical Functionality]]

== Use Cases ==
* QSS can replace certain classical secret sharing scenarios with unconditional security.[[Quantum Secret Sharing#References|(1)]]
* Secret sharing is a very common building block in other protocols:[[Quantum Secret Sharing#References|(2)]]
** [[Secure Multiparty Delegated Quantum Computation]]
** Leader election and [[Fast Quantum Byzantine Agreement|Byzantine Agreement]]
** Error correction in quantum computers[[Quantum Secret Sharing#References|(3)]]
** Bank transfers with third party endorsement, see [[Quantum Cheque]]

==Protocols==
(under construction)

==Properties==
QSS is inspired by classical secret sharing (CSS), but has one fundamental difference due to the no-cloning theorem. In CSS, Alice shares a secret among <math>n</math> parties and any team of <math>t</math> parties or more, with <math>t \leq n</math>, has full access to the secret, whereas <math>t-1</math> collaborating parties or less have no information about the secret at all. Such <math>(t, n)</math>-threshold schemes are not possible for QSS, since the no-cloning theorem forbids that quantum states are copied, resulting in only one party, the receiver, obtaining the quantum secret from Alice, who looses hers at the same. So in contrast to CSS, there are always <math>n</math> parties in QSS that all must collaborate by adhering to the protocol, in order that one party will receive the secret from Alice.

==References==
#[https://arxiv.org/abs/quant-ph/9802025 Mayers (2001)]
#[https://arxiv.org/abs/1807.03219 Joy et al (2018)]
#[https://arxiv.org/abs/quant-ph/9910067 Gottesman (1999)]
#[https://arxiv.org/abs/quant-ph/9806063 Hillery et al (1998)]

<div style='text-align: right;'>''contributed by Peter Limacher''</div>

Quantum Secret Sharing

2019-09-11T12:23:55Z

Limacher: Page created

==Functionality Description==
(under construction)

'''Tags:''' [[:Category: Building Blocks|Building Blocks]], [[:Category: Multi Party Protocols|Multi Party]], [[:Category: Quantum Enhanced Classical Functionality|Quantum Enhanced Classical Functionality]]

[[Category: Two Party Protocols]] [[Category: Quantum Enhanced Classical Functionality]]

== Use Cases ==
* QSS can replace classical secret sharing protocols.
* Secret sharing is a very common building block for other protocols like (under construction).

==Protocols==
(under construction)

==Properties==
(under construction)

==References==
#[https://arxiv.org/abs/quant-ph/9806063 Hillery et al (1998)]
#[https://arxiv.org/abs/quant-ph/9910067 Gottesman (1999)]

<div style='text-align: right;'>''contributed by Peter Limacher''</div>

Secure Multiparty Delegated Quantum Computation

2019-09-11T11:37:30Z

Limacher: /* Outline */

This [https://arxiv.org/abs/1606.09200 example protocol] achieves the functionality of [[Secure Client- Server Delegated Computation|Delegation Quantum Computation]] to a server for multiple Clients with the guarantee that Server is unknown of any Clients' inputs, outputs, and computation. This protocol is an extension of [[Prepare-and-Send Universal Blind Quantum Computation]] in the multiparty setting.

'''Tags:''' [[:Category:Multi Party Protocols|Multi Party Protocols]], [[:Category:Quantum Functionality|Quantum Functionality]], [[:Category:Universal Task|Universal Task]]
[[Category:Multi Party Protocols]] [[Category:Quantum Functionality]][[Category:Universal Task]]

==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 [[Quantum Secret Sharing|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==

* <math>n</math>: Total clients.
* <math>C_k</math>: Client with index <math>k</math>.
* <math>\mathcal{C}_k</math>: Register of client <math>C_k</math>.
* <math>S</math>: Server performing the computation.
* <math>I</math>: Set of input qubits.
* <math>O</math>: Set of output qubits.
* <math>O^c</math>: Set of all qubits except the output qubits.
* <math>\mathcal{S}_k</math>: Register of server with register index <math>k</math>.
* <math>t^i_j</math>: Outcome of the measurement for the qubit corresponding to <math>i^{th}</math> client for <math>j^{th}</math> qubit.
* <math>a_j</math>: Random bit chosen by <math>j^{th}</math> client in preparation phase.
* <math>r^k_j</math>: Random bit chosen by <math>k^{th}</math> client for <math>j^{th}</math> qubit in computation phase.
* <math>\theta^j_j</math>: Random phase given by <math>j^{th}</math> client to <math>j^{th}</math> qubit.
* <math>\delta_j</math>: Measurement angle for encrypted qubit <math>j</math>.
* <math>\phi_j</math>: Measurementangle for <math>j^{th}</math> decrypted qubit.
* <math>s^X_j</math>: <math>X</math> correction term for <math>j^{th}</math> qubit.
* <math>s^Z_j</math>: <math>Z</math> correction term for <math>j^{th}</math> qubit.

==Requirements==

* The quantum operations required from the clients are limited to creating <math>|+\rangle</math> states and applying X gates and rotations around the z-axis.

<br/>

[[File:SMPDQC_Server.PNG|center|Secure Multiparty Delegated Quantum Computation (Server)]]

<br/>

[[File:SMPDQC_Client.PNG|center|Secure Multiparty Delegated Quantum Computation (Client)]]

==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.

==Protocol Description==
*Enforcing honest behavior for client <math>C_k</math>
# Client <math>C_k</math> sends <math>m</math> qubits <math>|+_{\theta_i^k}\rangle=\frac{1}{\sqrt{2}}(|0\rangle+e^{i\theta_i^k}|1\rangle)</math> to the Server and secret-shares the values <math>\{\theta_i^k\}_{i=1}^m</math> with all clients, using a VSS scheme.
# 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.
*State preparation for <math>j\in I</math>)
#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>
###if <math>k=j</math> '''then''' break;
###if <math>k=n-1</math> and <math>j=n</math> '''then''' break;
###if <math>k=j-1</math>, '''then'''
####CNOT on <math>\mathcal{S}_k\otimes\mathcal{S}_{k+2}</math>;
###'''else'''
####CNOT on <math>\mathcal{S}_k\otimes\mathcal{S}_{k+1}</math>;
###measure state in <math>\mathcal{S}_k</math> and get outcome <math>t_j^k</math>;
##if <math>j=n</math> '''then'''
###CNOT on <math>\mathcal{S}_{n-1}\otimes\mathcal{S}_n</math>;
####Measure state in <math>\mathcal{S}_{n-1}</math> and get outcome <math>t_n^{n-1}</math>;
##else
###CNOT on <math>(\mathcal{S}_{n}\otimes\mathcal{S}_j)</math>;
####Measure state in <math>\mathcal{S}_n</math> and get outcome <math>t_j^n</math>;

\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 &[[User:Shraddha|Shraddha]] ([[User talk: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] } [[User:Shraddha|Shraddha]] ([[User talk: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}

====State preparation for (<math>j\in O^c\setminus I</math>)====

# 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>
## CNOT on <math>\mathcal{S}_k\otimes\mathcal{S}_{k+1}</math>;
## Measure state in <math>\mathcal{S}_k</math> and get outcome <math>t_j^k</math>;

\begin{figure}[H]
\centerline{
\Qcircuit @C=0.5em @R=1.5em {
\lstick{C_1:[[User:Shraddha|Shraddha]] ([[User talk:Shraddha|talk]]) 20:28, 17 April 2019 (CEST)\ket{+_{\theta_j^1}}} &\qw &\targ &\meter & \cw & t_j^1\\
\lstick{C_2:[[User:Shraddha|Shraddha]] ([[User talk: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:[[User:Shraddha|Shraddha]] ([[User talk:Shraddha|talk]]) 20:28, 17 April 2019 (CEST)\ket{+_{\theta_j^3}}} &\qw &\qw &\qw &\ctrl{-1} &\qw &\targ & \meter & \cw & \cw &[[User:Shraddha|Shraddha]] ([[User talk: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:[[User:Shraddha|Shraddha]] ([[User talk: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}

====Multiparty Quantum Computing Protocol====
* 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> .

'''Preparation phase'''

''Quantum input'': For <math>j\in I</math>

# 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.
# Each client <math>C_k (k\neq j)</math>, runs Protocol 1 with the Server. If all clients pass the test, the Server at the end has <math>n-1</math> states <math>|+_{\theta_j^k}\rangle=\frac{1}{\sqrt{2}}\big(|0\rangle+e^{i\theta_j^k}|1\rangle \big)</math> for <math>k\neq j</math>.
# The Server runs Protocol2 and announces outcome vector <math>\mathbf{t}_j</math>.
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
<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>
# [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}

<div style='text-align: right;'>''*contributed by Natansh Mathur''</div>