How does quantum function parallelism work?

Question

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!

Answer 1

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.

Answer 2

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