10
$\begingroup$

Tried asking here first, since a similar question had been asked on that site. Seems more relevant for this site however.

It is my current understanding that a quantum XOR gate is the CNOT gate. Is the quantum XNOR gate a CCNOT gate?

$\endgroup$
  • $\begingroup$ Thanks for bringing your question here, it is indeed a great one for this site. $\endgroup$ – James Wootton Jun 14 '18 at 8:35
6
$\begingroup$

Any classical one-bit function $f:x\mapsto y$ where $x\in\{0,1\}^n$ is an $n$-bit input and $y\in\{0,1\}$ is an $n$-bit output can be written as a reversible computation, $$ f_r:(x,y)\mapsto (x,y\oplus f(x)) $$ (Note that any function of $m$ outputs can be written as just $m$ separate 1-bit functions.)

A quantum gate implementing this is basically just the quantum gate corresponding to the reversible function evaluation. If you simply write out the truth table of the function, each line corresponds to a row of the unitary matrix, and the output tells you which column entry contains a 1 (all other entries contain 0).

In the case of XNOR, we have the standard truth table, and the reversible function truth table $$ \begin{array}{c|c} x & f(x) \\ \hline 00 & 1 \\ 01 & 0 \\ 10 & 0 \\ 11 & 1 \end{array} \qquad \begin{array}{c|c} (x,y) & (x,y\oplus f(x)) \\ \hline 000 & 001 \\ 001 & 000 \\ 010 & 010 \\ 011 & 011 \\ 100 & 100 \\ 101 & 101 \\ 110 & 111 \\ 111 & 110 \end{array} $$ Thus, the unitary matrix is $$ U=\left(\begin{array}{cccccccc} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \end{array}\right). $$ This can easily be decomposed in terms of a couple of controlled-not gates and a bit flip or two.

The method that I just outlined gives you a very safe way of making the construction that works for any $f(x)$, but it does not perfectly reconstruct the correspondence between XOR and controlled-not. For that, we need to assume a little bit more about the properties of the function $f(x)$.

Assume that we can decompose the input $x$ into $a,b$ such that $a\in\{0,1\}^{n-1}$ and $b\in \{0,1\}$ such that for all values of $a$, the values of $f(a,b)$ are distinct for each $b$. In this case, we can define the reversible function evaluation as $$f:(a,b)\mapsto(a,f(a,b)).$$ This means that we're using 1 fewer bits than the previous construction, but from here on the technique can be repeated.

So, let's go back to the truth table for XNOR. $$ \begin{array}{c|c} ab & f(a,b) \\ \hline 00 & 1 \\ 01 & 0 \\ 10 & 0 \\ 11 & 1 \end{array} $$ We can see that, for example, when we fix $a=0$, the two outputs are $1,0$, hence distinct. Similarly for fixing $a=1$. Thus, we can proceed with the reversible function construction $$ \begin{array}{c|c} ab & af(a,b) \\ \hline 00 & 01 \\ 01 & 00 \\ 10 & 10 \\ 11 & 11 \end{array} $$ and this gives us a unitary $$ U=\left(\begin{array}{cccc} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array}\right) $$ You can easily check that this is the same as $\text{cNOT}\cdot(\mathbb{1}\otimes X)$.

$\endgroup$
  • $\begingroup$ brilliant! thank you for this & all the other great answers i have seen from you (: $\endgroup$ – meowzz Jun 14 '18 at 16:12
4
$\begingroup$

The quantum XNOR is not a CCNOT. CCNOT would take 3 bits as input, whereas XOR, XNOR, and CNOT take in only 2 bits or qubits as input.

The reason why we say the XOR can be thought of as a CNOT is explained here, and the same reasoning can be used to construct the (2 qubit) XNOR.

$\endgroup$
  • $\begingroup$ If XOR == CNOT, is XNOR==SWAP? $\endgroup$ – meowzz Sep 17 '18 at 1:36
  • $\begingroup$ Seems like a separate question. $\endgroup$ – user1271772 Sep 17 '18 at 3:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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