Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I'm trying to understand the theory of quantum computing, and I'm a bit confused on a particular circuit:
Would the controlled NOT gate be a type of measurement, causing Q1 to be either |0> or |1>, or would the circuit be in a superposition of the |00> and |11> states until an actual measurement of Q1 or Q2 took place?
A controlled-NOT gate is meant to be a reversible operation which, for ordered pairs of bits $(a,b) \in \{0,1\}^2$, performs the operation $$ \mathrm{CNOT} (a,b)\; = \;(a, b \oplus a)$$ where conventionally we represent the "control" by the first bit and the "target" by the second. (In a physical implementation, essentially the same physical interaction but in a different orientation would be used to implement the transformation $(a,b) \mapsto (a\oplus b, b)$ and so this is also called a "controlled-NOT", rarely with any distinction from the one described above.) This gate is obviously reversible, as one can easily verify that $\mathrm{CNOT} \circ \mathrm{CNOT} = \mathrm{id}\,$.
As is usual in quantum computation, we "lift" reversible operations such as $\mathrm{CNOT}$ to distributions over inputs by describing it as a permutation of computational basis states. In particular, because $$\begin{align*} (0,0) \;&\xrightarrow{\;\mathrm{CNOT}\;\;}\; (0,0) \\ (0,1) \;&\xrightarrow{\;\phantom{\mathrm{CNOT}}\;\;}\; (0,1) \\ (1,0) \;&\xrightarrow{\;\phantom{\mathrm{CNOT}}\;\;}\; (1,1) \\ (1,1) \;&\xrightarrow{\;\phantom{\mathrm{CNOT}}\;\;}\; (1,0) \end{align*}$$ the permutation matrix which we use to represent $\mathrm{CNOT}$ is $$ \mathrm{CNOT} \;=\; \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}\; .$$ It is easy to verify that this (and all other permutation matrices) are unitary. This is the operation which transforms the state of the first two qubits. Because the state of those two qubits just before the $\mathrm{CNOT}$ gate is given by $$ |\psi_1\rangle \;=\; (H \otimes \mathbf 1) |0\rangle |0\rangle \;=\; \tfrac{1}{\sqrt 2} \Bigl[ |0\rangle |0\rangle + |1\rangle |0\rangle \Bigr] \;=\; \tfrac{1}{\sqrt 2} \begin{bmatrix} 1 \\ 0 \\ 1 \\ 0 \end{bmatrix} \,,$$ the state that we obtain afterwards is given by $$ |\psi_2\rangle \;=\; \mathrm{CNOT} |\psi_1\rangle \;=\; \tfrac{1}{\sqrt 2} \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \\ 1 \\ 0 \end{bmatrix} \;=\; \tfrac{1}{\sqrt 2} \begin{bmatrix} 1 \\ 0 \\ 0 \\ 1 \end{bmatrix} \;=\; \tfrac{1}{\sqrt 2} \Bigl[ |0\rangle |0\rangle + |1\rangle |1\rangle \Bigr] \,.$$ In this case, it's probably easiest to see that you can apply the action of $\mathrm{CNOT}$ on the standard basis states $|0\rangle|0\rangle$ and $|1\rangle|0\rangle$ separately, which form the components of $|\psi_1\rangle$, to obtain components $|0\rangle|0\rangle$ and $|1\rangle|1\rangle$ respectively; this is possible because the $\mathrm{CNOT}$ operation (and all other permutations and unitary operators) is linear.
