# How does a generic controlled-U operation work?

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?

• When you say that you retain another qubit as the control bit, do you mean that $U$ is controlled on two qubits or just the second one? Also in the last you just say that you have a $|+++\rangle$ state and use second qubit as control and apply $U$. But on which qubit/register are you applying the $U$ on? Could you be a bit more specific? – Tharrmashastha V Dec 11 '20 at 5:55
• @Tharrmashastha V Retaining the second bit as control bit means taking only the second bit as control. Here, since the discussion is on the amplitude estimation like algorithm, the operator $U$ is applied to the oracle register. Question is edited to specify this target. – Xavier van den Bosch Dec 11 '20 at 5:59

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.

• I adore you answer but I don't quite understand the dimension of your $M_{u}$ matrix. Taking your example $|+\rangle|+\rangle |\phi\rangle$. If state $|\phi\rangle$ is a $n$-qubit state, the dimension - number of elements in a state vector - of state $|+\rangle|+\rangle |\phi\rangle$ shall be $2^{2}\times 2^{n}$. However, matrix $M_{u}$ in this case has a dimension $(8+2n)\times(8+2n)$. Do they match? – Xavier van den Bosch Dec 11 '20 at 9:20
• I am extremely sorry. I made a mistake in the dimension of the matrix $U$. Since $U$ is a $n$-qubit unitary, the dimension of $U$ is $2^n\times 2^n$. I have made this correction in the answer now. I hope the answer makes sense now. – Tharrmashastha V Dec 11 '20 at 9:29

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

• Tried to vote this as accepted answer, too. Unfortunately I could choose only one. – Xavier van den Bosch Dec 11 '20 at 10:28
• Yes, that's the way it works! Just beware that in your accepted answer, the stated $M$ is not what you asked for (different control qubit), which is why it looks different to my stated answer. – DaftWullie Dec 11 '20 at 11:00
• Thanks for the reminder. I was aware of the statement the author made in the original post. That was why I combined your answer and the other one into a more general case in my post. – Xavier van den Bosch Dec 11 '20 at 11:05

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.