20
edits
Quantum Fingerprinting: Difference between revisions
Jump to navigation
Jump to search
m
Reverted edits by Shraddha (talk) to last revision by Bob
No edit summary |
Tag: Rollback |
||
| Line 1: | Line 1: | ||
Quantum fingerprinting allows two parties (two quantum clients) to collaboratively compute the value of a function using both of their inputs while maintaining the privacy of their own input. The protocol does not permit the two parties to interact directly with each other, hence they send their respective inputs to a trusted third party (quantum server) who computes the correct value of the function corresponding to both inputs while minimizing the amount of information sent by the two parties. | |||
</br></br> | |||
Minimization of information is done by fingerprinting, which is a technique that associates a string to an exponentially smaller string (fingerprints) such that any two strings can by distinguished solely based on their fingerprints. | |||
</br></br> | </br></br> | ||
'''Tags:''' | '''Tags:''' Fingerprinting | ||
==Assumptions== | ==Assumptions== | ||
==Outline== | ==Outline== | ||
The two quantum clients want to compute a function using the input of both parties. In this protocol, we focus on a specific function, which is the equality function. This function provides boolean output 1 if the input of both the parties is the same, otherwise, the output is 0. | |||
</br> | |||
Preparation stage involves two parties (two quantum clients) preparing the fingerprints of their individual inputs and sending their quantum states to the server (trusted third party). The two clients do not possess any shared quantum key. | |||
</br> | </br> | ||
* '''Client's preparation''': | |||
Next stage involves the server performing several operations on the fingerprints to check their equality. These operations are repeated several times on the same fingerprints to reduce the error probability. | |||
</br> | |||
* '''Client's preparation''': The client prepares the fingerprint of initial input sized <math>n</math>-bits. This fingerprint has a length of <math>\log_{}n</math> bits. The client now sends this fingerprint to the server through a quantum channel. Both the clients do this process simultaneously. | |||
* '''Server's preparation''': The server receives the two fingerprints from both the clients and prepares the operations to distinguish them. The server independently repeats the computation process with the fingerprints several times to reduce the error probability in detecting whether the equality of the two states. | * '''Server's preparation''': The server receives the two fingerprints from both the clients and prepares the operations to distinguish them. The server independently repeats the computation process with the fingerprints several times to reduce the error probability in detecting whether the equality of the two states. | ||
| Line 22: | Line 24: | ||
If the initial input of the two parties are equal, this would be inferred from the corresponding fingerprints with no error probability and the outcome of the protocol would be correct. However, if the two fingerprints are of different inputs, there exists a non-zero probability that the outcome of the protocol is incorrect. Therefore, there exists a one sided error in the measurement. This one sided error is reduced by repeating the server operations several times with the same fingerprints. | If the initial input of the two parties are equal, this would be inferred from the corresponding fingerprints with no error probability and the outcome of the protocol would be correct. However, if the two fingerprints are of different inputs, there exists a non-zero probability that the outcome of the protocol is incorrect. Therefore, there exists a one sided error in the measurement. This one sided error is reduced by repeating the server operations several times with the same fingerprints. | ||
== | ==Requirements== | ||
* Authenticated Quantum channel capable of sending a pair of qubits. | * Authenticated Quantum channel capable of sending a pair of qubits. | ||
* Quantum memory for | * Quantum memory for server to store the fingerprints. | ||
* Measurement devices for the server. | * Measurement devices for the server. | ||
==Notation== | ==Notation== | ||
* <math>|h_x\rangle</math>, Quantum fingerprint for <math>n</math>-bit input <math>x</math>. | * <math>|h_x\rangle</math>, Quantum fingerprint for <math>n</math>-bit input <math>x</math>. | ||
* <math>E(x)</math>, Fingerprint function associated with input <math>{x\in \{0, 1\}^n}</math> which maps <math>n</math>-bit input to <math>m</math>-bit fingerprint. | * <math>E(x)</math>, Fingerprint function associated with input <math>{x\in \{0, 1\}^n}</math> which maps <math>n</math>-bit input to <math>m</math>-bit fingerprint. | ||
* <math>\delta</math>, Fixed constant, such that <math>\delta<0</math>. | * <math>\delta</math>, Fixed constant, such that <math>\delta<0</math>. | ||
| Line 36: | Line 36: | ||
==Properties== | ==Properties== | ||
* The computational complexity of this protocol is <math>\mathcal{O}(\log{}n)</math>. | * The computational complexity of this protocol is <math>\mathcal{O}(\log{}n)</math>. | ||
* The two quantum clients have no shared key in this protocol. | |||
* Given an <math>n</math>-bit input, the protocol requires a quantum fingerprint of minimum <math>\log{}n</math> bits which contains quantum information. | * Given an <math>n</math>-bit input, the protocol requires a quantum fingerprint of minimum <math>\log{}n</math> bits which contains quantum information. | ||
* The quantum fingerprint is defined as the state <math>|h_x\rangle</math>, where <math>{E(x)}</math> is the fingerprint of the input <math>x</math>. <math>{E_i(x)}</math> is the <math>{i^{th}}</math> bit of <math>{E(x)}</math>. </br> | * The quantum fingerprint is defined as the state <math>|h_x\rangle</math>, where <math>{E(x)}</math> is the fingerprint of the input <math>x</math>. <math>{E_i(x)}</math> is the <math>{i^{th}}</math> bit of <math>{E(x)}</math>. </br> | ||
<math>|h_x\rangle = \frac{1}{\sqrt{m}}\sum_{n=1}^{m} |i\rangle|E_i(x)\rangle</math> | |||
* The hamming distance i.e. the number of positions between two strings of same length, at which the corresponding symbols are different, of <math>{E(x)}</math> and <math>{E(y)}</math> is at least <math>{(1+\delta)m}</math>. | * The hamming distance i.e. the number of positions between two strings of same length, at which the corresponding symbols are different, of <math>{E(x)}</math> and <math>{E(y)}</math> is at least <math>{(1+\delta)m}</math>. | ||
* Any two fingerprints, <math>|h_x\rangle</math> and <math>|h_y\rangle</math> have an inner product of at most <math>{\delta}</math>. | * Any two fingerprints, <math>|h_x\rangle</math> and <math>|h_y\rangle</math> have an inner product of at most <math>{\delta}</math>. | ||
| Line 54: | Line 56: | ||
'''Stage 2''': Server's preparation | '''Stage 2''': Server's preparation | ||
* Server prepares an ancilla qubit <math>|0\rangle</math> for final measurement purpose, and thus starts with the state <math>|0\rangle|h_x\rangle|h_y\rangle</math>. | * Server prepares an ancilla qubit <math>|0\rangle</math> for final measurement purpose, and thus starts with the state <math>|0\rangle|h_x\rangle|h_y\rangle</math>. | ||
* Server creates an entangled state by applying the gate <math>G = {(H\otimes I)(c-SWAP)(H\otimes I)}</math> | * Server creates an entangled state by applying the gate <math>G</math>. | ||
<math>G = {(H\otimes I)(c-SWAP)(H\otimes I)}</math> | |||
* The server measures the first qubit and transmits the output to both the parties. | * The server measures the first qubit and transmits the output to both the parties. | ||