Measuring in the computational basis in the single qubit gate QFT implementation

Question

I've come across this paper about a single-qubit-gate-only QFT implementation. In the paper it is claimed that measuring a qubit after applying the Hadamard gate (it isn't called Hadamard gate in the paper but its description matches that of the Hadamard gate) is no different from measuring before the gate.

Now what I assumed is that the measurement before the gate would have been made in the $\{|0⟩,|1⟩\}$ basis and the measurement after the gate would have been made in the $\{|+⟩,|-⟩\}$ basis.

However, I came across these conflicting sources about the term "Computational Basis" regarding measurement:

• this Wikipedia page
• this question in this stack exchange.
• This site

So my questions are:

1. Does saying "measure in the computational basis" means that in whatever basis you qubits are in you measure them according to that basis to get classical bits or does it always refer to measuring in the {|0⟩,|1⟩} basis?
2. If it is the latter then how does the claim hold when we know that $H|0\rangle=\frac{1}{\sqrt 2}(|0⟩+|1⟩)$ and $H|1\rangle=\frac{1}{\sqrt 2}(|0⟩-|1⟩)$ so the probabilities of measuring an outcome after H should be $\frac{1}{2}$ regardless of the original state of the qubit?

Answer 1

Measuring in the 'Computational Basis' always means to measure in the $\{|0\rangle,|1\rangle\}^n$ basis for $n$ qubits.

As for your second question, I feel that you misinterpreted the author. It is certainly true that on applying the $H$ gate on $|0\rangle$ or $|1\rangle$ you would get the states $|0\rangle$ and $|1\rangle$ with equal probabilities. But the underlying idea is this: let $q$ be a qubit in the circuit given in the paper. Let $m$ many gates are applied on $q$. For some $k\le m$, see that if only the first $k$ gates actually transform the state of $q$ (by some rotation) and if for the rest of the $m-k$ gates $q$ just acts as a control qubit, then the last $m-k$ gates cannot change the state of $q$. So, if the probability of obtaining $|0\rangle$ on measuring the qubit $q$ as $|0\rangle$ was $p$ before applying the last $m-k$ gates, then even after applying the $m-k$ gates, the probability of obtaining $|0\rangle$ on measuring $q$ remains $p$. The author then uses this fact and uses the measured outcomes to control the other gates. An example might help understand. Take, for instance, the following three qubit circuit:

In this circuit, $q_0$ gets rotated in the first gate and just acts as a control qubit for the next two gates. Now notice that if you were to measure $q_0$ just after the first gate, you would get $|0\rangle$ and $|1\rangle$ with equal probabilities. But if you measure $q_0$ after all the gates have been applied, the probabilities of obtaining $|0\rangle$ and $|1\rangle$ still remain the same.

Next, notice that the output of this circuit is $|\psi\rangle = \frac{1}{\sqrt{2}}(|000\rangle + |111\rangle)$. So you get the states $|000\rangle$ and $|111\rangle$ with equal probabilities on measuring all the qubits of the circuit after all the gates have been applied. Now, on the other hand let us first measure the qubit $q_0$ just after $H$, then apply an $X$ gate to $q_1$ and $q_2$ only if the measured outcome of $q_0$ is 1 and then measure the qubits $q_1$ and $q_2$. Now, if the measurement of $q_0$ yields $|0\rangle$ then the other two gates have no effect on $q_1$ and $q_2$. So after the final measurement, the complete measured state would be $|000\rangle$. Similarly, if the measurement of $q_0$ yields $|1\rangle$ then the other two gates flips the qubit state in $q_1$ and $q_2$. So after the final measurement, the complete measured state would be $|111\rangle$. Now, if you perform this for some $d$ times, then for an expected $d/2$ times you obtain $|0\rangle$ during the first measurement and so obtain $|000\rangle$ as the final measurement and for an expected $d/2$ times you obtain $|1\rangle$ during the first measurement and so obtain $|111\rangle$ as the final measurement. Now, see that in both the cases, you obtain the same probability distribution. But in the first case we use two two-qubit gates but in the second case, we use no two-qubit gates. So irrespective of whether you measure a qubit after all the gates in a circuit or whether you measure a qubit just after all the rotations on it have been applied, the output probability distribution turns out to be the same. This is the idea that the author tries to convey and use in constructing the single-qubit-gate-only QFT implementation in the paper.