3
$\begingroup$

On contrary to amplitude amplification, can I do some reflection such that my marked states' probability will vanish (ideally become zero but if there are small residuals also acceptable)? In order to preserve the normalization condition, all the rest states will get amplified uniformly but the phases of them should remain the same (their coefficients are complex. Is this possible?

$\endgroup$
3
$\begingroup$

Any state $|\Psi\rangle$ can be decomposed using a two-dimensional subspace comprising marked and unmarked states, $$ |\Psi\rangle=\alpha|\Psi_m\rangle+\beta|\Psi_u\rangle. $$ Part of the assumption is that you have a marking oracle that acts as $$ |\Psi\rangle|0\rangle\rightarrow\alpha|\Psi_m\rangle|1\rangle+\beta|\Psi_u\rangle|1\rangle. $$ This is exactly the same thing that you use during amplitude amplification (usually, your ancilla bit would be in the state $|-\rangle=(|0\rangle-|1\rangle)/\sqrt{2}$ in order to get the phase kick-back onto the main system).

In the typical setting, the amplitude for marked states ($\alpha$) is small. If this is the case, if you simply measure the ancilla qubit, you'll find it to be in the state $|1\rangle$ with probability $|\beta|^2$, which is close to 1. You're left with the state $|\Psi_u\rangle$. Even if it doesn't work, you just have to repeat a small number of times.

If you're in the opposite regime where $\alpha$ is large, then notice this is just your normal amplitude amplification, you've merely switched the roles of marked and unmarked states - suppressing $\alpha$ is the same as amplifying $\beta$. To make this work, all you need to do is every time you apply the marking procedure, flip the ancilla qubit as well, converting marked into unmarked and vice versa.

how should I use just one ancilla to record multiple marked states?

Hopefully this is already clearer. However, the point is there is a boolean value for "should this state be marked?": 0 for no, 1 for yes. Multiple states can answer 1. For example, you could define the marking function to be something like "is the number even?" which is simple enough to mark all the even numbers simultaneously (actually, you just take the least significant bit of the number and flip it).

$\endgroup$
  • $\begingroup$ Firstly thanks for answering my question (I'm a newbie here :) ). I need to clarify with you though: 1. by '0 (unmarked) or 1 (marked)' do you mean inverting the phase of those unwanted states like the oracle in Grover search? 2. The unwanted states do not necessarily have small amplitudes. $\endgroup$ – Zzy1130 Jun 12 at 12:10
  • $\begingroup$ Also how should I use just one ancilla to record multiple marked states? $\endgroup$ – Zzy1130 Jun 12 at 13:03
  • $\begingroup$ I figured it out. Thanks. $\endgroup$ – Zzy1130 Jun 13 at 10:07
0
$\begingroup$

You can simply apply amplitude amplification to the unmarked states. Whereas you originally reflect around the marked states, now you simply reflect around the unmarked states.

$\endgroup$
  • $\begingroup$ Is the reflection still around the mean? $\endgroup$ – Zzy1130 Jun 13 at 6:06
  • $\begingroup$ You alternate reflections around the mean and around the unmarked states. $\endgroup$ – smapers Jun 14 at 9:04
  • $\begingroup$ I tried. It doesn't work for states with complex coefficients. You can initialize some complex coefficients and have a try $\endgroup$ – Zzy1130 Jun 14 at 10:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.