Editing
Multi-Database Quantum Symmetric Private Information Retrieval without Shared Randomness
(section)
Jump to navigation
Jump to search
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
==Protocol Description== <!-- Mathematical step-wise protocol algorithm helpful to write a subroutine. --> '''Inputs:''' * User: index of the desired database element <math>i</math>. * Each of the <math>k</math> servers: database <math>x</math> (an <math>n</math> bit string). '''Output:''' * User: desired database element <math>x_i</math> (a single bit of <math>x</math>). '''Protocol:''' ''This protocol works on top of [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.79.549&rep=rep1&type=pdf Beimel et al classical PIR scheme], which involves the following steps:'' * '''Query:''' The user generates a random string <math>r</math> and <math>k</math> queries <math>q_1 (i,r),...,q_k (i,r)\in \{0,1\}^t</math>. The user sends each query to the corresponding server. * '''Answer:''' Each server answers the user: the <math>j^\text{th}</math> server answers with classical answer <math>a_j \in \{0,1\}^{a}</math>. * '''Retrieval:''' The user outputs the desired database element <math>x_i = \sum_{j=1}^k a_j \cdot b_j</math> where <math>b_j=b_j(i,r) \in \{0,1\}^{a}</math>, and all operations are modulo 2. ''Kerenidis and de Wolf quantum SPIR scheme works as follows:'' * '''Query:''' ** The user generates a random string <math>r</math>, <math>k</math> queries <math>q_1 (i,r),...,q_k (i,r)\in \{0,1\}^t</math> and <math>k</math> random strings <math>r_1,...,r_k\in \{0,1\}^a</math>. ** The user prepares a <math>(k+1)</math>-register state: <math>\frac{1}{\sqrt{2}} |0\rangle|q_1,r_1 \rangle ...|q_k,r_k \rangle+\frac{1}{\sqrt{2}} |1\rangle|q_1,r'_1 \rangle ...|q_k,r'_k\rangle</math> where <math>r'_j := r_j+b_j</math> and <math>b_j=b_j (i,r)\in \{0,1\}^a</math> is the part known only to the user that, together with the answers of the server, allows the user to reconstruct the desired database element at the end of [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.79.549&rep=rep1&type=pdf Beimel et al PIR protocol]: <math>\sum_{j=1}^k a_j \cdot b_j = x_i</math>. ** The user keeps the first <math>1</math>-qubit register and sends the other <math>k</math> registers to the corresponding server. * '''Answer:''' ** Each server applies a unitary map to the received quantum register: <math>|q_j,r \rangle \rightarrow (-1)^{a_j \cdot r} |q_j,r\rangle</math> where <math>a_j=a_j (q_j,x)\in \{0,1 \}^a</math> is the classical answer of the <math>j^\text{th}</math> server to the user in [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.79.549&rep=rep1&type=pdf Beimel et al PIR protocol]. The transformed quantum register is then sent back to the user. * '''Retrieval:''' ** The complete state owned by the user is now of the form: <math>\frac{1}{\sqrt{2}} |0\rangle (-1)^{a_1 \cdot r_1} |q_1,r_1\rangle ... (-1)^{a_k \cdot r_k} |q_k,r_k\rangle + \frac{1}{\sqrt{2}} |1\rangle (-1)^{a_1 \cdot r'_1} |q_1,r'_1\rangle ... (-1)^{a_k \cdot r'_k} |q_k,r'_k\rangle</math> <math>= \frac{1}{\sqrt{2}} |0\rangle (-1)^{\sum_{j=1}^k a_j \cdot r_j} |q_1,r_1\rangle ... |q_k,r_k\rangle + \frac{1}{\sqrt{2}} |1\rangle (-1)^{\sum_{j=1}^k a_j \cdot r'_j} |q_1,r'_1\rangle ... |q_k,r'_k\rangle</math> <math>= \frac{1}{\sqrt{2}} |0\rangle (-1)^{\sum_{j=1}^k a_j \cdot r_j} |q_1,r_1\rangle ... |q_k,r_k\rangle + \frac{1}{\sqrt{2}} |1\rangle (-1)^{\sum_{j=1}^k a_j \cdot (r_j + b_j)} |q_1,r'_1\rangle ... |q_k,r'_k\rangle</math> <math>= (-1)^{\sum_{j=1}^k a_j \cdot r_j} \left( \frac{1}{\sqrt{2}} |0\rangle |q_1,r_1\rangle ... |q_k,r_k\rangle + \frac{1}{\sqrt{2}} |1\rangle (-1)^{\sum_{j=1}^k a_j \cdot b_j} |q_1,r'_1\rangle ... |q_k,r'_k\rangle \right)</math> Hence, up to a global phase <math>(-1)^{\sum_{j=1}^k a_j \cdot r_j} </math>, this state is: <math>\frac{1}{\sqrt{2}} |0\rangle |q_1,r_1\rangle ... |q_k,r_k\rangle + \frac{1}{\sqrt{2}} |1\rangle (-1)^{x_i} |q_1,r'_1\rangle ... |q_k,r'_k\rangle </math>. ** To retrieve the desired database element <math>x_i</math>, the user then maps the <math>k</math> quantum registers to the ground state – this way, entanglement is destroyed, and the first qubit is in state <math>\frac{1}{\sqrt{2}}(|0\rangle+(-1)^{x_i} |1\rangle)</math>. **Lastly, the user applies a Hadamard transform to the first qubit, which is now in state <math>|x_i\rangle</math>. Measuring in the computational basis <math>\{|0\rangle,|1\rangle\}</math> has classical outcome the desired bit <math>x_i</math>.
Summary:
Please note that all contributions to Quantum Protocol Zoo may be edited, altered, or removed by other contributors. If you do not want your writing to be edited mercilessly, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource (see
Quantum Protocol Zoo:Copyrights
for details).
Do not submit copyrighted work without permission!
To protect the wiki against automated edit spam, we kindly ask you to solve the following CAPTCHA:
Cancel
Editing help
(opens in new window)
Navigation menu
Personal tools
Not logged in
Talk
Contributions
Log in
Namespaces
Page
Discussion
English
Views
Read
Edit
View history
More
Search
Navigation
Main page
News
Protocol Library
Certification Library
Nodal Subroutines
Codes Repository
Knowledge Graphs
Submissions
Categories
Supplementary Information
Recent Changes
Contact us
Help
Tools
What links here
Related changes
Special pages
Page information