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: enter image description here


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

  • $\begingroup$ Sir i a have a few questions. First of all i know the symbol of CNOT gate i.e a solid dot on the control bit and an XOR symbol on the target bit, but what does this hollow dots on the control bit mean. Second, how did you know that the control bit is $0$ instead of $1$. Can you explain the diagram a bit how do these lines that connect mean. $\endgroup$
    – Upstart
    Mar 26, 2019 at 17:23
  • $\begingroup$ The hollow dot is a convention, lesser known than the usual CNOT but still common, which precisely means for the NOT to be controlled on 0. (Perhaps it says so in the article or text where the diagram came from.) The rest is all the same as usual: if you have more questions, you might want to ask them separately, because they are more general questions about circuit diagrams. $\endgroup$ Mar 26, 2019 at 20:42
  • $\begingroup$ okay i will ask them separately $\endgroup$
    – Upstart
    Mar 27, 2019 at 4:29
  • $\begingroup$ @Upstart: I would like to apologise --- I read your question too quickly at first, and did not realise that your question was only about the circuit drawing itself. I have revised my answer to include a description of how to read the circuit. $\endgroup$ Mar 27, 2019 at 12:23
  • $\begingroup$ okay sir i will try yo understand this $\endgroup$
    – Upstart
    Mar 27, 2019 at 15:09

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.