5.7 Other controlled gates

5.7.1 Controlled-phase

Needless to say, not everything is about the controlled-\texttt{NOT} gate. Another common two-qubit gate is the controlled-phase gate \texttt{c-}P_\varphi.

controlled-phase
\left[\begin{array}{c|c}\begin{matrix}1&0\\0&1\end{matrix}&\begin{matrix}0&0\\0&0\end{matrix}\\\hline\begin{matrix}0&0\\0&0\end{matrix}&\begin{matrix}1&0\\0&e^{i\varphi}\end{matrix}\end{array}\right]

We can also represent the \texttt{c-}P_\varphi gate using the circuit notation, as in Figure 5.2.

Where x,y\in\{0,1\}.

Figure 5.2: Where x,y\in\{0,1\}.

Again, the matrix is written in the computational basis \{|00\rangle,|01\rangle,|10\rangle,|11\rangle\}. If we do not specify the phase then we usually assume that \varphi=\pi, in which case we call this operation the controlled-Z gate, which acts as |0\rangle\langle 0|\otimes\mathbf{1}+ |1\rangle\langle 1|\otimes Z. Here Z refers again to the Pauli phase-flip \sigma_z\equiv Z operation.

In order to see the entangling power of the controlled-phase shift gate, consider the following circuit.

(Generating entanglement, again).

In this circuit, first the two Hadamard gates prepare the equally-weighted superposition of all states from the computational basis

and then the controlled-Z operation flips the sign in front of |11\rangle

which results in the entangled state.

5.7.2 Controlled-U

Both the above two-qubit controlled gates (i.e. \texttt{c-NOT} and \texttt{c-}P_\varphi) are specific examples of the more general construction of a controlled-U gate: \texttt{c-}U = |0\rangle\langle 0|\otimes\mathbf{1}+ |1\rangle\langle 1|\otimes U where U is an arbitrary single-qubit unitary transformation U.

controlled-U
\left[\begin{array}{c|c}\begin{matrix}1&0\\0&1\end{matrix}&\begin{matrix}0&0\\0&0\end{matrix}\\\hline\begin{matrix}0&0\\0&0\end{matrix}&U\end{array}\right]

We can also represent the \texttt{c-}U gate using the circuit notation, as in Figure 5.3.

Where x,y\in\{0,1\}.

Figure 5.3: Where x,y\in\{0,1\}.

We can go even further and consider a more general unitary operation: the two-qubit x-controlled-U gate: \sum_x |x\rangle\langle x|\otimes U_x \equiv |0\rangle\langle 0|\otimes U_0 + |1\rangle\langle 1|\otimes U_1 where each U_x is a unitary transformation that is applied to the second qubit only if the first one is in state |x\rangle. In general, an x-controlled-U gate can be defined on two registers of arbitrary size n and m, with x\in\{0,1\}^n and the U_x being (2^m\times 2^m) unitary matrices acting on the second register.

5.7.3 Phase kick-back

Before moving on to the next section, we first describe a simple “trick” — an unusual way of introducing phase shifts that will be essential for our analysis of quantum algorithms. Consider the following circuit.

(Controlled-U interference).

where |u\rangle is an eigenstate of U (that is, U|u\rangle = e^{i\varphi}|u\rangle for some \varphi).

This should look familiar: it is the usual interference circuit, but with the phase gate replaced by a controlled-U gate, which will mimic the phase gate, as we shall soon see. Note that the second qubit is prepared in state |u\rangle, which is required to be an eigenstate of U. The circuit effects the following sequence of transformations (omitting the normalisation factors): \begin{aligned} |0\rangle|u\rangle &\overset{H}{\longmapsto} (|0\rangle+|1\rangle)|u\rangle \\&\quad = |0\rangle|u\rangle + |1\rangle|u\rangle \\&\overset{\texttt{c-}U}{\longmapsto} |0\rangle|u\rangle + |1\rangle U|u\rangle \\&\quad = |0\rangle|u\rangle + e^{i\varphi}|1\rangle|u\rangle \\&\quad = (|0\rangle + e^{i\varphi}|1\rangle) |u\rangle \\&\overset{H}{\longmapsto} \left( \cos\frac{\varphi}{2}|0\rangle - i\sin\frac{\varphi}{2}|1\rangle \right) |u\rangle. \end{aligned} Note that the second qubit does not get entangled with the first one: it remains in its original state |u\rangle. However, the interaction between the two qubits introduces a phase shift on the first qubit. This may look like an unnecessarily complicated way of introducing phase shifts, but, as we shall soon see, this is how quantum computers do it. Let me give you a preview of things to come.

