How does quantum function parallelism work?

Quantum parallelism is usually introduced from CNOT schema, saying that there it results, calling $$|c\rangle$$ the control and $$|t\rangle$$ the target $$|0\rangle |t\rangle \implies |0\rangle |t\rangle$$

$$|1\rangle |t\rangle \implies |1\rangle X|t\rangle$$ Generalizing that for a generic controlled-U gate, it gives $$|1\rangle |t\rangle \implies |1\rangle U|t\rangle$$ To note that the separation of the output is possible only if the control $$|c\rangle$$ is a pure state (i.e. $$|0\rangle$$ or $$|1\rangle$$).

With a further step it is said that, if $$|t\rangle = |0\rangle$$, the controlled-$$U$$ behaves as following $$|c\rangle |0\rangle \implies |c\rangle |f(c)\rangle$$ with $$f(x)$$ a proper function, non necessarily equal to $$U$$. More generally $$|c\rangle |t\rangle \implies |c\rangle |t XOR f(c)\rangle$$ Now my question: from where above two expressions are derived? And how can we build $$f(x)$$ from U? Making some examples with $$C_X$$, $$C_Z$$, $$C_Y$$ the unitaries needed for implementing the $$f(x)$$ are always different, and I couldn't find any clear logic for it.

Any clarification, or a working examples, would be great!

Generically, given any controlled-$$U$$, you cannot go backwards and work out the function $$f(x)$$, because it may not exist. For example, controlled-Hadamard takes a basis state and returns a superposition of basis states rather than a single basis state output. So there's no single $$f(x)$$ value to identify.

If it happens to be the case that for all inputs of the form $$|x\rangle|0\rangle$$ you gate an output of the form $$|x\rangle|f(x)\rangle$$, then you could literally just write down a table to the values $$x$$ and the corresponding $$f(x)$$. That truth table would define the function. Of course, that does not mean that $$U$$ acting on $$|x\rangle|y\rangle$$ necessarily produces $$|x\rangle|y\oplus f(x)\rangle$$.

For example, for controlled-not, one has

+---+------+
| x | f(x) |
+---+------+
| 0 |    0 |
| 1 |    1 |
+---+------+

i.e. f(x) is the identity function.

What you can do is work in the other direction. If you're given $$f(x)$$, you can figure out the circuit that gives you a unitary $$U$$ that acts as $$|x\rangle|y\rangle\mapsto |x\rangle|y\oplus f(x)\rangle.$$ This is not a quantum problem, but a problem of reversible classical computation (how do you convert a function evaluation into a reversible function, and find the circuit).

For instance, imagine I have a two-bit input $$x$$, and I want to evaluate $$f(x)$$ as the AND function. You need the truth table

+----+---+------------+
| x  | y | y XOR f(x) |
+----+---+------------+
| 00 | 0 |          0 |
| 01 | 0 |          0 |
| 10 | 0 |          0 |
| 11 | 0 |          1 |
| 00 | 1 |          1 |
| 01 | 1 |          1 |
| 10 | 1 |          1 |
| 11 | 1 |          0 |
+----+---+------------+

Hopefully, you can convince yourself that this is the same as the Toffoli gate (controlled-controlled-not).

• Thanks! It was clear to me that the step U --> f(x) was not the way, and I was actually trying to work out the way for going from f(x) to U. Bu tI was still looking (wrongly) to an output in a controlled-U like format, which instead you clarified it's not necessarily the case (and in general in fact it's not). It was misleading for me the use in many documents of the controlled schema for explaining it. Much clear to me now. Jan 1 '19 at 13:50

For $$cX$$,$$cY$$ and $$cZ$$ first.

Let $$U_Y$$ be the 1 qubit unitary such that $$U_Y^\dagger X U_Y = Y$$ and similarly for $$Z$$. This can be done because they all diagonalize to the same thing $$Z$$, so you can find that $$U$$ as an exercise.

