Quantum Protocol Zoo - User contributions [en]

Quantum Coin

2020-01-23T11:07:20Z

129.215.91.184: /* Notations */

This [http://users.math.cas.cz/~gavinsky/papers/QuMoClaV.pdf example protocol] is a private-key protocol which implements Quantum Money, a unique object generated by a Trusted Third Party (TTP). It is then circulated among untrusted clients (Transferability). Each client should be able to prove the authenticity of his owned quantum money to a verifier. On the other hand, an adversary must fail in counterfeiting the quantum money with overwhelmingly high probability (Unforgeability). <br>

'''Tags:''' [[:Category: Multi Party Protocols|Multi Party Protocols]], [[:Category: Quantum Enhanced Classical Functionality|Quantum Enhanced Classical Functionality]], [[:Category: Specific Task|Specific Task]], Prepare (bank) and Measure (client)
[[Category: Specific Tasks]]
[[Category: Quantum Enhanced Classical Functionality]]
[[Category: Multi Party Protocols]]

== Outline ==
In this scheme, a Trusted Third Party (TTP) and a coin holder run the following procedure for generating and verifying a quantum coin:<br>
* '''Quantum coin Generation''' - The TTP chooses k random 4-bit strings, keeps them in secret and produce k quantum states. A newly issued quantum coin consists of a piece of paper glued to k quantum registers that hold k quantum states. The piece of paper contains a unique identification tag and k initially unmarked positions, where the i-th position has to be marked in k-bit classical register P when the corresponding quantum state is used in the verification protocol.
* '''Quantum coin Verification''' - To verify a quantum coin through classical communication with the TTP, its holder sends the identification number of the quantum coin to the TTP. Then, the TTP and the coin holder exchange some classical information for choosing some quantum registers. The coin holder measures the chosen registers and sends their corresponding classical information to the TTP. The TTP verifies the authenticity of the coin by the secret information he possesses.
==Notations==
* <math>HMP_4</math>-states: <math>|\alpha(x)\rangle=\dfrac{1}{2}\sum_{1\leq i\leq4}(-1)^{x_i}|i\rangle</math>, <math>x\in\{0, 1\}^4</math>
* for <math>m, a, b \in \{0, 1\}</math>, <math>(x, m, a, b) \in HMP_4 </math> if <math> b = \begin{cases}
x_1 \oplus x_{2+m} & \text{if } a = 0 \\
x_{3-m} \oplus x_4 & \text{if } a = 1 \end{cases}</math>

* <math>HMP_4</math>-queries: An <math>HMP_4</math>-query is an element <math>m \in \{0, 1\}</math>. A valid answer to the query w.r.t. <math>x \in \{0, 1\}^4</math> is a pair <math>(a, b) \in \{0, 1\} \times \{0, 1\}</math>, such that <math>(x, m, a, b) \in HMP_4</math>. An <math>HMP_4</math> -state can be used to answer an <math>HMP_4</math> -query with certainty: If <math> m = 0 </math>, let
<math> v_1 \overset{def}{=}\dfrac{|1\rangle+|2\rangle}{\sqrt{2}} </math> <math> v_2 \overset{def}{=}\dfrac{|1\rangle-|2\rangle}{\sqrt{2}} </math> <math> v_3 \overset{def}{=}\dfrac{|3\rangle+|4\rangle}{\sqrt{2}} </math> <math> v_4 \overset{def}{=}\dfrac{|3\rangle-|4\rangle}{\sqrt{2}} </math>
otherwise (m = 1), let
<math> v_1 \overset{def}{=}\dfrac{|1\rangle+|3\rangle}{\sqrt{2}} </math> <math> v_2 \overset{def}{=}\dfrac{|1\rangle-|3\rangle}{\sqrt{2}} </math> <math> v_3 \overset{def}{=}\dfrac{|2\rangle+|4\rangle}{\sqrt{2}} </math> <math> v_4 \overset{def}{=}\dfrac{|2\rangle-|4\rangle}{\sqrt{2}} </math>

Measure <math>|\alpha(x_i)\rangle</math> in the basis <math>{v_1, v_2, v_3, v_4}</math>, and let <math>(a, b)</math> be <math>(0, 0)</math> if the outcome is <math>v_1</math>; <math>(0, 1)</math> in the case of <math>v_2</math>; <math>(1, 0)</math> in the case of <math>v_3</math>; <math>(1, 1)</math> in the case of <math>v_4</math>. Then <math>(x, m, a, b) \in HMP_4</math> always.

==Requirements==
*Network stage: [[:Category: Quantum Memory Network Stage|quantum memory network]][[Category:Quantum Memory Network Stage]].

==Knowledge Graph==

{{graph}}

== Properties ==
* '''General Features''':
** No need to quantum communication for quantum coin verification.
** The classical communication channel used for verification can be unencrypted.
** The database of the bank is static, and therefore many de-centralized “verification branches” can exist that do not have to communicate with one another.
** The number of verifications that a quantum coin can go through is limited.

*'''Security Claims''':
**The coins are exponentially hard to counterfeit.
**Secure against an adversary who uses adaptive “attempted verifications” in order to collect information about a coin.

==Protocol Description==
'''Stage 1: Quantum coin generation'''<br>
''Input'': A secret record consists of <math>k</math> entries <math>x_1, . . . , x_k</math>,<math> x_i\in \{0,1\}^4</math><br>
''Output'': A “fresh” quantum coin<br>
The Trusted Third Party (TTP) chooses <math>x_1, . . . , x_k\in\{{0, 1}\}^4</math> at random, keeps them in secret and produces quantum states <math>|\alpha(x_1)\rangle, . . . , |\alpha(x_k)\rangle</math>.
A “fresh” quantum coin corresponding to this record consists of:
* <math>k</math> quantum registers consisting of 2 qubits each, where the <math>i</math>-th register contains <math>|\alpha(x_i)\rangle</math>;
* a <math>k</math>-bit classical register <math>P</math>, that is initially set to <math>0^k</math>;
* a unique identification number.

'''Stage 2: Quantum coin verification'''<br>
''Input'': the identification number of the quantum coin<br>
''Output'': Accept or Reject<br>
<br>
This stage is run as follows:
* The holder sends the identification number of the quantum coin to the TTP.
* The TTP chooses uniformly at random a set <math>L_{bn}\subset[k]</math> of size <math>t</math>, and sends it to the coin holder.
* The holder consults with P and chooses uniformly at random a set <math>L_{hl} \subset L_{bn}</math> consisting of <math>2t/3</math> yet unmarked positions. He sends <math>L_{hl}</math> to the bank and marks in <math>P</math> all the elements of <math>L_{hl}</math> as used.
* The TTP chooses at random <math>2t/3</math> values <math>m_i \in\{{0, 1}\}</math>, one for each <math>i \in L_{hl}</math> , and sends them to the coin holder.
* The holder measures the quantum registers corresponding to the elements of <math>L_{hl}</math> in order to produce <math>2t/3</math> pairs <math>(a_i, b_i)</math> (refer to <math>HMP_4</math>-queries in Notations), such that <math>(x_i,m_i, a_i, b_i)\in HMP_4</math> for all <math>i \in L_{hl}</math>. He sends the list of <math>(a_i, b_i)</math>s to the TTP.
* The TTP checks whether <math>(x_i,m_i, a_i, b_i)\in HMP_4</math> for all <math>i \in L_{hl}</math>, in which case it confirms validity of the quantum coin. Otherwise, the coin is declared to be a counterfeit.

==Further Information==
Gavinsky, Dmitry. "Quantum money with classical verification." 2012 IEEE 27th Conference on Computational Complexity. IEEE, 2012, Available at: http://users.math.cas.cz/~gavinsky/papers/QuMoClaV.pdf

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

Measurement-Only Universal Blind Quantum Computation

2019-10-25T11:06:18Z

129.215.91.184:

The [https://journals.aps.org/pra/abstract/10.1103/PhysRevA.87.050301 example protocol] achieves the functionality of [[Secure Client- Server Delegated Computation]] by assigning quantum computation to an untrusted device while maintaining privacy of the input, output and computation of the client. The client requires to be able to prepare and send quantum states while the server requires to possess a device with quantum memory, measurement and entanglement generation technology. Following description deals with a method which involves quantum online and classical online communication, called Blind Quantum Computation. It means the protocol needs continuous quantum and classical communication between the parties, throughout the execution. It comes with the properties of [[Secure Client- Server Delegated Quantum Computation#Properties|correctness]], [[Secure Client- Server Delegated Quantum Computation#Properties|blindness]] and [[Secure Client- Server Delegated Quantum Computation#Properties|universality]].</br></br>
'''Tags:''' [[Category: Two Party Protocols]] [[:Category: Two Party Protocols|Two Party]], [[Category: Universal Task]][[:Category: Universal Task|Universal Task]], [[Category: Quantum Functionality]] [[:Category: Quantum Functionality|Quantum Functionality]], Quantum Online communication, Classical Online communication, [[Supplementary Information#Measurement Based Quantum Computation|Measurement Based Quantum Computation (MBQC)]],
[[Prepare and Send-Universal Blind Quantum Computation|Prepare and Send-UBQC]], [[Measurement-Only Verifiable Universal Blind Quantum Computation|Measurement Only Verifiable UBQC]], [[Quantum Key Distribution|QKD]], [[Quantum Teleportation]].

==Assumptions==
* This protocol is secure against honest but curious adversary setting
*Client should have the classical means to compute the measurement pattern
*Client should have measurement devices.
*Protocol 1a assumes that quantum channel is not too lossy.
*No unwanted leakage from Client is assumed, i.e. Server cannot bug Client’s laboratory, a fundamental assumption in QKD.

==Outline==
The following Universal Blind Quantum Computation (UBQC) protocol uses the unique feature of [[Supplementary Information#Measurement Based Quantum Computation|Measurement Based Quantum Computation (MBQC)]] that separates the classical and quantum parts of a computation. Based on its counterpart Prepare and Send UBQC, this protocol requires Client to possess only a measurement device in order to perform blind quantum computation, hence the name 'Measurement Only UBQC'. The motivation behind this protocol lies in the fact that for several experimental setups like optical systems, measurement of a state is much easier than the generation of a state. Presented below are two versions of the protocol. The first protocol needs only quantum communication throughout the protocol while the second needs both quantum and classical throughout the communication. These protocols are designed for classical input and output. It can be extended to quantum input/output by modifying the measurement angles of the Client according to Prepare and Send UBQC in order to hide her quantum output from the Server. Like all the other delegated quantum computing protocols, this protocol is also divided into two stages, Preparation and Computation.
===Protocol 1a: Device Independent===
*''Server’s preparation'': Server prepares the resource graph state required for MBQC by the Client.
*'' Interaction and Client’s Computation'': Server sends single qubits of the prepared resource state to the Client who measures it in the basis required to carry out the quantum computation according to the measurement pattern in her mind. She records the outcomes and at the end of the computation stage, gets the result of her computation. This protocol is not tolerant to channel losses.

===Protocol 1b: Tolerant to high channel losses===
*''Server’s preparation'': This step remains the same as protocol 1a
*'' Interaction and Client’s Computation'': Server prepares a Bell pair and sends one half of the Bell Pair to the Client. The Client informs the Server if she receives it or else if she doesn’t, Client asks Server to send it again. The client measures her share of entangled pair in a certain measurement basis depending on her MBQC pattern. The Server then entangles his share of Bell pair and qubit of the resource state using CZ gate which transfers the gate/ measurement operated by Client to the resource qubit. Then he measures the resource qubit in X basis and communicates his classical measurement outcome to the Client. Client records it and uses it to compute her final outcome.

==Requirements==
*'''Network Stage:''' [[:Category:Quantum Memory Network Stage|Quantum Memory]] [[Category:Quantum Memory Network Stage]]
*'''Required Network Parameters:'''
**'''<math>\epsilon_j</math>''', which measures the error due to noisy operations.
**Number of communication rounds
**Circuit depth
**Number of physical qubits used
*Client should have measurement devices
*Quantum offline channel
*Classical online channel
*Server should be able to generate and store large network of entangled quantum states.

==Knowledge Graph==

{{graph}}

==Properties==
*Universality - Any model of quantum computation based on MBQC can be changed made blind using these protocols, thus, the universality of the protocol is implied by the universality of the resource state used.
*Correctness - Correctness for both protocols is implied from MBQC implementing the quantum computation successfully.
*Blindness - Blindness for protocol 1a is implied by no-signalling theorem as Client does not send any information to Server by measuring her states.
*Security of protocol 1a is device independent i.e. Client does not need to trust her measurement device in order to guarantee privacy.
*Protocol 1a can cope with Client’s measurement device inefficiency.
*Protocol 1b can cope with high channel losses but is no longer a no-signalling protocol. In order to make it no-signalling Client needs to discard measurement device after one use or use a random number generator to indicate if the particle was received or not.
*Both protocols follow the following definition of blindness: A protocol is blind if,
**The conditional probability distribution of Alice’s computational angles, given all the classical information Bob can obtain during the protocol, and given the measurement results of any POVMs which Bob may perform on his system at any stage of the protocol, is equal to the a priori probability distribution of Alice’s computational angles, and
**The conditional probability distribution of the final output of Alice’s algorithm, given all the classical information Bob can obtain during the protocol, and given the measurement results of any POVMs which Bob may perform on his system at any stage of the protocol, is equal to the a priori probability distribution of the final output of Alice’s algorithm.

==Notations==
*(m,n,o) dimensions of cluster state. It could be 2D or 3D.
* <math>G_{\text{mxnxo}}</math>: Graph state/Resource state created by the Server, as required by Client
* <math>|\psi\rangle_{i,j,k}\rangle</math>: A qubit of the resource state at position (i,j,k)
* <math>\Phi_{1,2}</math>: [[Glossary#Bell States|Bell pair]]
* <math>|\phi_2\rangle</math>: Client's half of the Bell pair
* <math>|\phi_1\rangle</math>: Server's half of the Bell pair
* <math>\theta</math>: Measurement angle as determined by Client's MBQC pattern. <math>\theta \epsilon\{0,\pi /2\}</math> in case of Clifford gates while <math>\theta \epsilon\{\pi /4\}</math> in case of non-Clifford gates.

==Protocol Description==
*Unless given specific mention in [.], following steps apply to both protocols
*'''Input:''' Server: Dimensions of Resource State (m,n,o)
*'''Output:''' Client: Final Outcome
#Server’s preparation
##Server creates a resource state <math>G_{\text{mxnxo}}</math>
#Interaction and Computation
##For i= 1,2,...m, j= 1,2,...n, k= 1,2,...o
##[Protocol 1a]
###Server sends <math>|\psi\rangle_{i,j,k}\rangle</math> to Client
###Client measures <math>|\psi\rangle_{i,j,k}\rangle</math> in the required measurement basis according to her measurement pattern
##[Protocol 1b]
###Server creates <math>\Phi_{1,2}=\frac{1}{\sqrt{2}}(|00\rangle+|11\rangle)</math>
###Server sends to Client (<math>|\phi_2\rangle</math>) and waits for Client's response
###Client checks if she received and tells the Server as Client.Response()
###'''If Client.Response()=No''', Server repeats the previous two steps
###'''Else''' Client measures (<math>|\phi_2\rangle</math>) in measurement basis {<math>|0\rangle \pm e^{i\theta}|1\rangle</math>
###'''Server's Computation: [[Glossary#Gate Teleportation|Gate Teleportation]]'''
####He entangles <math>|\phi_2\rangle</math> with <math>|\psi\rangle_{i,j,k}</math> by performing [[Glossary#Unitary Operations|C-Z]]
####He measures <math>|\psi\rangle_{i,j,k}</math> in X basis ({<math>|+\rangle,|-\rangle</math>})
####Server's applies correction on the classical outcome using Gate Teleporation
###Server communicates the corrected outcome
####Client records Server’s outcome and uses it when computing the final result or measurement angles for further qubits

*Interaction and Computation steps are repeated until all the qubits of resource state are measured.

==Further Information==

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