# Is the outcome of this quantum circuit correct and if so why?

I am very novice with quantum computing and try to understand it. I thought I was getting a handle on it until I built the quantum circuit (1) below. The app I used to build it allows me to measure the possible outcomes. It was no surprise for me that whenever the fifth qbit resulted in a zero, that there would be an even number of qbits following it. However, when it resulted in a one I was surprised to see there were only two possible outcomes, each with approximately 25% chance of occurring. The states are [10000> and [11111> (note that the first qbit is put in the rightmost position and the fifth in the leftmost). What I was expecting was to see that one followed by all possible 4-qbit states, so: [10000>, [10001>, [10010>, [10011>, ..., [11110>, [11111>. Am I wrong or the app I used?

The way I understand it is as follows:

1. First I put it in a uniform superposition where all 16 4-qubit states are equally possible using independent Hadamard gates.
2. Then I check the parity of each state in the superposition using CNOT gates. So if a state has an odd number of ones, then the fifth bit will be flipped an odd number of times resulting in a one.
3. Perform a Hadamard operation on each of the first qbit if the fifth qbit is a one. I expected this to turn [10001> into [10000> and [10001>, [10010> into [10010> and [10011>, ..., and [11110> into [11110> and [11111>. (So far measurements seem to confirm this expectation)
4. Do the same for the second qbit. Now I see dependencies between those first and second qbits appear that I did not expect. I would for example expect [10000> and [10001> to become [10000>, [10010>, [10001>, and [10011>, but instead it seems those two states transform into just [10000> and [10011>.
5. Do the same for the third and fourth qbits.

What's actually happening here at step 4? What am I missing?

This circuit might be a bit hard to analyze if you’re just getting started with quantum computing, so I will try to explain it step by step:

1. The $$H$$ gates place the top four qubits in an equal superposition:

$$|\psi_1\rangle = \frac{1}{\sqrt{2^4}} \sum_{x = 0}^{2^4-1} |x\rangle \otimes|0\rangle$$

1. The $$CNOT$$ gates compute the parity of $$x$$ and stores it in the last qubit ($$0$$ for even parity, $$1$$ for odd parity):

$$|\psi_2\rangle = \frac{1}{\sqrt{2^4}} \sum_{x = 0}^{2^4-1} |x\rangle \otimes\left|\bigoplus_{i=0}^4 x_i\right\rangle.$$

Here, $$\bigoplus$$ denotes addition $$\text{mod } 2$$ over the bits of $$x$$, so the expression above can be rewritten as:

$$|\psi_2\rangle = \frac{1}{\sqrt{2^4}} \left (\sum_{x \in\text{even}} |x\rangle \otimes |0\rangle + \sum_{x \in\text{odd}} |x\rangle \otimes |1\rangle\right )$$

(I think you understand things very well up to this point).

1. Then, the $$CH$$ gates will:
• Leave $$x$$ unchanged for those states with even parity (i.e., states where the fifth qubit is $$|0\rangle$$).
• Apply $$H$$ gates to the top 4 qubits if the parity is odd (i.e., states where the fifth qubit is $$|1\rangle$$):

$$|\psi_3\rangle = \frac{1}{4} \left (\sum_{x \in\text{even}} |x\rangle \otimes |0\rangle + \sum_{x \in\text{odd}} H^{\otimes4}|x\rangle \otimes |1\rangle\right ),$$

The tricky step here is figuring out what this part of the expression: $$\sum_{x \in\text{odd}} H^{\otimes4}|x\rangle$$ is equal to once we apply the Hadamard gates on the top 4 qubits.

Well, it turns out that this is equal to a GHZ state of the following form:

$$\frac{1}{\sqrt{2^3}} \sum_{x \in\text{odd}} H^{\otimes4}|x\rangle = \frac{1}{\sqrt{2}} \left( |0000\rangle - |1111\rangle \right).$$

To understand why, it is easier to work backwards (since the Hadamard is its own inverse). If you apply 4 Hadamard gates to the state $$\frac{1}{\sqrt{2}} \left(|0000\rangle - |1111\rangle \right)$$, you get the superposition of odd parity states. Similarly, if you were to apply $$H$$ gates to $$\frac{1}{\sqrt{2}} |0000\rangle + |1111\rangle$$ you will get the superposition of even parity states. This is because the $$H$$ gates create the right number of even/odd pairs of opposite signs to cancel out the even/odd parity terms leaving only the odd/even parity terms in the superposition. I strongly encourage you to try this out with pen and paper; it is a great exercise.

So, at the end, what you end up with is the state:

$$|\psi_3\rangle = \frac{1}{4} \sum_{x \in\text{even}} |x\rangle \otimes |0\rangle + \frac{1}{2} \left(|0000\rangle - |1111\rangle \right) \otimes |1\rangle .$$

As a matter of fact, this result can be generalized for an abitrary number of $$n+1$$ qubits (the $$+1$$ being for the parity qubit):

$$|\psi \rangle = \frac{1}{\sqrt{2^n}} \sum_{x \in\text{even}} |x\rangle \otimes |0\rangle + \frac{1}{\sqrt{2}} |\Phi^-_n\rangle \otimes |1\rangle,$$

where $$|\Phi^-_n\rangle$$ is an $$n$$-qubit GHZ state with negative relative phase.

• Great break down of the circuit Commented Aug 2 at 22:56