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

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?

• What do you see as wrong with the second gate? Are there problems with both C and D, or just one of the two? Oct 8 at 12:44
• @MarkSpinelli it is so because the states are not maintained. When A and B are 0 and 1 respectively the outputs are 0 and 0 while A and B are 1 and 0 the outputs are 1 and 0, If 0 and 1 had been the states of the outputs it could have been a valid gate. I can just look at it logically tho,i am figuring out a way to prove it mathematically Oct 8 at 13:56
• As far as truth tables are concerned, an easy way to check if it is a valid quantum gate is to check if all the outputs are unique, i.e., they occur only once. In the case in the question, if any two-bit output repeats, it does not make a valid quantum gate. The idea comes from the necessary condition that any quantum gate has to be reversible, as explained nicely by @FDGod. Oct 12 at 8:59

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?

• I am not sure how familiar you are with bra-ket/dirac notation; hence, I avoided using it in my answer. Oct 8 at 17:28