How does a generic controlled-U operation work?

Question

It appears that controlled-$U$ type operation is the bedrock to many quantum algorithms, for instance, phase estimation and amplitude estimation. These algorithms systematically employs the controlled-$U$ type operation on the a state, say $|\psi\rangle$, stored in an oracle register while retaining one qubit in the computational register as the control bit. Consider a general case: The control bit is brought into a superposition $\frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$ and the $|\psi\rangle$ is not an eigenstate of operator $U$, meaning $U|\psi\rangle = |\phi\rangle$. Now, we execute the controlled-$U$ operation to have

$\frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)\otimes|\psi\rangle \xrightarrow{c-U}\frac{1}{\sqrt{2}}(|0\rangle\otimes|\psi\rangle + |1\rangle \otimes|\phi\rangle)$

where this basically implies that the control bit is entangled with the state in the oracle register. (Phase estimation is a special case where operator $U$ 'squeezes' out a phase factor $U|\psi\rangle = e^{\theta}|\psi\rangle$ and once this phase factor is considered back-kicked to state $|1\rangle$, the states in computational and oracle registers are separable.)

Here is what puzzles me. First, when we retain another bit in computational register as the control bit and apply $U$ on the oracle register, to what state are we actually applying this operator $U$? It appears in the most general case the resulting state of the control bit and the oracle register needs to be viewed as one state. Second, how does the matrix that represents this controlled-$U$ operator look like? To be more concrete, take the following 3-bit computational register as example,

$\frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)\otimes\frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)\otimes\frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$

retaining the second bit as control and apply $U$ (on the oracle register), how does that matrix look like?

Answer 1

We know that operators are applied on qubits. But sometimes it does not make sense to ask the state on which we apply an operator, say $U$. For instance, take the two-qubit entangled state $|\psi\rangle = \frac{1}{\sqrt{2}}(|00\rangle+|11\rangle)$. Now, say, I would like to apply a $H$ gate on the first qubit. If I ask the state on which I will be applying the $H$ gate, it does not make sense because the state of the first qubit alone is not defined for $|\psi\rangle$. This is true whenever we try to apply any $m$-qubit gate $U$ on $m$ qubits that are part of some $n$-qubit entanglement state where $m< n$. So you were perfectly right in saying that in most cases we have to view the state of the control bit and that of the oracle register together.

For any $n$-qubit unitary $U$, the matrix of its controlled version $c$-$U$ can be given as $\begin{bmatrix} I & 0 \\ 0 & U \\ \end{bmatrix}$ where $I$ is the identity matrix of size $2^n$ and $0$ is the zero matrix of size $2^n$. This is quite simple. But when you try to obtain the matrix corresponding to the operation where you have 3 registers and the $c$-$U$ is applied from the first register to the third, it follows a similar pattern. For instance, assume that we have three registers of the form $|+\rangle |+\rangle |\phi\rangle$, where $|\phi\rangle$ is some $n$-qubit state. Then on the assumption that the $U$ matrix is of the form $U = [u_{i,j}]_{2^n\times 2^n}$, the matrix representation of the above operation looks like the following: $$M_u = \begin{bmatrix} I_{2^n} & 0 & 0 & 0\\ 0 & I_{2^n} & 0 & 0 \\ 0 & 0 & U & 0\\ 0 & 0 & 0 & U\\ \end{bmatrix}_{(2^{n+2})\times (2^{n+2})}$$ where $I_{2^n}$ is the identity matrix of size $2^n$. Notice that this is a 3-qubit unitary and it is not possible to write $M_u$ as a tensor product of two matrices. This can be viewed as the operator $$|0\rangle\langle 0| \otimes I_2 \otimes I_{2^n} + |1\rangle\langle 1| \otimes I_2 \otimes U.$$ An alternative way to see this using the fact that this operation is equivalent to first swapping the first and the second qubits, then performing a $c$-$U$ with the second qubit as the control and the third register as the target and then again swapping the first and the second qubits. Mathematically, this can be given as $$M_u = (SWAP_{\{1,2\}}\otimes I_{2^n})\cdot (I_2\otimes cU_{\{2,3\}}) \cdot (SWAP_{\{1,2\}}\otimes I_{2^n})$$ where $SWAP_{\{1,2\}}$ is the matrix corresponding to the $SWAP$ gate. This can be generalized even to cases where you have $p$ many gates in between the control and the target qubits very easily.

Answer 2

It appears in the most general case the resulting state of the control bit and the oracle register needs to be viewed as one state.

Yes, absolutely. This is rather the point of quantum computation - for any interesting computation, there will be entangling steps that mean you cannot view the state as "state of qubit 1, and state of qubit 2" but they are a single, unified state.

how does the matrix that represents this controlled-U operator look like? ... the second bit as control and apply U (on the oracle register), how does that matrix look like?

Here, you're doing nothing on the first qubit, so that means apply identity $I$ on that qubit. Hence the operator looks like $$ I\otimes |0\rangle\langle 0|\otimes I+I\otimes |1\rangle\langle 1|\otimes U. $$ Writing this as a matrix, it looks like $$ \left(\begin{array}{cccc} I & 0 & 0 & 0 \\ 0 & U & 0 & 0 \\ 0 & 0 & I & 0 \\ 0 & 0 & 0 & U \end{array}\right). $$

Answer 3

It appears that the answers from Tharrmashastha V and DaftWullie can be combined to give a rather general solution. Consider a $n$-qubit computational register that stores an equally weighted superposition

$\frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)\otimes \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)\otimes \cdots \otimes \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$

and a generic state $|\psi\rangle$ is stored in an oracle register (doesn't have to be a qubit state). Let's assume state $|\psi\rangle$ -- as a vector -- has $m$ components.

Now, retain the $i^\text{th}$ qubit (in the computational register) as a control bit and apply an operator $\hat{U}$ on state $|\psi\rangle$. This operation can be represented as the following matrix

$\underbrace{I_{2}\otimes I_{2}\otimes\cdots I_{2}}_{i-1 \ \text{times}}\otimes |0\rangle\langle 0|\otimes \underbrace{I_{2}\otimes\cdots \otimes I_{2}}_{n-i \ \text{times}}\otimes I_{m} \\ \ + \underbrace{I_{2}\otimes I_{2}\otimes\cdots I_{2}}_{i-1 \ \text{times}}\otimes |1\rangle\langle 1|\otimes \underbrace{I_{2}\otimes\cdots \otimes I_{2}}_{n-i \ \text{times}}\otimes \hat{U}$

where $I_{m}$ denotes a $m$-by-$m$ identity matrix.