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

Question

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?

Answer 1

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$$

2. 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).

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