• 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.


  • 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


  • 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$


  • $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$


  • 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).
  • $\begingroup$ 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)? $\endgroup$
    – Sam Jaques
    Dec 8, 2020 at 17:39
  • $\begingroup$ 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? $\endgroup$
    – Lena
    Dec 9, 2020 at 8:37
  • $\begingroup$ @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. $\endgroup$
    – Aritra
    Dec 9, 2020 at 14:14
  • $\begingroup$ @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). $\endgroup$
    – Aritra
    Dec 9, 2020 at 18:28
  • $\begingroup$ 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. $\endgroup$
    – Sam Jaques
    Dec 10, 2020 at 1:06


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.