# Information retrieval from a database

Consider a database $\cal D$ containing $N$ entries $A_0, A_1, ... A_{N-1}$, which are some fixed and unknown strings of $k$ bits; you can access this database sending a coherent superposition of addresses $|j\rangle$ and retrieve a coherent superposition of answers: $${\cal D}:\sum_j \alpha_j \ |j\rangle \mapsto \sum_j \alpha_j \ |j\rangle \ |A_j\rangle.$$ You can then perform some POVM measurement in order to extract classical information from this state.

Question 1: Is it possible with a single query to $\cal D$ to obtain classical information which is a function of more than a single entry of the database? For example, is it possible to obtain the value of $A_i \oplus A_j$ with a single query?

Notice that the answer is encoded on a new quantum system provided by the database, so you cannot use ancilla qubits entangled with this answer. The Holevo bound then already precludes to obtain more than $k$ bits of classical information (the amount of information contained in each string), but does not by itself prevent the user from knowing the bitwise XOR of two or more elements.

I believe that the answer should be no'', essentially because of linearity of quantum mechanics, which should prevent the computation of a non-linear function of the states. However, I am looking for a convincing proof of this fact.

Question 2: Consider this variant ${\cal D}'$ of the database, in which you also provide the quantum system on which send back the answer: $${\cal D}:\sum_{j,X} \alpha_{j,X} \ |j\rangle \ |X\rangle \mapsto \sum_{j,X} \alpha_{j,X} \ |j\rangle \ |X \oplus A_j\rangle.$$ in which $X$ represent any possible bit string. In this case, is it possible to obtain classical information that depends non-trivially on more than one database entry?

Question 3: Given the possibility to access $\cal D$ (or ${\cal D}'$) many times - say $m$ times - is there any strategy that allows to obtain classical information that depends on more than $m$ different entries?

I suspect that the answer to these question is also negative, but I wouldn't be surprised of the contrary.

• i guess for the 1st question the mapping would be sth like: ${\cal D}:\sum_{ij} \alpha_{ij} \ |ij\rangle \mapsto \sum_{ij} \alpha_{ij} \ |ij\rangle \ |A_{ij}\rangle.$ where $A_{ij}$ would correspond to $A_i \oplus A_j$ – Nikos M. Oct 2 '14 at 13:27