How does this parallel computation scheme fail?

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

• this would be easier to understand written as a quantum circuit. What is the goal of the algorithm? What do you mean by "fail"?
– glS
Commented Jun 10, 2018 at 23:32
• I'm not too at-home with quantum circuit notation. Feel free to edit. I've edited to adress the rest. Commented Jun 11, 2018 at 0:15
• Can we change "Let x be in a uniform superposition of 0 and 1" to "Let $|x\rangle=\frac{1}{2}(|0\rangle+|1\rangle)$" to make things clearer? Then what are $|m\rangle$, $|a\rangle$, and $|b\rangle$ ? Commented Jun 11, 2018 at 0:46
• What specifically do you mean by "use amplitude amplification to restore uniformity"? You really should write this down as a circuit so it's unambiguous. Commented Jun 11, 2018 at 2:22

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

• I see where what you wrote differs from what I meant, but I can adopt that notation easily enough. All the sqrt factors seem boilerplatey, though. Commented Jun 11, 2018 at 7:02
• You have to have the square root factors to make the state normalised, and to let you calculate the probabilities of different measurement outcomes. Commented Jun 11, 2018 at 7:08
• d is whatever factor normalizes the state. I suppose I can put in an explicit formula. We don't need to evaluate f again, we copy the value from the unnamed register. I'll try to make that clearer. Commented Jun 11, 2018 at 9:00
• @Gurkenglas but you can't copy a quantum state in general. You have to show that every possible state you create is orthogonal if you want to be able to do this. Commented Jun 11, 2018 at 9:01
• But can't you always go from |x> to |x>|0> to |x>|xor(0,x)> to |x>|x>? Commented Jun 11, 2018 at 12:43

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