3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – narip
    Commented Dec 19, 2021 at 4:29

1 Answer 1

Reset to default
3
$\begingroup$

It's just Grover's algorithm. You don't need to mark the state manually, at least in Grover's algorithm. If you mark them manually, you might lose the essence of the oracle.

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}$.

$\endgroup$
4
  • $\begingroup$ I think there is a missing piece - according to the question, you are blindly given a single copy of this unknown quantum state. Without knowing its details (which is exactly what you are trying to find out), you don't seem to have access to the information needed to construct the oracle as you describe. $\endgroup$
    – MPeti
    Commented Dec 19, 2021 at 13:01
  • $\begingroup$ @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. $\endgroup$
    – narip
    Commented Dec 19, 2021 at 13:39
  • $\begingroup$ Right, that makes sense! So you're just applying a phase gate to the ancilla qubit in this case, right? I think I agree now. $\endgroup$
    – MPeti
    Commented Dec 19, 2021 at 15:50
  • $\begingroup$ 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$. $\endgroup$
    – user17549713
    Commented Dec 19, 2021 at 20:25

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .