1
$\begingroup$

It is normal to extend fixed-point amplitude amplification to an oblivious version, i.e., $1 - (1-e^{i \beta})|t\rangle \langle t | \rightarrow 1 - (1-e^{i \beta}) 1 \otimes |0\rangle \langle 0|$, and one uses an additional ancilla to apply a phase to the target state $|t\rangle$.

However typically the other reflection, $1 - (1-e^{-i\alpha}) |0\rangle \langle 0|$ is about the all-zero initial state. But suppose you are given an unknown initial state, $|\psi_0 \rangle$. You know you can construct a unitary $U$ that does $$ U |\psi_0\rangle |0\rangle = \sqrt{a}|A_0\rangle |0\rangle + \sqrt{1-a}|A_1\rangle |1\rangle, $$ and so could amplify the probability of $|A_{0}\rangle |0\rangle$ to 1, but only if you could implement $1 - (1-e^{-i\alpha})|\psi_0\rangle\langle \psi_0 | \otimes |0\rangle \langle 0|$, and you don't know how $|\psi_{0}\rangle$ came about. Is it possible instead to construct a unitary $U'$ that will give you $$ U' |\psi_0\rangle |0\rangle = \sqrt{a}|A_0\rangle |0\rangle + \sqrt{1-a}|A_1\rangle |1\rangle, $$ while simultaneously only using $1 - (1-e^{-i\alpha})1\otimes |0\rangle \langle 0|$ for the initial state reflection during amplitude amplification? It is not clear to me how one would construct a $U'$ that moves between the two bases $|A_0\rangle |0\rangle$, $|A_1\rangle |1\rangle$, and $|\psi_0\rangle |0\rangle$, $|\psi_{1}\rangle |1\rangle$, for some $|\psi_1 \rangle |1\rangle$.

$\endgroup$

1 Answer 1

1
$\begingroup$

Yes, it is possible to combine fixed-point amplitude amplification with oblivious amplitude amplification, provided that $a$ in the definition of $U$ is independent of the input state $|\psi_0\rangle$, as discussed in this paper by Dalzell, Yoder, and Chuang (cf. Section VI.B in particular). Importantly, that means oblivious amplitude amplification does not work if $U$ is non-unitary. This paper by Guerreschi also discusses fixed-point oblivious amplitude amplification.

$\endgroup$
1
  • $\begingroup$ My question is whether one can reflect obliviously about the initial state. $\endgroup$
    – kηives
    Nov 18, 2022 at 19:24

Your Answer

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

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