How does this parallel computation scheme fail?

Question

I've accidentally written a procedure which appears to compute both outputs of a long-running function $f: \{0,1\} \to \{1...n\}$ using one run of $f$ plus $\mathcal{O}(n)$ time. I thought this couldn't be done. Where's the bug in my "perpetuum mobile"? If I'm wrong, what's the name of this technique?

• Initialize with $\sum_ic_i|i\rangle_x$, with $c_0$ initially, say, $\sqrt½$, and the invariant $\sum_ic_i^2 = 1$.

• Compute $f(x)$, producing: $\sum_ic_i|i\rangle_x|f_i\rangle$ (1). We never evaluate $f$ again, and our goal is to extract these $f_i$.

• Produce: $$ \sqrt½\sum_ic_i|i\rangle_x|f_i\rangle(|i^{|a|}\rangle_a|f_i\rangle_b+2^{-|a+b|/2}\sum_{rs}|r\rangle_a|s\rangle_b) $$

• Measure and discard the $a$ and $b$ registers, getting (1) with $c_0^2 \in \{1/(2+2^{|a|+|b|}), ½, 1-1/(2+2^{|a|+|b|})\}$, and in all probability we know which.

• Use amplitude amplification, where the good and bad subspaces are distinguished using the $x$ qubit, to get $c_0^2$ between ⅛ and ⅞.

• Repeat the last 3 *s a bunch of times.

• In all probability, we've measured $f_0$ and $f_1$.

Answer 1

There's quite a lot that doesn't make sense in your described protocol, at least to me! It would be a lot clearer in terms of bras and kets. Let me try to translate, and you can comment to try and get us one the same page...

• Let $|x\rangle=(|0\rangle+|1\rangle)/\sqrt{2}$

• Compute $f(x)$, so you have $(|0\rangle|f(0)\rangle+|1\rangle|f(1)\rangle)/\sqrt{2}$

• Let $|m\rangle=(|0\rangle+|1\rangle)/\sqrt{2}$, so that we have an overall state $$ (|0\rangle_m|000\ldots 0\rangle_a|f(0)\rangle_b+|1\rangle_m|111\ldots 1\rangle_a|f(1)\rangle_b)/\sqrt{2} $$

• Measure the $a$ and $b$ registers.

What I don't understand: you've defined $|x\rangle$ but never used it. You've initialised the registers $a$ and $b$, but overwritten them immediately (so why did you initialise them?). What amplitude is it that you think you want to amplify?

With 50:50 probability, you either get $|0\rangle_m|000\ldots 0\rangle_a|f(0)\rangle_b$ or $|1\rangle_m|111\ldots 1\rangle_a|f(1)\rangle_b$. So, to get both values, you repeat until you've got both values. That requires a few runs. At best it takes 2, but you'd be better off just evaluating $f(0)$ and $f(1)$ by using two runs.

---

Update after question revision:

There are still issues with the description of the protocol: what is $d$, and how do you produce such a state with $d\neq0$? Surely you're better off just leaving $d=0$?

However, i think we're now getting to the point of main misunderstanding, which is counting the circuit complexity. Every time you produce the state $$ |\Psi_f\rangle=\sqrt½\sum_ic_i|i\rangle_x|f(i)\rangle(|i^{|a|}\rangle_a|f(i)\rangle_b+d\sum_{rs}|r\rangle_a|s\rangle_b) $$ you have to evaluate the function $f(x)$. If that is the costly function to evaluate, you have to count the number of repetitions. You say "Repeat the last 3 *s a bunch of times.", so that costs you a bunch of function evaluations, while just evaluating $f(0)$ and $f(1)$ costs you exactly 2 function evaluations. Moreover, to get 2 answers out, you must repeat your procedure at least twice, so you can never even get lucky and beat the naive classical case sometimes.

Note that if you want to be able to copy the state $|\Psi_f\rangle$, then for all different functions $f(x)$, those states must be orthogonal. However, consider two different functions: $f(0)=f(1)=0$ and $g(0)=0,g(1)=1$. We have that $\langle\Psi_f|\Psi_g\rangle\neq 0$.

Answer 2

Ampltiude amplification seems to require both that it is easy to judge between good and bad (which is easy enough if one goes by the $x$ qubit), and that it is easy to get to one's starting point, which in this case requires evaluating $f$.