Consider the following x-controlled-U operation: \begin{gathered} \left[ \begin{array}{cccc} \mathbf{1}& 0 & 0 & 0 \\0 & \mathbf{1}& 0 & 0 \\0 & 0 & \mathbf{1}& 0 \\0 & 0 & 0 & X \end{array} \right] \\[1em] =|00\rangle\langle 00|\otimes\mathbf{1} \\+ |01\rangle\langle 01|\otimes\mathbf{1} \\+ |10\rangle\langle 10|\otimes\mathbf{1} \\+ |11\rangle\langle 11|\otimes X. \end{gathered} The first register is of size 2, and the second register is of size 1. If the first register is prepared in state |11\rangle, then the qubit in the second register is flipped (by the Pauli bit-flip X); otherwise, nothing happens. This unitary operation is a quantum version of the Boolean function evaluation: it corresponds to the Boolean function \begin{aligned} f\colon\{0,1\}^2 &\to \{0,1\} \\00&\mapsto0 \\01&\mapsto0 \\10&\mapsto0 \\11&\mapsto1. \end{aligned} If f(x)=1, then we flip the bit value in the second register (with operation X); if f(x)=0, then we do nothing.

Now, prepare the qubit in the second register in state |0\rangle-|1\rangle, which is an eigenstate of X with eigenvalue e^{\pi i}=-1. So whenever X is applied to the second register, the phase factor -1 appears in front of the corresponding term in the first register. If we prepare the first register in the superposition |00\rangle+|01\rangle+|10\rangle+|11\rangle then the result of applying the above x-controlled-U operation is the entangled state |00\rangle+|01\rangle+|10\rangle-|11\rangle. That is, the phase kick-back mechanism introduced a relative phase in the equally-weighted superposition of all binary strings of length two.

Phase kick-back is how we control quantum interference in quantum computation.

We will return to this topic later on, when we discuss quantum evaluation of Boolean functions and quantum algorithms.

5.7.4 Universality, revisited

We will come across few more gates in this course, but at this stage you already know all the elementary unitary operations that are needed to construct any unitary operation on any number of qubits:

  • the Hadamard gate,
  • all phase gates, and
  • the \texttt{c-NOT}

These gates form a universal set of gates: with O(4^{n}n) of these gates, we can construct any n-qubit unitary operation.81 We should mention that there are many universal sets of gates. In fact, almost any gate that can entangle two qubits can be used as a universal gate.

We are particularly interested in any finite universal set of gates (such as the one containing the Hadamard, P_{\frac{\pi}{4}} (the T gate), and the \texttt{c-NOT}), which can approximate any unitary operation on n qubits with arbitrary precision. The price to pay is the number of gates — better precision requires more gates. We shall elaborate on this later.

5.7.5 Density operators and the like

The existence of entangled states leads to an obvious question: if we cannot attribute a state vector to an individual qubit, then how can we describe its quantum state? In the next few chapters we will see that, when we limit our attentions to a part of a larger system, states are not represented by vectors, measurements are not described by orthogonal projections, and evolution is not unitary. As a spoiler, here is a dictionary of some of the new concepts that will soon be introduced:

state vectors \longmapsto density operators
unitary evolutions \longmapsto completely-positive trace-preserving maps
orthogonal projectors \longmapsto positive operator-valued measures

  1. Recall the big-O asymptotic notation: given a positive function f(n), we write O(f(n)) to mean “bounded above by c\,f(n) for some constant c > 0 (for sufficiently large n)”. For example, 15n^2+4n+7 is O(n^2).↩︎