# 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 Jun 10 '18 at 23:32
• I'm not too at-home with quantum circuit notation. Feel free to edit. I've edited to adress the rest. – Gurkenglas Jun 11 '18 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$ ? – user1271772 Jun 11 '18 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. – Craig Gidney Jun 11 '18 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. – Gurkenglas Jun 11 '18 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. – DaftWullie Jun 11 '18 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. – Gurkenglas Jun 11 '18 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. – DaftWullie Jun 11 '18 at 9:01
• But can't you always go from |x> to |x>|0> to |x>|xor(0,x)> to |x>|x>? – Gurkenglas Jun 11 '18 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$.