Suppose you did $$U_Y$$ on the target qubit, then a CNOT and then a $$U_Y^\dagger$$ on the second qubit.

If the initial state is of the form $$|0\rangle | t \rangle$$ then you get $$| 0 \rangle ( U_Y | t \rangle )$$ after the first step. The second step doesn't change anything and then the third step takes you to $$| 0 \rangle ( U_Y^\dagger U_Y | t \rangle )$$ which is the same as the starting state. So that agrees with what $$cY$$ should have done on this type of state.

If the initial state is of the form $$|1\rangle | t \rangle$$ then you get $$| 1 \rangle ( U_Y | t \rangle )$$ after the first step. The second step does change things this time. You get $$| 1 \rangle ( X U_Y | t \rangle )$$. The third step then takes you to $$| 1 \rangle ( U_Y^\dagger X U_Y | t \rangle )$$. But by definition of $$U_Y$$ this is $$| 1 \rangle ( Y | t \rangle )$$.So that agrees with what $$cY$$ should have done on this type of state.

The same applies mutatis munandis with $$Z$$ replacing $$Y$$ to make $$cZ$$.

Secondarily:

Say you have some complicated expression for $$U$$ but it is written as a product of $$U_1 \cdots U_n$$ but you know how to make controlled versions of each of the $$U_i$$. Then you can make $$cU$$ by $$cU_1 \cdots cU_n$$. Like $$U=XZY$$ turning into $$cX cZ cY$$.

General 2-qubit $$cU$$:

You can use theorem 5 of this paper to decompose other controlled unitaries $$cU$$ besides those where there exists a $$V$$ such that $$V^\dagger X V=U$$. In those cases you can do the first procedure, but if not, you must do something more.

For 2 qubits with $$f(c)$$:

Suppose $$f(0)=0$$, then either $$f(1)=1$$ in which case you are describing a controlled not or $$f(1)=0$$ in which case you are describing the identity. If $$f(0)=1$$, then either $$f(1)=1$$ in which case you are describing a $$X$$ on the target qubit no matter the control. Or $$f(1)=0$$ in which case you are doing a controlled NOT but after reversing the way the controls go so that $$0$$ means perform the operation and $$1$$ means do not. This would be implemented by conjugating by an $$X$$ on the control qubit.

You should more be thinking of this as building the unitary from the function not the other way around. There are functions $$\{0,1\}^c \to \{0,1\}^t$$ where $$c$$ is the number of control qubits and $$t$$ is the number of target qubits and XOR is replaced by bitwise XOR in your formula. These give unitary matrices as you describe on $$(\mathbb{C}^2)^{c+t}$$. But there are far more unitaries than functions. So you can't expect to go from unitary to function, only the other way around.

• Thanks a lot for the clarification. It's opened a new way for looking at the problem, and it looks very promising for solving my issue. :-) I'll go through it in coming days. Have a great 2019!! Dec 30 '18 at 15:45
• AHusain, for the first two points, i.e. basic 2x2 c-gates (cY/cZ) realization and more general 2x2 cases the picture is clear to me. What I 'm still missing is the part related to the implementation of f(c) (or f(x)). Here my approach is actually from function to operator, as also suggested by you, but what I can get is a global U operator to applied to |x> and to ancillas |0>, and not really a c-U like schema. Here in fact what I'm missing is how a c-U schema, where an input |0, 0> is always translated to |0, 0>, can be used for implementing a generic f(x) with an arbitrary f(0) != 0. Jan 1 '19 at 10:22
• What individual gates are you writing that global U with? If you know how to make controlled versions of all the ingredients, you can make the cU schema. See the part after "secondarily." Jan 1 '19 at 18:30
• Thanks for this further clarification. I'm not particularly interested in doing a decomposition in basic gates, but more focused in understanding the principle and if there are limits for its applicability. I'm working at higher level algorithms but I still want to have a sound understanding of the foundations.... Jan 2 '19 at 11:28