# Is it possible to recover a marked bitstring from a superposition?

Is it possible to recover a marked bitstring from a superposition?

For example, consider the state $$\lvert \psi \rangle = \frac{1}{2}\left(\lvert 00 \rangle \lvert 0 \rangle + \lvert 01 \rangle \lvert 0 \rangle + \lvert 10 \rangle \lvert \mathbf{1} \rangle + \lvert 11 \rangle \lvert 0 \rangle\right)$$ which has a uniform superposition in the first register and one marked $$\lvert 1 \rangle$$ in the ancilla register.

If I were blindly given $$\lvert \psi \rangle$$, is there a quantum circuit that would recover the marked bitstring $$\lvert 10 \rangle$$?

It almost feels like a Grover Search / Amplitude Amplification use case (with the aim of boosting the probability of $$\lvert 1 \rangle$$ in the ancilla). But that doesn't quite seem to work or at least I can't see what oracle to use, given just one copy of the quantum state.

Thanks.

• Why can't just consider normal Grover's search with $|\psi\rangle=\frac{1}{2}(|00\rangle+|01\rangle+|10\rangle+|11\rangle)$? No need to mark some state obviously. Commented Dec 19, 2021 at 4:29

If you mark the target state with an ancilla, the oracle can be easily build by using a control gate. In your case, the oracle should be $$\left( e^{i\theta}|00\rangle \langle 00|+e^{i\theta}|01\rangle \langle 01|+e^{i\theta}|10\rangle \langle 10|+e^{i\theta}|11\rangle \langle 11| \right) \otimes |1\rangle \langle 1|+I\otimes |0\rangle \langle 0|\\=e^{i\theta}I\otimes |1\rangle \langle 1|+I\otimes |0\rangle \langle 0|,$$ i.e. we mark the target state with phase $$e^{i\theta}$$.
• @MPeti I don't think oracle like $e^{i\theta}I\otimes |1\rangle \langle 1|+I\otimes |0\rangle \langle 0|$ will need details of the state. Commented Dec 19, 2021 at 13:39
• Thanks for the answer @narip. Unfortunately, I don't think this would work, because Grover search only works when we consider starting from a uniform superposition over all bitstrings. In this case, applying Grover's diffusion operator would cause non-zero amplitudes for states such as $\lvert 00 \rangle \lvert 1 \rangle$. Commented Dec 19, 2021 at 20:25