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

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

  • $\begingroup$ What do you see as wrong with the second gate? Are there problems with both C and D, or just one of the two? $\endgroup$ Commented Oct 8, 2023 at 12:44
  • $\begingroup$ @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 $\endgroup$
    – Ri dev
    Commented Oct 8, 2023 at 13:56
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Oct 12, 2023 at 8:59

1 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?

  • 1
    $\begingroup$ I am not sure how familiar you are with bra-ket/dirac notation; hence, I avoided using it in my answer. $\endgroup$
    – FDGod
    Commented Oct 8, 2023 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.