Question:
- Search a 'known' element in an 'unknown' quantum database
- Alternatively, show this is fundamentally impossible (somehow related to the Holevo bound or P < NP?)
Related yet different:
- Grover Search (and related improvements): single element marked in a 'full' superposition.
- Quantum Associative Memory (and related improvements): single element marked in a database, but the memory oracle marks all 'stored patterns' thus requires knowledge of the database (quantum phone directory).
- Quantum Counting (and related improvements): assumes either full superposition or knowledge of database.
Formulation:
- Database structure of $t$ (qu)bits of tag and $d$ (qu)bits of data
- An initial state with a equal superposition of tag qubits and zero in the data qubits: $|\psi_0\rangle = \sum_{x \in 2^t} (\dfrac{1}{\sqrt{2^t}} |tag_x\rangle \otimes |0\rangle^d)$
- Unitary $U$ that evolves $|\psi_0\rangle$ to $|\psi\rangle = \sum_{x \in 2^t} (\dfrac{1}{\sqrt{2^t}} |tag_x\rangle\otimes |data_x\rangle)$
- Thus, every binary encoded tag is unique and has an associated data, however, the data may not be unique
Problem:
- Given $t$, $d$ and the knowledge of which qubits encode the tag and the data
- Given access to $|\psi\rangle$ in $t+d$ qubits without explicit knowledge of the superposition state
- Search/sample associated tag/s of corresponding $|data_i\rangle$ with high probability
- Count the number of tags storing a specific $|data_i\rangle$
Example:
- $t = 2$ qubit tag and $d = 3$ qubit data
- $|\psi\rangle = \dfrac{1}{2} (|00.010\rangle + |01.110\rangle + |10.100\rangle + |11.110\rangle)$. The dot is notational denoting the $tag.data$ encoding.
- $|data_i\rangle = 110$
- Search aim: amplify the corresponding tags towards the state $\dfrac{1}{\sqrt{2}} (|01.110\rangle + |11.110\rangle)$. Note: I can mark and post-select on the data but that would succeed with very low probability if the number of marked states is low and gives no advantage if I want to sample the tags.
- Count aim: counting the number of tags $\rvert|tag_i\rangle\rvert= 2$
Motivation
- Imagine a dictionary given as a quantum superposition of word and meanings. I have knowledge of what words are there in the dictionary and can list them classically. I want to query the meaning of a specific word. It seems counterintuitive that I need classical knowledge of the 'meaning of every word in the dictionary' to construct the quantum circuit (oracle+diffusion).
