# Quantum Search/Count on an unknown superposition state

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).
• Can you clarify slightly: We have the state $\vert \psi\rangle$ in quantum memory already. Do we have a unitary to map $\vert \psi_0\rangle$ to $\vert \psi\rangle$? Or do we just have a classical list of all the tags and data (from which we could build the required unitary, but only at tremendous cost)? Commented Dec 8, 2020 at 17:39
• I am not sure I understand exactly what you are looking for, but the problem made me think of the qRAM, is that right? What are you trying to do exactly?
– Lena
Commented Dec 9, 2020 at 8:37
• @SamJaques yes, I meant that the unitary to create the |ψ⟩ is given, but the classical tag-data is not. So you can repeat the experiment if you want (provided it doesn't nullify the quantum advantage), but the search/count circuit cannot use the knowledge of the tag-data list in it to create an oracle/marking. Commented Dec 9, 2020 at 14:14
• @Lena well, it is similar to a qRAM (maybe this is a special case of a qROM query). However, there are 2 differences: (a) in qRAM/qROM, n qubit tag accesses a data over 2^n qubits. Here, the size of the data string is independent of the tag string. (b) we are not searching by the tag, but by the data (which doesn't have a full superposition). Commented Dec 9, 2020 at 18:28
• Assuming you also have a unitary $U_0$ that can map $\vert 0\rangle$ to $\vert \phi_0\rangle$, then you should be able to do a Grover search: Start with $\vert 0\rangle$, apply $U$, then apply $U$ and flip the phase of all desired data; then apply $U^{-1}$, then $U_0^{-1}$, flip the phase of the $\vert 0\rangle$ state, then repeat. Commented Dec 10, 2020 at 1:06