Understanding quantum circuit diagrams: a circuit that compares two states $|YX\rangle$ and $|AB\rangle$

Question

I have a quantum circuit which I would like to understand, which compares two standard basis states $|YX\rangle$ and $|AB\rangle$. It operates on the corresponding bits in each of the two states: i.e., if $$ \begin{align*} &|YX\rangle=|y_{n-1}y_{n-2}...y_0x_{n-1}x_{n-2}..x_0\rangle \quad\text{and} \\&|AB\rangle=|a_{n-1}a_{n-2}...a_0b_{n-1}b_{n-2}....b_0\rangle, \end{align*} $$ this operator or gate seems to act on the bits $y_j$ and $a_j$, and on the bits $x_j$ and $b_j$, for each $j$.

Here is the diagram of the circuitry involved: I understand the computations part of it, but can anybody explains the diagram:

Answer 1

How to read the circuit

You should think of this as a diagram describing a transformation of the qubits. The input state of the qubits is on the left, and describes the state $|Y\rangle \otimes |X\rangle \otimes |A\rangle \otimes |B\rangle$, reading the qubits from top to bottom. Each qubit corresponds to a horizontal wire, which we trace from left to right.

The qubits are acted on by operations, which are represented by nodes, symbols, or boxes which interrupt the wires. We think of these (abstractly) as gates which happen at a specific moment in time, e.g. at integer time steps. These correspond to quantum gates.

The symbols in your upper circuit are different variations of controlled-not gates:

• A filled cdot on one wire, directly above (or below) an $\oplus$ symbol on another wire, represents a CNOT gate where the target is where the $\oplus$ symbol is put. These are connected by a vertical wire, which may pass over other qubit wires. (These qubits are not involved in the operation).

• A hollow dot on one wire, directly above (or below) an $\oplus$ symbol on another wire, represents a CNOT gate where the target is where the $\oplus$ symbol is put, and where the operation is conditioned on the control being in the state $|0\rangle$ instead of $|1\rangle$.

• A vertical wire which connects several filled (or empty) dots to an $\oplus$ symbol is a multiply-controlled NOT gate. In the case that all of the dots are filled, it performs the operation $$ \mathrm{C^k NOT} = \mathbf 1^{\otimes k} \otimes \mathbf 1 + \Bigl(\lvert11\cdots1\rangle\!\langle11\cdots1\rvert \otimes \bigl(X - \mathbf 1\bigr)\Bigr)$$ which performs an $X$ operation on the target provided that all of the $k$ control qubits (marked with filled dots) are all in the state $|1\rangle$. Variations in which some or all of the dots are hollow depend on those specific qubits being in the state $|0\rangle$ instead; and the gate acts on arbitrary states in linear superposition, according to how they decompose into standard basis states.

What the circuit does

Most of the gates in the circuit are CNOT gates, but conditioned on the control being 0 instead of 1:$\def\xCNOT{\overline{\textrm{CNOT}}}$ $$ \xCNOT = \lvert 0 \rangle\!\langle 0 \rvert \otimes X + \lvert 1 \rangle\!\langle 1 \rvert \otimes \mathbf 1 $$ (note that this is not standard notation). What happens if you take two standard basis states, and act on them with this opposite-CNOT, is that the target will have the value 1 if and only if the control and target had different values. $$ \begin{aligned} \xCNOT \lvert a \rangle\lvert b \rangle &= \lvert a \rangle \lvert b \oplus (\neg a)\rangle \\&= \lvert a \rangle \lvert b \oplus (a \oplus 1)\rangle \\&= \lvert a \rangle \lvert (b \oplus a) \oplus 1\rangle \\&= \begin{cases} \lvert a \rangle \lvert 0 \rangle, & \text{if $a = \neg b$}; \\ \lvert a \rangle \lvert 1 \rangle, & \text{if $a = b$}. \end{cases} \end{aligned} $$ Your circuit is performing this, and then performing a multiply-controlled-NOT gate conditioned on those targets all being equal to 1 — that is, conditioned on all of those pairs of qubits being equal if they happen to be standard basis states. If that is the case, then the pairs of inputs are indeed equal, so the target of that multiply-controlled-NOT gate is flipped. The computation of whether the individual qubit-pairs are equal is then undone to restore the original standard basis inputs.

For general quantum states, this all occurs in coherent superposition, of course. But for standard basis states, this realises an equality test.