How to figure out whether a truth table can correspond to a valid quantum gate

Question

I am new to quantum computing and trying to wrap my head around this exercise from Wong's introduction to classical and quantum computer.

I can interpret it mentally that first is a valid quantum gate and second one is not; How can I prove it Mathematically?

Answer 1

Quantum gates need to be reversible, as you have mentioned in the title. Reversible means that given the output $(C,D)$, there exists a unique input $(A,B)$.

As you said, for case (b),

Given that output $(C,D) = (0,0)$; Can you know what the input $(A,B)$ was? No. Because both

input $(A,B) = (0,0)$ and

input $(A,B) = (0,1)$, both maps to output $(C,D) = (0,0)$.

More precisely, given that $(C,D) = (0,0)$, you can say that $A$ has to be $0$, but you don't have any information about $B$. It can be $0$ or $1$, and hence, this operation is not reversible, and hence it is not a valid quantum gate.

---

You can observe for case (a) that given any output $(C,D)$, you can always uniquely identify what the input $(A,B)$ must have been. There is no loss of information in this operation. It is reversible and, hence, a valid quantum operation. You will require two qubits to perform this.

---

Showing that mapping from inputs to output is many-to-one (surjective map) is sufficient to argue that the operation is irreversible.

---

If you want to show it rigorously, another way would be to represent this operation as a matrix and see that the matrix is invertible (i.e., has a full rank, has a non-zero determinant) and, hence, reversible.

For case (a):

Let denote input $(A,B)$ & output $(C,D)$ bits as the following vectors:

$$(0,0) := \begin{bmatrix}1\\0\\0\\0\\\end{bmatrix},(0,1) := \begin{bmatrix}0\\1\\0\\0\\\end{bmatrix}\,, (1,0) := \begin{bmatrix}0\\0\\1\\0\\\end{bmatrix}\,, (1,1) := \begin{bmatrix}0\\0\\0\\1\\\end{bmatrix}\,.$$

Then you can represent this operation as matrix $U$, where $$U = \begin{bmatrix}0&0&1&0\\1&0&0&0\\0&0&0&1\\0&1&0&0 \end{bmatrix}\,.$$

You can easily check that this matrix is invertible, and hence reversible and hence a valid quantum operation.

• The way this $U$ operation works, is that let $\vec{x}$ be the vector corrosponding to your inputs $(A,B)$; as defined above. Then your output would be $\vec{y}$, corrosponding to output $(C,D)$; as defined above, where $$\vec{y} = U \cdot \vec{x}\,.$$

---

Construct this matrix corresponding to the operation in case (b). Do you get an invertible matrix?